Eigendecomposition
For a given square matrix \(A\), eigendecomposition means finding of set of vectors \(v\) such that
\(A v=\lambda v\)
Then, \(v\) is called eigenvector, and \(\lambda\) is corresponding eigenvalue.
If \(\lambda =1\), then the eigenvector has sense of fixed point of matrix \(A\).
It seems, up to year 2014, in the internet, there is no general routine in C++ available to calculate eigenvectors \(v\) and eigenvalues \(\lambda\) of a general matrix \(A\). Following the goal of TORI, such a routine should be implemented and uploaded, because the eigendecomposition is important tool for any serious research (including the "outstanding research"). While, the available links on the topic are collected here.
Not all matrices allow the eigendecomposition. The finite algorithm of finding eigenvectors for a general matrix is declared to be impossible [1].
Therefore, the general algorithm should be iterative; the goal of the efficient implementation is to realise the algorithm that converges quickly, providing the required precision within some reasonable number of arithmetic operations.
Naive iteration
The primitive iteration, called also power iteration http://en.wikipedia.org/wiki/Power_iteration refers to the sequence
\( \displaystyle b_{k+1}= \frac{A b_k}{||A b_k||}\)
where \(b_0\) is some vector that is expected to be an initial approximation of the eigenvector with biggest value of \(|\lambda|\). Sequence \(b\) has no need to converge. However, the sequence
\(\displaystyle \mu_k= \frac{b_k^{\dagger}A b_k}{ b_k^\dagger b_k} \)
is believed to converge to \(\lambda\) with biggest amplitude. This eigenvalue is called "dominant eigenvalue", and corresponding eigenvector is called "dominant eigenvector".
Once the dominant eigenvector \(v\) is evaluated, there is seduction to consider matrix \(A\) as an operator on subspace of vectors that are orthogonal to \(v\). However, this algorithm is not straightforward because in the general case, the set of eigenvectors has no need to be orthogonal.
References
- ↑ http://en.wikipedia.org/wiki/Eigenvalue_algorithm .. Any monic polynomial is the characteristic polynomial of its companion matrix. Therefore a general algorithm for finding eigenvalues could also be used to find the roots of polynomials. The Abel-Ruffini theorem shows that any such algorithm for dimensions greater than 4 must either be infinite, or involve functions of greater complexity than elementary arithmetic operations and fractional powers. For this reason algorithms that exactly calculate eigenvalues in a finite number of steps only exist for a few special classes of matrices. For general matrices, algorithms are iterative, producing better approximate solutions with each iteration. ..
http://en.wikipedia.org/wiki/Eigendecomposition_of_a_matrix
http://ftp.utdallas.edu/~herve/Abdi-EVD2007-pretty.pdf Hervé Abdi. The Eigen-Decomposition: Eigenvalues and Eigenvectors. (2007)
http://www.onmyphd.com/?p=eigen.decomposition How to compute eigendecomposition? .. Calculating the characteristic polinomial and then solving it with the respect to the eigenvalues becomes impractical as the size of the matrix increases. In practice, iterative algorithms are used to eigendecompose a matrix.
http://www.feynarts.de/diag/ Thomas Hahn. Routines for the diagonalization of complex matrices. 9 Aug 11 . (2011 ?) ( Both in Fortran and C-- )
Keywords
Characteristic polynomial, Eigenvalue, Eigenvector, Fixed point, Linear algebra,