of the n x n matrix A is computed efficiently
by using the n x n identity matrix as the matrix B .
In that case, the columns of the n x n matrix X
are the columns of .
This page provides an outline of the LAPACK operations
related to solving dense linear systems. For more details, see, for example,
[55]
or the other references herein.
A linear system Ax = b with a dense coefficient matrix A is solved by a three step process. To begin, the matrix A is factored (using partial pivoting) into the product PA = LU , where P is a permutation matrix, L is unit lower triangular, and U is upper triangular. The linear system may then be rewritten as PAx = LUx = Pb . After making the substitution y = Ux , the lower triangular system Ly = Pb is solved by the method of forward elimination. The upper triangular system Ux = y is then solved via backsubstitution.
When solutions are needed for many right hand side vectors, those
vectors are stored as the columns of a matrix B , and the same
procedure is followed for the system AX = B using the matrix substitution
UX = Y . The columns of the matrix X are the solution vectors.
The inverse
of the n x n matrix A is computed efficiently
by using the n x n identity matrix as the matrix B .
In that case, the columns of the n x n matrix X
are the columns of .
The condition number of a square, invertible matrix A is defined as
, where
p is 
or
one of the other possibilities listed in
Table 4.2. The condition number
measures how sensitive is to
changes in A: the larger
the condition number, the more sensitive
.
LAPACK condition estimation routines typically compute a variable called RCOND , which is the reciprocal of the condition number (or an approximation of the reciprocal). The reciprocal of the condition number is used instead of the condition number itself in order to avoid the possibility of overflow when the condition number is very large. To spare the expense of computing the inverse, condition numbers are not computed exactly but rather are approximated. Details of the approximation methods may be found in [63].
LAPACK provides computational routines for evaluating the accuracy of a computed solution to a linear system. Both backward and forward error bounds are produced. For more details, see section 4.4 of the LAPACK Users' Guide .
The LAPACK equilibration routines attempt to reduce the condition number of an m x n matrix A by rescaling its elements. The row scale factors R and the column scale factors C are chosen to try to make the largest element in each row and column of the matrix B with elements B(i,j)=R(i)*A(i,j)*C(j) have absolute value 1. The scaling factors are not guaranteed to reduce the condition number of A, but they do work well in practice.
More specifics of the corresponding computational routines are available
in section 2.4 of the LAPACK Users' Guide .
1999-12-21