I have a huge matrix (1000,000 x 1000,000) and I am trying to find the first twenty something eigenvectors of this problem. Is there a way to maybe break this huge matrix into many smaller ones to speed up the process.
I have tried the Lanczos method in python (scipy), but it is still computationally very expensive. At the moment I am not even able to load the huge matrix into memory, let alone compute anything.
I have checked the matrix, and it is not sparse.
On
I am not an expert in this field, but since your matrix is given as $B=AA^\top$ by a smaller $1000,000\times 100$-matrix $B$, we already know that all the eigenvalues are real and non-negative. We know this because $B$ is symmetric and positive semi-definite. Maybe you can use this knowledge to find optimized algorithms.
Some algorithms for finding some eigenvalues of large matrices (e.g. in ARPACK) only require you to perform matrix vector multiplication as a black box operation. This means, they hand you a vector $v$ and require you to return $Bv$ $-$ and they do not care how you did it. Since your matrix is given by $AA^\top$, it is not necessary to load all of $B$, but it suffices to load $A$. You then compute $v\mapsto A^\top v\mapsto AA^\top v=Bv$.
Another idea is to compute the singular values of $A$ instead. The eigenvalues of $B$ are then the square of these singular values.
Too long for a comment
pythonis probably not the best way to go. Even loading the whole matrix in memory is probably not possible at all in your case.Most numerical methods rely on multiplication of the matrix times an input vector, so instead of generating the matrix and then multiplying it times a given vector you can create the matrix elements on-the-fly
I've used
scalapackin the past and it is very powerfullhttp://www.netlib.org/scalapack/
But it does requiere to know
C/Fortran. However, if you really are out of your confort zone with this languages you can always write a wraper forpython