Timeline for Is there a fast way to check if a matrix has any small eigenvalues?
Current License: CC BY-SA 4.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 6 at 17:31 | comment | added | Will Jagy | Suggest you also subscribe to their users mailing list \\\\\\\\\\\ Date: Fri, Jan 26, 2024 at 9:38 AM \\\\\\\\\\\\\\\\\\\\ Subject: subscribe \\\\\\\\\\\\\ To: <[email protected]> \\\\\\\\\\\\\\\\\\\\\\ Not sure how this works. \\\\\\\\\\\\\\\\\\\\\\\\\ Will Jagy \\\\\\\\\\\\\\\\\\\\\\ | |
| Feb 1 at 20:36 | comment | added | JCK |
How much faster do you need? I just did a quick test with numpy on a M2 macbook, calculating the eigenvalues of a 20x20 0/1 symmetric matrix and checking the minimum absolute value (np.min(np.abs(np.linalg.eigh(A)[0])) ) took 90us, and you can do 36 million of those per hour. I know that you want exact answers, but this uses syevd and that's should be good enough that you'll only have to double-check values very close to 1.
|
|
| Jan 27 at 13:56 | comment | added | Max Lonysa Muller | In case you're looking for ideas besides the ones provided in the answers below, you could consider also posting your question on Computational Science SE: scicomp.stackexchange.com | |
| Jan 26 at 19:02 | comment | added | Will Jagy | Got a reply from Pari-gp. Both the commands qfgaussred() and qfsign() run on rational numbers when given a square symmetric integer matrix. So, as in the idea of @BrendanMcKay, run qfsign() on $A, A+I, A-I,$ and compare | |
| Jan 26 at 7:54 | answer | added | Artemy | timeline score: 4 | |
| Jan 26 at 5:06 | comment | added | Brendan McKay | I have (undebugged) code about 100 times faster than Nathaniel reports for Matlab. | |
| Jan 25 at 22:34 | answer | added | Nick Alger | timeline score: 27 | |
| Jan 25 at 20:35 | answer | added | Joseph Van Name | timeline score: 2 | |
| Jan 25 at 19:42 | comment | added | Luis Ferroni | So, isn't the whole problem equivalent to deciding whether the matrix $A^2-I$ is positive semidefinite? | |
| Jan 25 at 19:00 | comment | added | Will Jagy | Also, this is called Gauss reduction in France although often called Lagrange reduction as in Gantmacher's books, pages 299-300 in volume one. fr.wikipedia.org/wiki/R%C3%A9duction_de_Gauss# | |
| Jan 25 at 18:19 | comment | added | Will Jagy | see mathoverflow.net/questions/268334/signature-of-a-quadratic-form That is, I think the command qfgaussred() is what you want if you are working in pari-gp | |
| Jan 24 at 19:56 | answer | added | Will Jagy | timeline score: 3 | |
| Jan 24 at 18:09 | comment | added | Nathaniel Johnston | The off-the-shelf eigenvalue computations that MATLAB uses can solve this problem (i.e., computing the minimal eigenvalue to, say, 8 decimal places) for 100 million $30 \times 30$ symmetric $\{0,1\}$ matrices in about 2 hours. If you want an exact answer you will need to use the characteristic polynomial when there is an eigenvalue really close to $1$, but can you use these numerical methods to rule out all matrices with an eigenvalue below, say, $0.999$? | |
| Jan 24 at 17:27 | answer | added | Denis Serre | timeline score: 10 | |
| Jan 24 at 16:42 | answer | added | ors | timeline score: 2 | |
| Jan 24 at 14:19 | history | became hot network question | |||
| Jan 24 at 12:11 | comment | added | Bill Bradley | Compared to the time for computing, say, the determinant, how long would it take to compute the matrix inverse? If that were available cheaply you could, for instance, use the inverse power method. | |
| Jan 24 at 10:47 | answer | added | Liviu Nicolaescu | timeline score: 14 | |
| Jan 24 at 8:09 | comment | added | Brendan McKay | If $|A|\ne 0$ and either $|A+I|$ or $|A-I|$ has different sign from $|A|$, then there is a small eigenvalue. | |
| Jan 24 at 8:00 | answer | added | Federico Poloni | timeline score: 20 | |
| Jan 24 at 7:39 | comment | added | Gordon Royle | @FedericoPoloni They are symmetric matrices, so the unit disc is the unit interval so with a bit of pre-processing to eliminate repeated roots and roots at $\pm 1$ Sturm sequences can be used. | |
| Jan 24 at 7:35 | comment | added | Federico Poloni | @GordonRoyle How do you test if a polynomial has no roots inside the unit disc without computing the roots? Schur/Hurwitz stability criteria? | |
| Jan 24 at 7:34 | comment | added | Gordon Royle | @FedericoPoloni My current slow method (via characteristic polynomials) uses exact arithmetic only and does not compute any eigenvalues, but I would experiment with a heuristic involving floating point arithmetic if necessary. | |
| Jan 24 at 6:33 | comment | added | Gordon Royle | @CarloBeenakker Since the matrices are all 0/1-matrices, the condition number never tells me much. | |
| Jan 24 at 6:27 | comment | added | Carlo Beenakker | You could use the condition number, computed as the ratio of the largest diagonal element and the smallest diagonal element. | |
| Jan 24 at 6:18 | history | asked | Gordon Royle | CC BY-SA 4.0 |