Arnoldi Nonsymmetric Krylov Hessenberg

worked-example

Let us trace the first step of the Arnoldi iteration for a simple 3 × 3 matrix A = [[0, 1, 0], [0, 0, 1], [0, 0, 0]] with a starting vector v = [[1], [0], [0]]. We aim to compute the first column of the Hessenberg matrix H.

1. Initialize q_1 = v / ‖v‖ = [[1], [0], [0]].
2. Compute w = A q_1 = [[0], [0], [0]].
3. Compute h_(1,1) = q_1^T w = 0.
4. Update w = w - h_(1,1) q_1 = [[0], [0], [0]].
5. Compute h_(2,1) = ‖w‖ = 0. Since h_(2,1) = 0, we have a happy breakdown. The Krylov subspace is exactly invariant under A.

experiment

You can interactively explore the Arnoldi algorithm using theArnoldi Nonsymmetric Krylov Hessenberg module.

1. Set the Matrix control to Nonnormal and the Start vector to ones.
2. Set the Steps control to 2 to observe the dimension of the subspace and the upper Hessenberg matrix elements.
3. Change the Matrix control to Shift and the Start vector to e1. Observe the Happy Breakdown field change to Yes at step 1.

limitations

The standard Arnoldi process uses modified Gram-Schmidt orthogonalization. However, in finite precision arithmetic, orthogonality can be lost if a vector is normalized after severe cancellation. The module uses a double modified Gram-Schmidt pass (also known as the "twice is enough" approach) to better maintain numerical orthogonality. Even so, rounding errors will eventually accumulate for large matrices, requiring restart strategies like in implicitly restarted Arnoldi methods.

references

For more detailed background on the Arnoldi algorithm and Krylov subspace methods, refer to the primary literature on iterative methods for linear systems.

• Saad, Y. (2003). Iterative Methods for Sparse Linear Systems (2nd ed.). SIAM.https://www-users.cse.umn.edu/~saad/IterMethBook_2ndEd.pdf