Symbolic Computation Group

Since the introduction of sub-cubic matrix multiplication algorithms, block algorithms have been designed to reduce the complexity of most classical problems in linear algebra to that of the matrix multiplication: O(n^omega).However the best known algorithm for the computation of the characteristic polynomial, by Keller-Gehrig, still involves a logarithmic number of matrix multiplications resulting in O(n^omega log n) field operations. Keller-Gehrig also proposed a O(n^omega) algorithm, but this was only valid with generic matrices.

We will present a new randomized algorithm computing the characteristic polynomial of any matrix over a field. If the field has at least 2n^2 elements, then this Las Vegas algorithm has expected cost in O(n^omega), matching the lower bound for this problem.

Asymptotically fast linear algebra used to be often considered as not practically efficient. But the development of efficient kernels for matrix multiplication (combining both cache optimizations and subcubic matrix multiplication) have raised the interest of these reductions to matrix multiplication for efficienct algorithms in practice.

Therefore the new algorithm is also of high interest for practical implementation. After some improvements of the preconditioning phase, the new algorithm actually outperforms the most efficient previous implementations.