What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T11:29:39Z http://mathoverflow.net/feeds/question/24287 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix? Philipp 2010-05-11T20:13:48Z 2012-06-26T13:49:35Z <p>see title. </p> <p>An algorithm is 'good' if it is able to distinguish between zero Eigenvalues and nonzero Eigenvalues.</p> http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/24294#24294 Answer by Ryan Williams for What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix? Ryan Williams 2010-05-11T21:12:33Z 2010-05-11T21:29:07Z <p>One method is to reduce the computation to that of computing matrix multiplication of $n \times n$ matrices. In particular, the determinant of a symbolic matrix can be computed in $O(n^{\omega})$ arithmetic operations, where $\omega &lt; 2.376$ is the matrix multiplication exponent, and from a symbolic determinant of course one can recover all eigenvalues. However, since the operations here will be over polynomials of degree $n$ with coefficients in $m$ bits, this method would take about $O(n^{1+\omega} m)$ time to get $m$ bits of the eigenvalues.</p> <p>More complex methods can get you the eigenvalues in $O(n^3 + n^2 \log^2 n \log b)$ time, where the eigenvalues are approximated to within $2^{-b}$. For some structured matrices you can get about $O(n^{\omega})$. See</p> <blockquote> <p>Victor Y. Pan, Zhao Q. Chen: The Complexity of the Matrix Eigenproblem. STOC 1999: 507-516</p> </blockquote> <p>(Actually it appears this paper never appeared in a journal form, so study it very carefully if you are serious about this problem.)</p> <p>I don't see a simple way to exploit the fact that (a) it is symmetric and (b) you just want to find the smallest nonzero eigenvalue. It seems doubtful to me that you could do this much faster than $O(n^{\omega})$ (without finding <em>all</em> nonzero eigenvalues faster than this), but this is just based on intuition, not fact.</p> http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/24297#24297 Answer by Ed Gorcenski for What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix? Ed Gorcenski 2010-05-11T21:41:22Z 2010-05-11T21:41:22Z <p>A quick search led me to this paper, which deals specifically with sparse symmetric matrices, although some of its references might be useful.</p> <blockquote> <p>Jang, Ho-Jong, and Lee, Sung-Ho, "NUMERICAL STABILITY OF UPDATE METHOD FOR SYMMETRIC EIGENVALUE PROBLEM," J. Appl. Math. &amp; Computing Vol. 22(2006), No. 1 - 2, pp. 467 - 474.</p> </blockquote> <p>A PDF copy is available here: <a href="http://www.mathnet.or.kr/mathnet/kms_tex/986075.pdf" rel="nofollow">http://www.mathnet.or.kr/mathnet/kms_tex/986075.pdf</a></p> <p>I should also mention that "best" is a difficult superlative to qualify without knowing the structure of your matrices. Probably the best algorithm for a sparse symmetric matrix is not the best algorithm for a symmetric Toeplitz matrix.</p> http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/24666#24666 Answer by Michael Hoffman for What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix? Michael Hoffman 2010-05-14T21:34:33Z 2010-05-14T21:34:33Z <p>This is the method they use with LaPACK, which is usually the fastest for general problems (fastest noncommercial anyway)</p> <p><a href="http://www.netlib.org/lapack/lug/node48.html" rel="nofollow">http://www.netlib.org/lapack/lug/node48.html</a></p> <p>and here's a discussion regarding this computation</p> <p><a href="http://www.netlib.org/lapack/lug/node30.html#subsecdriveeigSEP" rel="nofollow">http://www.netlib.org/lapack/lug/node30.html#subsecdriveeigSEP</a></p> <p>I honestly am not sure if you can hunt down the smallest eigenvalue without finding all of them.</p> <p>However, I would not under any circumstances do the symbolic determinant. So far as I know if you're doing a numerical calculation, an introduction of symbols will give you a major slowdown. I don't have the time at the moment to look up the exact computation, but I think that outside of quantum computing symbolic factorization is NP-hard/NP-complete. In the multivariate case (using Groebner Bases) it's doubly exponential.</p> http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/24682#24682 Answer by Deane Yang for What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix? Deane Yang 2010-05-15T02:02:14Z 2010-05-15T02:02:14Z <p>First, a disclaimer: I know absolutely nothing about numerical algorithms for finding the eigenvalue of a matrix, symmetric or not. So my feelings will not be hurt if my answer gets downvoted into oblivion.</p> <p>It seems to me that an obvious but perhaps overly naive approach is the following:</p> <p>Let $A$ be the symmetric matrix in question.</p> <p>a) Use some standard minimization algorithm (maybe the conjugate gradient method?) to minimize</p> <p>$$\frac{x\cdot Ax}{x\cdot x}$$ </p> <p>over nonzero $x$ (an obvious thing to do is to restrict to $|x| = 1$ but you might save some arithmetic if you don't bother with this normalization).</p> <p>b) See what eigenvalue you get. If it's the eigenvalue you want, then you're done. If not, save the eigenvector you found and proceed to c)</p> <p>c) Repeat a), except restrict to the subspace orthogonal to all of the eigenvectors you've found so far. See what eigenvalue you get. If it's the one you want, you're done. Otherwise, save the eigenvector and repeat this step again.</p> <p>Eventually, you'll have all of the eigenvalues and eigenvectors. Depending on what "smallest" means, you may or may not be able to stop before you have found all of the eigenvectors. Actually, if "smallest" means "eigenvalue with the smallest nonzero absolute value", then just do the steps above with $A^2$ instead of $A$.</p> <p>For small matrices this seems like a practical approach to me. But, as I said, I don't know anything about this stuff.</p> http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/33487#33487 Answer by J. M. for What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix? J. M. 2010-07-27T09:30:00Z 2010-07-27T09:30:00Z <p>Probably still your best bet, after of course reducing your original symmetric matrix to tridiagonal form, would be either bisection (with the help of Gerschgorin bounds) or an appropriate modification of the dqd/MRRR algorithm of Parlett, Fernando, and Dhillon.</p> <p>If your matrix has additional structure apart from symmetry (e.g. it is a Toeplitz or arrowhead matrix), there of course may be even more slick apporaches. I suggest looking at the references given in LAPACK and other numerical linear algebra books.</p> http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/40737#40737 Answer by Denis Serre for What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix? Denis Serre 2010-10-01T11:15:25Z 2010-10-01T11:15:25Z <p>The QR algorithm gives quite rapidly a good approximation of the eigenvalues of a real symmetric (or complexHermitian). But overall, it gives first the smallest eigenvalues. The reason is that the ratio $\lambda_{n-1}/\lambda_n$ is the convergence rate.</p> http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/40829#40829 Answer by Bill Bradley for What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix? Bill Bradley 2010-10-02T12:11:56Z 2010-10-02T12:11:56Z <p>Tao and Vu (1) have shown that the distribution of the smallest singular value of a random matrix is "universal", i.e. independent of the particular random variable populating the matrix. They are interested in analyzing distributions, not particular matrices, but it appears that it might be possible to use their machinery for addressing this problem.</p> <p>First, several caveats.<br> 1. Their analysis assumes there are no zero eigenvalues. With random matrices, this isn't much of a restriction, but it might be for your application. If there were at most a small number of zero eigenvalues, one could pick them off somewhat efficiently and then reduce to the invertible case. 2. The results hold with high probability, not certainty. 3. The results recover estimates of eigenvalues, not the exact values, although they can be made arbitrarily accurate. 4. Tao and Vu's analysis is not aimed at this particular application, so there very well may be some issue translating them to this domain.</p> <p>Now that the pussy-footing is out of the way, the basic idea is as follows: We wish to find the smallest eigenvalue $\lambda_n$ of a matrix $A$. Suppose that $A$ is invertible. Then the <strong>largest</strong> eigenvalue of $A^{-1}$ is $1/\lambda_n$. Since finding the largest eigenvalue is a much easier problem (by, e.g. the power method), we might be in a better position.</p> <p>But computing $A^{-1}$ is (generically) as difficult as computing all the eigenvalues! Tao and Vu dodge this problem by taking random subsets of the columns of $A$ and considering the orthogonal complement; this is inspired by "property testing" arguments in complexity theory. Then with high probability one can estimate the largest eigenvalue of $A^{-1}$ from these restrictions, and we are done.</p> <p>(1) Terence Tao and Van Vu. "Random matrices: the distribution of the smallest singular values". March, 2009. <a href="http://arxiv.org/abs/0903.0614v1" rel="nofollow">http://arxiv.org/abs/0903.0614v1</a></p> http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/100671#100671 Answer by mkatkov for What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix? mkatkov 2012-06-26T10:40:42Z 2012-06-26T10:40:42Z <p>If smallest means closest to zero, than Rayleigh quotient iterations gives cubic convergence, but still requires matrix inverse, or actually to solve the system of linear equations.</p> <p><a href="http://en.wikipedia.org/wiki/Rayleigh_quotient_iteration" rel="nofollow">http://en.wikipedia.org/wiki/Rayleigh_quotient_iteration</a></p> <p>see also <a href="http://en.wikipedia.org/wiki/Inverse_iteration" rel="nofollow">http://en.wikipedia.org/wiki/Inverse_iteration</a></p> http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/100686#100686 Answer by David Speyer for What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix? David Speyer 2012-06-26T13:38:52Z 2012-06-26T13:49:35Z <p>Here is a simple idea, with no complexity analysis. Compute a basis $v_1$, ..., $v_{n-r}$ for the kernel of $A$; this can be done with exact arithmetic in $n^3$ operations by Gaussian elimination. Compute a basis $w_1$, ..., $w_{r}$ for the othogonal complement: Again, doable in exact arithmetic with $n^3$ operations. $\mathrm{Span}(w_1, ..., w_r)$ is the orthogonal complement to the $0$-eigenspace of $A$ and hence, since $A$ is symmetric, it is the span of the nonzero eigenspaces of $A$. So $A$ maps $\mathrm{Span}(w_1, \ldots, w_r)$ to itself. Let $X$ be the $r \times r$ matrix of this map. This is again a matrix of rational numbers, computable with exact arithmetic in reasonable time, whose eigenvalues are the same as the nonzero eigenvalues of $A$. Note, however, that $X$ is not symmetric.</p> <p>Invert $X$ and find its largest eigenvalue by one of the standard methods.</p> <p>What I am gambling here is that the advantages of working in exact arithmetic are greater than the disadvantages of passing to a nonsymmetric matrix.</p>