Implementation of some methods to solve eigenvalue problem with the use of Krylov subspaces in C++.
The Krylov subspace is the space spanned by the set of vectors:
Methods making use of these subspaces are most effective for large sparse matrices, as they use matrix-vector multiplication and the resulting subspace to search for solutions as opposed to normal matrix-matrix multiplication, which becomes very expensive for larger systems.
This is the most simple method and is used to approximate the largest eigenvalue of a system, where the iteration is very simply:
This comes from the idea that approximates the dominant eigenvector. Therefore, the dominant eigenvalue comes from the Rayleigh quotient:
Where the power method estimates the largest eigenvalue of , the inverse power method estimates the smallest eigenvalue of
. The only extra step is to invert
, such that the iteration becomes:
and then the eigenvalue can be extracted from the converged to eigenvector via the Rayleigh quotient as before.
Here the iteration intends to converge to the eigenvalue closest to the given value, :
Where the inverse power method operates for = 0. Further, finding the inverse of large matrices is not the most pleasant task, therefore typically the approach is to solve the following linear system.
Naturally the better the guess of , the faster the convergence. This means in some cases that it is more efficient to update
with the Rayleigh quotient and 'restart' the iteration, instead of sticking with the same
until convergence.
#TODO
A specific form of the Arnoldi method, for when is Hermitian (square matrix which is equal to the conjugate transpose of itself).
The purpose of Lanczos is to reduce the hermitian matrix to a smaller tri-diagonal matrix, for which the eigenpairs can be readily found via another method (QR is common). However, this only works if the eigenpairs of approximate those of
(which isn't actually guarunteed as Lanczos is known to have problems with rounding errors that lead to loss of orthogonality).
#TODO
Arnoldi (just like Lanczos) reduces to a smaller matrix that can be fed into simple methods to approximate the eigenpairs corresponding to the largest eigenvalues of
.
This smaller matrix, in the case of Arnoldi, is , a upper Hessenberg matrix:
where is actually the projection of
onto the Krylov subspace
.
is the n-order orthogonal Krylov basis used to map
to
.
With each iteration of Arnoldi, a new basis vector of the Krylov subspace orthogonalised wrt the other basis vectors is added to . Arnoldi can be restarted in the case the subspace being generated starts to become too large.
W. Ford. Numerical Linear Algebra with Applications. Academic Press, 2015
B.N. Parlett. The Symmetric Eigenvalue Problem. Classics in Applied Mathematics 20. SIAM, Philadelphia, 1998
Yousef Saad. Numerical Methods for Large Eigenvalue Problems. Manchester University Press, 1992.
D.V. Fedorov. Yet Another Introduction to Numerical Methods. https://phys.au.dk/~fedorov/Numeric/Book/book.pdf, 2013
* Not implemented
** Could potentially maybe possibly still need some fine tuning