Do We Fully Understand the Symmetric Lanczos Algorithm Yet?
CALIFORNIA UNIV BERKELEY DEPT OF MATHEMATICS
Pagination or Media Count:
Imagine that one has computed the real n-vectors b, Ab, A2b,..., Am-1b where A is a real symmetric nxn matrix. Lanczos showed us in 1950 how to construct a much better basis for the Krylov space spanned by these power vectors and for little extra cost. The new basis q1, q2,..., qm now called the Lanczos basis, has two nice properties 1 it is orthonormal, 2 the representation of As projection is a symmetric tridiagonal matrix Tm. Property 2 is synonymous with the three term recurrence governing the Lanczos vectors. Moreover, some of Tms eigenvalues, called Ritz values hereafter, are excellent approximations to some of As eigenvalues even when m n. In addition we can tell, with little expense, which Ritz values are also eigenvalues. One surprising implication of these properties is that it is easier to find the largest few eigenvalues of A than to solve Axb When the Lanczos algorithm is implemented in a computer the user discovers an unpleasant fact. Property 1 fails completely for m as small as 20 or 30 and consequently the computed Tms relation to A is unclear. Lanczos was aware of this blemish and proposed the obvious remedy keep applying the Gram-Schmidt process to each new Lanczos vector as it is computed. The catch here is that all the qi must be kept handy whereas in exact arithmetic only the three latest Lanczos vectors are needed and earlier qs may be discarded. The arithmetic cost of this full reorthogonalization grows quadratically with m. So the hope of computing Tn efficiently and accurately by the Lanczos algorithm was dashed and other methods prevailed. In exact arithmetic Tn is similar to A and the algorithm stops. AN
- Numerical Mathematics