Computational cost of Arnoldi and Lanczos

• nnz: number of non-zero entries in matrix $A$.
• nnz is $O(n)$ for sparse matrices.

Arnoldi

• Matrix-vector products: $O(k\mathrm{nnz})$.
• $h_{ik}={\mathbf{q}}_i^{T}A{\mathbf{q}}_k,$ $1\le i\le k.$ $O(kn)$ per iteration.
• Vector operations: $O(k^{2}n)$ total cost.

Lanczos

• Matrix-vector products: $O(k\mathrm{nnz})$.
• Vector operations: $O(kn)$ total cost.
• Lanczos is much more efficient!

Algorithm for the Arnoldi process, Algorithm for the Lanczos process