# Is it possible to use the deflation algorithm to compute the eigenvalues of a large sparse matrix?

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.

Alex

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.