Is it faster to compute eigenvalues or coefficients of characteristic polynomials?

Question

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.

Answer 1

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:

• if you know the eigenvalues you can compute the characteristic polynomial in $O(n^2)$ or maybe even $O(n \log^{something} n)$ time: multiply the monomials $\lambda-\lambda_i$ one with each other, two by two, then four by four etc., in a binary tree fashion, using FFT;
• if you have the coefficients of the characteristic polynomial you can compute its roots in $O(n^2)$ (see e.g. https://arxiv.org/abs/1611.02435).

Computing eigenvalues via the characteristic polynomial is notoriously unstable, though, so this is a theoretical observation but I wouldn't recommend it in practice.