The Lanczos Connection



next up previous contents index
Next: Block and -step Up: Remaining topics Previous: Remaining topics

The Lanczos Connection

   

As discussed by Paige and Saunders in [168] and by Golub and Van Loan in [109], it is straightforward to derive the conjugate gradient method for solving symmetric positive definite linear systems from the Lanczos algorithm for solving symmetric eigensystems and vice versa. As an example, let us consider how one can derive the Lanczos process for symmetric eigensystems from the (unpreconditioned) conjugate gradient method.

Suppose we define the matrix by

and the upper bidiagonal matrix by

where the sequences and are defined by the standard conjugate gradient algorithm discussed in §gif. From the equations

and , we have , where

Assuming the elements of the sequence are -conjugate, it follows that

is a tridiagonal matrix since

Since span{} = span{} and since the elements of are mutually orthogonal, it can be shown that the columns of matrix form an orthonormal basis for the subspace , where is a diagonal matrix whose th diagonal element is . The columns of the matrix are the Lanczos vectors (see Parlett [171]) whose associated projection of is the tridiagonal matrix

 

The extremal eigenvalues of approximate those of the matrix . Hence, the diagonal and subdiagonal elements of in (gif), which are readily available during iterations of the conjugate gradient algorithm (§gif), can be used to construct after CG iterations. This allows us to obtain good approximations to the extremal eigenvalues (and hence the condition number) of the matrix while we are generating approximations, , to the solution of the linear system .

For a nonsymmetric matrix , an equivalent nonsymmetric Lanczos algorithm (see Lanczos [142]) would produce a nonsymmetric matrix in (gif) whose extremal eigenvalues (which may include complex-conjugate pairs) approximate those of . The nonsymmetric Lanczos method is equivalent to the BiCG method discussed in §gif.  



next up previous contents index
Next: Block and -step Up: Remaining topics Previous: Remaining topics



Jack Dongarra
Mon Nov 20 08:52:54 EST 1995