Timeline for What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix?
Current License: CC BY-SA 2.5
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 26, 2012 at 13:38 | answer | added | David E Speyer | timeline score: 1 | |
| Jun 26, 2012 at 10:40 | answer | added | mkatkov | timeline score: 2 | |
| Oct 2, 2010 at 12:11 | answer | added | Bill Bradley | timeline score: 7 | |
| Oct 1, 2010 at 12:28 | comment | added | Federico Poloni | You may also rely on an algorithm of this kind: reduce to integer coefficients; then compute the determinant $\mod p$ for several values of $p$, and check if it is zero. If you are fine with a probabilistic result, check just a few primes. If you want to be 100% sure of your computation, I am afraid you will need exponentially many primes (or exponentially large primes, which is the same). | |
| Oct 1, 2010 at 12:24 | comment | added | Federico Poloni | for (ii), you just have to compute the determinant and check if it is zero. The traditional bound is $2/3n^3$ operations, but much depends on what is an "operation" if you are dealing with rational numbers. You may want to compute everything exactly, and in this case you need to operate with very large integers, or rely on an approximation. In the former case, the time is probably going to be exponential, since the worst-case bounds on the coefficient growth in Gaussian elimination are exponential. In the latter, it's just $2/3n^3 \log \epsilon$, with $\epsilon$ the desired precision. | |
| Oct 1, 2010 at 11:15 | answer | added | Denis Serre | timeline score: 4 | |
| Jul 27, 2010 at 9:30 | answer | added | J. M. isn't a mathematician | timeline score: 2 | |
| May 15, 2010 at 2:02 | answer | added | Deane Yang | timeline score: 3 | |
| May 14, 2010 at 21:34 | answer | added | Michael Hoffman | timeline score: 2 | |
| May 11, 2010 at 21:41 | answer | added | Ed Gorcenski | timeline score: 2 | |
| May 11, 2010 at 21:12 | answer | added | Ryan Williams | timeline score: 20 | |
| May 11, 2010 at 20:22 | comment | added | alex | To make things my inquiry more specific, suppose the matrix is $n \times n$ and entries are rational numbers, taking $K$ bits to specify the numerator and denominator. How many operations do you need to give me: (i) the first $m$ bits of the smallest eigenvalue (ii) whether the smallest eigenvalue equals zero or not. | |
| May 11, 2010 at 20:20 | comment | added | alex | I'm would also be very interested to hear an answer to this question, if "best" is interpreted as "best in terms of theoretical guarantees" and not "best in practice." | |
| May 11, 2010 at 20:13 | history | asked | Philipp | CC BY-SA 2.5 |