2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Collection 2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Organizer(s) van der Hoeven, Joris ; Giesbrecht, Mark ; Koiran, Pascal ; Villard, Gilles
Date(s) 25/09/2023 - 29/09/2023
linked URL https://indico.math.cnrs.fr/event/8113/
13 17

On the complexity of computing characteristic polynomials

By Clément Pernet

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.

Information about the video

Citation data

  • DOI 10.57987/IHP.2023.T3.WS1.014
  • Cite this video Pernet, Clément (28/09/2023). On the complexity of computing characteristic polynomials. IHP. Audiovisual resource. DOI: 10.57987/IHP.2023.T3.WS1.014
  • URL https://dx.doi.org/10.57987/IHP.2023.T3.WS1.014

Bibliography

  • P. Karpman, C. Pernet, H. Signargout, and G. Villard : Computing the Characteristic Polynomial of Generic Toeplitz-like and Hankel-like Matrices / In Proc. ISSAC '21. ACM, 249–256. doi:10.1145/3452143.3465542
  • V. Neiger, C. Pernet : Deterministic computation of the characteristic polynomial in the time of matrix multiplication / Journal of Complexity (67), 2021. doi:10.1016/j.jco.2021.101572

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback