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.
De Joachim von zur Gathen
De Sébastien Tavenas
De Pranjal Dutta
De Nitin Saxena
De Clément Pernet
De Fredrik Johansson
De Lihong Zhi
De Annie Cuyt
De Juan Camilo Arosemena Serrato
De Giuseppe Savaré
De Juan Camilo Arosemena Serrato
De Amine Marrakchi
De Francesca Arici
De Shirly Geffen
