Arnoldi iteration
Arnoldi finds an approximation to the eigenvalues and eigenvectors of general (possibly non-Hermitian) matrices by constructing an orthonormal basis of the Krylov subspace, which makes it particularly useful when dealing with large sparse matrices.
The Arnoldi method belongs to a class of linear algebra algorithms that give a partial result after a small number of iterations, in contrast to so-called direct methods which must complete to give any useful results (see for example, Householder transformation).
The partial result in this case being the first few vectors of the basis the algorithm is building.
[1] An intuitive method for finding the largest (in absolute value) eigenvalue of a given m × m matrix
is the power iteration: starting with an arbitrary initial vector b, calculate Ab, A2b, A3b, ... normalizing the result after every application of the matrix A.
We may expect the vectors of this basis to span good approximations of the eigenvectors corresponding to the
Every step of the k-loop takes one matrix-vector product and approximately 4mk floating point operations.
In the programming language Python with support of the NumPy library: Let Qn denote the m-by-n matrix formed by the first n Arnoldi vectors q1, q2, ..., qn, and let Hn be the (upper Hessenberg) matrix formed by the numbers hj,k computed by the algorithm: The orthogonalization method has to be specifically chosen such that the lower Arnoldi/Krylov components are removed from higher Krylov vectors.
can be expressed in terms of q1, ..., qi+1 by construction, they are orthogonal to qi+2, ..., qn, We then have The matrix Hn can be viewed as A in the subspace
The relation between the Q matrices in subsequent iterations is given by where is an (n+1)-by-n matrix formed by adding an extra row to Hn.
Also Francis' algorithm itself can be considered to be related to power iterations, operating on nested Krylov subspace.
In fact, the most basic form of Francis' algorithm appears to be to choose b to be equal to Ae1, and extending n to the full dimension of A.
Improved versions include one or more shifts, and higher powers of A may be applied in a single steps.
This can be related to the characterization of Hn as the matrix whose characteristic polynomial minimizes ||p(A)q1|| in the following way.
Due to practical storage consideration, common implementations of Arnoldi methods typically restart after a fixed number of iterations.
One approach is the Implicitly Restarted Arnoldi Method (IRAM)[3] by Lehoucq and Sorensen, which was popularized in the free and open source software package ARPACK.
[4] Another approach is the Krylov-Schur Algorithm by G. W. Stewart, which is more stable and simpler to implement than IRAM.
