I am trying to compute the eigenvalues of a large sparse matrix (about 10% of the values are nonzero). The matrix is real valued, but since it is accumulated by a stochastic process it is not fully symmetric. I have used power iteration to compute the largest eigenvalue and the method worked fine. Unfortunately if I would apply the standard methods of deflation to compute the other eigenvalues I will spoil the sparsity.
I tried exploiting the fact that the eigenvectors of a real symmetric matrix form a basis. In this basis every vector can be expressed as
${\bf x} = a_1{\bf v}_1+a_2{\bf v}_2 + \dots + a_n{\bf v}_n$
One can eliminate the eigenvalues one by one by subtracting the component along the corresponding eigenvector.
$ {\bf x}_{n+1} = {\bf A }{\bf x}_{n} $
$ {\bf x}_{n+1} = {\bf x}_{n+1} - a_1{\bf v}_1 $
Where $a_1 = \frac{<{\bf v}_1,{\bf x}_{n+1}>}{\lVert {\bf x}_{n+1} \rVert}$, and ${\bf v}_1$ is the eigenvector corresponding to the largest eigenvalue as computed by the power iteration method.
The problem is that my matrix is not really symmetric. Therefore, I presume that my strategy is wrong. In the case of an asymmetric matrix, the eigenvalues can be complex, and some of the eigenvalues might have multiplicity bigger than one.
I looked at other possibilities, for instance
${\bf A } - {\bf x}_1{\bf u}_1^T $
Where different choices of ${\bf u}_1$ can be made e.g. left eigenvector of ${\bf A }$ or ${\bf u}_1=\lambda_1{\bf x}_1$ etc.. Unfortunately the resulting matrix is no longer sparse.
I will appreciate ideas how to apply the deflation algorithm to the spectrum of the problem outlined above.
Thank you in advance,
Alex
