Timeline for Is it faster to compute eigenvalues or coefficients of characteristic polynomials?
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 19, 2019 at 22:27 | comment | added | JCK | This seems to me to be one of the questions for which the proper response is more along the lines of: 'wait, what exactly is the problem you're trying to solve?' | |
| Jul 19, 2019 at 21:47 | answer | added | Federico Poloni | timeline score: 7 | |
| Jul 19, 2019 at 20:55 | comment | added | Dima Pasechnik | methods that update $A$ (e.g. Gaussian elimination) or do matrix-matrix operations stop working pretty quickly as $n$ grows. That's why Krylov subspaces and all this not so easy machinery of numerical linear algebra was invented. | |
| Jul 19, 2019 at 20:41 | comment | added | Timothy Chow | As Dima Pasechnik has explained, you'll probably need to say a little more to get a useful answer. For example, do you need to compute all the eigenvalues/coefficients? To what level of precision? When you use the word "generally" you must be implicitly thinking of a probability distribution on matrices. Are the matrices ill-conditioned? If you have to compute all the eigenvalues of an ill-conditioned matrix to high precision then that can be much worse than computing the coefficients, but approximate computation of the eigenvalues is tractable for well-conditioned matrices. | |
| Jul 19, 2019 at 20:28 | comment | added | user6976 | One can use Gaussian elimination of the $\lambda$-matrix $A-\lambda I$. | |
| Jul 19, 2019 at 20:23 | comment | added | Dima Pasechnik | talking about inexact computations, the errors one accumulates from computing $A^{1000}$, say, would lead nowhere. Cf e.g. Numerical Computation of the Characteristic Polynomial of a Complex Matrix | |
| Jul 19, 2019 at 20:02 | comment | added | Geoff Robinson | @FedericoPoloni : OK, I spoke too quickly, you do have to worry about permutation of the rows. | |
| Jul 19, 2019 at 19:46 | comment | added | David Handelman | I have no idea whether this is more or less efficient; but to compute the characteristic polynomial, it is enough to compute ${\rm tr} A^k$ for all $k = 1,2, \dots, n$; then Newton's identities give you the coefficients of the characteristic polynomial. | |
| Jul 19, 2019 at 19:07 | comment | added | Dima Pasechnik | The story is that there are very efficient iterative methods to compute "some" eigenvalues, e.g. largest in magnitute. Computing all eigenvalues to acceptable precision is very hard as soon as your matrices are big. The same applied to the characteistic polynomial, in fact. | |
| Jul 19, 2019 at 19:02 | history | edited | j.c. | CC BY-SA 4.0 |
complete title
|
| Jul 19, 2019 at 18:59 | comment | added | WhatsUp | Computing characteristic polynomial will be polynomial complexity, while computing eigenvalues will inavoidably factorize the polynomial, which in general is much slower. Reference: search wiki for Eigenvalue algorithm. | |
| Jul 19, 2019 at 18:56 | history | edited | Pietro Paparella |
edited tags
|
|
| Jul 19, 2019 at 18:55 | comment | added | Pietro Paparella | @DimaPasechnik: inexact. Not fluent enough in numerical analysis to understate what you’re asking in your second question. | |
| Jul 19, 2019 at 18:43 | comment | added | Dima Pasechnik | Are you talking about exact computation, or inexact? And if inexact, then in what model? The "standard" floating point complex numbers? A special library? A GPU? | |
| Jul 19, 2019 at 18:29 | history | asked | Pietro Paparella | CC BY-SA 4.0 |