The Lanczos Connection     Next: Block and -step Up: Remaining topics Previous: Remaining topics

# The Lanczos Connection

As discussed by Paige and Saunders in  and by Golub and Van Loan in , 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 § . 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 ) 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 ( ), which are readily available during iterations of the conjugate gradient algorithm (§ ), 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 ) would produce a nonsymmetric matrix in ( ) whose extremal eigenvalues (which may include complex-conjugate pairs) approximate those of . The nonsymmetric Lanczos method is equivalent to the BiCG method discussed in § .     Next: Block and -step Up: Remaining topics Previous: Remaining topics

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