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

• matrix-vector products $r = Av$: $\gamma p n$;
• basic Lanczos steps: $9 pn$;
• orthogonalization corrections: roughly $4(k+p)n$ per correction. A worst-case estimate is $4(kp + p^2)n$ per IRLM iteration (assumes one correction per each new Lanczos vector);
• implicit restart: $2 n(k^2 + kp) + O( (k+p)^3)$;
• total cost: $\gamma p n + (6k + 9)pn + 4p^2 n + 2k^2n + O( (k+p)^3)$.

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$.