Faster algorithms for the characteristic polynomial
Clément Pernet, Arne Storjohann · 2007
A new randomized algorithm is presented for computing the characteristic polynomial of an n x n matrix over a field. Over a suffciently large field the asymptotic expected complexity of the algorithm is O(nθ)field operations, improving by a factor of log n on the worst case complexity of Keller-Gehrig's algorithm [11].