On the complexity of computing characteristic polynomials

Appears in collection : 2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Among the classical problems in computational linear algebra, the computation of the characteristic polynomial is of great relevance for applications as it reflects most invariants of the input matrix. It is a key component in the solution of many other related problems, such as computing eigenvalues, invariant factors and invariant subspace decomposition, testing matrices for similarity, Krylov methods etc. Computing characteristic polynomials efficiently is surprisingly challenging and has lead to a very diverse algorithmic landscape, as it lies in-between scalar linear algebra and modules of polynomial matrices. For instance, finding a deterministic reduction to dense matrix multiplication was an open-problem until recently. We will introduce some of these algorithmic techniques to present recent complexity improvements for the computation of characteristic polynomials: with dense matrices, first, we will present a recent work achieving the first reduction to matrix multiplication, based on polynomial matrix arithmetic. Then, in the context of matrices with a displacement rank structure, we will present algorithms, leading to the first sub-quadratic time cost.