Best method to calculate the characteristic polynomial
Is there a "gold" standard for computing the characteristic polynomial of a given $n \times n$ matrix in finite precision arithmetic on a computer?
There are fast methods running in $O(n^3)$ or even $O(n^\omega)$ :
An $O(n^3)$ algorithm for the Frobenius normal form by Storjohann
Nearly optimal algorithms for canonical matrix forms by Giesbrecht
Fast algorithms for the characteristics polynomial by Keller-Gehrig
These algorithms are quite fast but were developed for finite fields and require randomness and matrix inversion, which in finite precision arithmetic can cause numerical problems.
On the other hand there is the Faddeev-Leverrier algorithm which only requires matrix multiplication but runs in time $O(n^4)$.
Does anyone have experience using these algorithms for numerical calculations?
$\endgroup$ 2 Reset to default
