next up previous contents index
Next: Deflation and Stopping Rules Up: Implicitly Restarted Lanczos Method Previous: Convergence Properties   Contents   Index

Computational Costs and Tradeoffs

The implicit scheme costs $p$ rather than the $k+p$ matrix-vector products the explicit scheme would require to apply the same $p$-degree polynomial and rebuild the $k$-step Lanczos factorization. When the operation $r = Av $ 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 $p$ in general.

The convergence behavior depends to a great deal on the distribution of the spectrum of $A$. Two matrices with precisely the same sparsity pattern could exhibit completely different convergence characteristics for a given choice of $k$ and $p$. 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 $r = Av $ is $\gamma n$. For a sparse matrix, one could think of $\gamma$ as twice the average number of nonzero entries per row of $A$. For a dense matrix $\gamma = 2 n$, and for a fast Fourier transform (FFT) matrix $\gamma \approx \log_2(n)$. See §10.2. For a fixed value of $k$ and $p$, the cost (in floating point operations) for one iteration of IRLM is

If the matrix-vector product $Av$ is cheap (i.e., $\gamma$ 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 $\psi(A)$ in place of $A$. An example would be a Chebyshev polynomial designed to damp the unwanted portion of the spectrum. The action $r = \psi(A)\, v$ would, of course, be applied as a succession of matrix-vector products involving $A$.


next up previous contents index
Next: Deflation and Stopping Rules Up: Implicitly Restarted Lanczos Method Previous: Convergence Properties   Contents   Index
Susan Blackford 2000-11-20