Deterministic computation of the characteristic polynomial in the time of matrix multiplication |
| |
| Institution: | 1. Univ. Limoges, CNRS, XLIM, UMR 7252, F-87000 Limoges, France;2. Université Grenoble Alpes, Laboratoire Jean Kuntzmann, CNRS, UMR 5224, 700 avenue centrale, IMAG - CS 40700, 38058 Grenoble cedex 9, France;1. University of South Carolina, United States of America;2. Steklov Institute of Mathematics, Russia;3. Lomonosov Moscow State University, Russia;4. Moscow Center for Fundamental and Applied Mathematics, Russia;5. Faculty of Mathematics, 09107 Chemnitz, Germany;1. Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenbergerstr. 69, 4040 Linz, Austria;2. Institut für Finanzmathematik und Angewandte Zahlentheorie, Johannes Kepler Universität Linz, Altenbergerstr. 69, 4040 Linz, Austria |
| |
| Abstract: | 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. |
| |
| Keywords: | Characteristic polynomial Polynomial matrices Determinant Fast linear algebra |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
