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{\langle{\bf v}_1,{\bf x}_{n+1}\rangle}{\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^\top $$
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.
wasWell the answer to the above question is yes. The trouble I was having is due to a coding bug. I tried the methodology on a 45000 x 45000 sparse matrix having about 11% non zero elements. The first eigenvalue coincided exactly whit the values given by eigs() from matlab when printed in double precision. The second eigenvalue coincided up to 9 digits after the decimal point. So it looks that although my matrix is not symmetric and positive definite, the above algorithm somehow worked.
If you hove other ideas, write me a comment.