Deterministic computation of the characteristic polynomial in the time of matrix multiplication

DOI10.1016/j.jco.2021.101572zbMath1482.65072arXiv2010.04662OpenAlexW3154023210WikidataQ114163593 ScholiaQ114163593MaRDI QIDQ2238844

Vincent Neiger, Clément Pernet

Publication date: 2 November 2021

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.04662

zbMATH Keywords

polynomial matricescharacteristic polynomialdeterminantfast linear algebra

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical computation of determinants (65F40) Numerical computation of matrix exponential and similar matrix functions (65F60)

Related Items (2)

Efficient sampling in spectrahedra and volume approximation ⋮ Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x\)]
• Efficient algorithms for order basis computation
• A general module theoretic framework for vector M-Padé and matrix rational interpolation
• On computing the determinant in small parallel time using a small number of processors
• Fast algorithms for the characteristic polynomial
• Fast projection methods for minimal design problems in linear system theory
• The complexity of partial derivatives
• On fast multiplication of polynomials over arbitrary algebras
• Linear multivariable systems
• On lattice reduction for polynomial matrices
• On the complexity of computing determinants
• High-order lifting and integrality certification
• Fast computation of approximant bases in canonical form
• Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix
• Normal forms for general polynomial matrices
• Gaussian elimination is not optimal
• Fast computation of the rank profile matrix and the generalized Bruhat decomposition
• Computing minimal interpolation bases
• Bruhat canonical form for linear systems
• Modern Computer Algebra
• Efficient computation of order bases
• Computing column bases of polynomial matrices
• Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts
• Faster Polynomial Multiplication over Finite Fields
• Minimal Bases of Rational Vector Spaces, with Applications to Multivariable Linear Systems
• Powers of tensors and fast matrix multiplication
• Unimodular completion of polynomial matrices
• A generalization of the fast LUP matrix decomposition algorithm and applications
• Fast Parallel Matrix Inversion Algorithms
• A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Nearly Optimal Algorithms for Canonical Matrix Forms
• Computing Canonical Bases of Modules of Univariate Relations
• Certification of Minimal Approximant Bases
• Computing Popov and Hermite Forms of Rectangular Polynomial Matrices
• Computing minimal nullspace bases
• Normalization of row reduced matrices
• Efficient computation of the characteristic polynomial
• Invariant Description of Linear, Time-Invariant Controllable Systems
• A Method of Determining Explicitly the Coefficients of the Characteristic Equation
• Efficient algorithms for computing the characteristic polynomial in a domain

This page was built for publication: Deterministic computation of the characteristic polynomial in the time of matrix multiplication