2020/10/09 by Vincent Neiger, Neiger, Vincent, Clément Pernet +1 · 2 citations
Computer Science · #Cellular Automata and Applications #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Matrix Theory and Algorithms #Symbolic Computation (cs.SC) #cs.CC #cs.SC
paper · pdf · doi:10.48550/arxiv.2010.04662
38 pages, 5 algorithms
openalex publication_date 2020/10/09 · arxiv created 2021/04/09 · arxiv updated 2021/04/12 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
This paper describes an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. Our algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form, and relies on new subroutines for transforming shifted reduced matrices into shifted weak Popov matrices, and shifted weak Popov matrices into shifted Popov matrices.