next up previous contents index
Next: Deflation and Stopping Rules Up: Implicitly Restarted Arnoldi Method Previous: Numerical Stability   Contents   Index

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


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