Computational Costs and Tradeoffs

This 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 Arnoldi factorization. When the operation $w \leftarrow Av$ is relatively expensive, this savings can be considerable. However, there are tradeoffs. It is impossible to predict optimal values for $k$ and $p$ in general. The distribution of the spectrum of $A$ has a great deal to do with convergence behavior. 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 $w \leftarrow 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 an FFT matrix $\gamma \approx \log(n)$. See §10.2. For a fixed value of $k$ and $p$, the cost (in floating point operations) for one iteration of IRAM is

1. matrix-vector products $w \leftarrow Av$: $\gamma p n$;

2. Arnoldi steps (extend from $k$ to $k+p$) : $[(4k-2)p + 2p^2]n$;

3. orthogonalization corrections: roughly $4(k+p)n$ per correction. A worst-case estimate is $[(4k-2)p + 2p^2]n$ (assumes one correction per each new Arnoldi vector);

4. implicit restarting: $2 n(k^2 + kp) + O( (k+p)^3)$;

5. total cost: $\gamma p n + 2[(5k-2)p + 2p^2]n + 2k^2n + O( (k+p)^3)$.

Note that the factor of 2 in the second term is due to a worst-case scenario with respect to orthogonalization corrections. This factor will usually be around 1.5 in practice. If the matrix-vector product $Av$ is cheap ( i.e. $\gamma$ is quite small) then the cost of implicit restarting 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 constructed 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 $w \leftarrow \psi(A)$ would, of course, be applied as a succession of matrix-vector products involving $A$.