     Next: Deflation and Stopping Rules Up: Implicitly Restarted Lanczos Method Previous: Convergence Properties   Contents   Index

The implicit scheme costs rather than the matrix-vector products the explicit scheme would require to apply the same -degree polynomial and rebuild the -step Lanczos factorization. When the operation is relatively expensive, this savings can be considerable. However, there are tradeoffs. It is impossible to predict optimal values for the number of extra vectors in general.

The convergence behavior depends to a great deal on the distribution of the spectrum of . Two matrices with precisely the same sparsity pattern could exhibit completely different convergence characteristics for a given choice of and . Therefore, it would be misleading to draw any conclusions based solely on operation counts per iteration. Nevertheless, it can be useful to have a notion of the major costs of an iteration to guide initial choices.

In the following, we assume that the cost of a matrix-vector product is . For a sparse matrix, one could think of as twice the average number of nonzero entries per row of . For a dense matrix , and for a fast Fourier transform (FFT) matrix . See §10.2. For a fixed value of and , the cost (in floating point operations) for one iteration of IRLM is

• matrix-vector products : ;
• basic Lanczos steps: ;
• orthogonalization corrections: roughly per correction. A worst-case estimate is per IRLM iteration (assumes one correction per each new Lanczos vector);
• implicit restart: ;
• total cost: .

If the matrix-vector product is cheap (i.e., is quite small), the cost of implicit restart is significant and alternatives should be considered. One of these might be to use a polynomial spectral transformation. This would involve operating with a suitably constricted polynomial function of in place of . An example would be a Chebyshev polynomial designed to damp the unwanted portion of the spectrum. The action would, of course, be applied as a succession of matrix-vector products involving .     Next: Deflation and Stopping Rules Up: Implicitly Restarted Lanczos Method Previous: Convergence Properties   Contents   Index
Susan Blackford 2000-11-20