Given $A \in \mathsf{M}_n(\mathbb{C})$ (no special structure) is it (generally) faster to compute its eigenvalues or the coefficients of its characteristic polynomial?
References/insights would be greatly appreciated as well.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityGiven $A \in \mathsf{M}_n(\mathbb{C})$ (no special structure) is it (generally) faster to compute its eigenvalues or the coefficients of its characteristic polynomial?
References/insights would be greatly appreciated as well.
With the traditional algorithms and complexity measures used in numerical linear algebra (dense real matrices, floating point computations, flop count as a complexity measure), they are both more or less equally fast, with the characteristic polynomial probably being slightly faster.
Eigenvalue computation requires an iteration so its time is not constant, but the traditional ballpark estimate is $10n^3$ if you want the eigenvalues only (no eigenvectors).
As far as I know, the best way to compute the characteristic polynomial numerically is performing a Hessenberg decomposition ($10/3n^3$), and then evaluating the polynomial $\det(H-\lambda I)$ on each of the $n$th roots of unity ($n^2$ each for a Hessenberg PLU decomposition, $n^3$ in total) and interpolating via an FFT (negligible time).
References for all these operation counts are Golub-Van Loan's Matrix Computations, or Appendix C in Higham's Functions of matrices just for the raw number.
A hint to the fact that they should be essentially equally fast is that both computing the characteristic polynomial and the eigenvalues are $O(n^3)$ operations (or $O(n^\omega)$, where $\omega$ is the matrix multiplication exponent, if you care about this sort of things), but if you know one of them you can get the other in sub-cubic time:
Computing eigenvalues via the characteristic polynomial is notoriously unstable, though, so this is a theoretical observation but I wouldn't recommend it in practice.