I am doing research on eigen decomposition these days.
I know that for small 2x2 or 3x3 matrix, we can solve the characteristic polynomial to get the eigen values and then compute the corresponding eigen vectors
However, I cannot figure out how is eigen-decomposition done in realy world problem, say 300x300 matrix
According to wiki page, there is 'power iteration' algorithm, but I doubt this is what happens under the hood in R and python/sklearn
Can anyone share some insight here?
Thanks
First, notice that for general matrices of size $ 5 \times 5 $ or larger, it can be proven that there is no algorithm (formula) that in a finite number of steps computes the eigenvalues of a matrix. This is due to the fact that for arbitrary polynomials of degree five or greater, there is no formula for computing the roots and for every polynomial, there is a way to construct a matrix that has that polynomial as its characteristic polynomial.
So, there is no formula for finding the eigenvalues in this case, and hence there is no formula for finding the eigenvectors. (If you can compute an eigenvector, then you can compute the corresponding eigenvalue with the formula $ x^T A x / x^T x $.
Now, under mild conditions, you can use the power method to approximately compute the eigenvector associated with the largest eigenvalue, and then you can use that to compute further eigenvectors and eigenvalues (approximately).
Now, there are algorithms, like the QR algorithm, that then extend the power method to compute all eigenvalues and eigenvectors of a matrix, and there are other methods (Arnoldi methods, for example) that are also based on the power method that compute some of the eigenvectors and corresponding eigenvalues (again, approximately).
A number of such algorithms (for dense matrices) are incorporated in packages like LAPACK, and the assumption that R and Python then call that package is almost certainly correct.
There are a number of videos that discuss the Power Method on YouTube. Here is one that may help you visualize what happens: https://www.youtube.com/watch?v=OzeDqsVoTFc&t=606s