2
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ 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? $\endgroup$ Jul 19, 2019 at 18:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – WhatsUp
    Jul 19, 2019 at 18:59
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 19, 2019 at 19:07
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 19, 2019 at 20:41
  • 1
    $\begingroup$ 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?' $\endgroup$
    – JCK
    Jul 19, 2019 at 22:27

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Grazie Federico! $\endgroup$ Jul 19, 2019 at 22:04
  • $\begingroup$ Prego! Note that this answer covers only a specific setting; I agree with the comments above that it might be useful to know more about the problem you're trying to solve, though. $\endgroup$ Jul 19, 2019 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.