Deterministic computation of the characteristic polynomial in the time of matrix multiplication - Archive ouverte HAL Accéder directement au contenu
Pré-Publication, Document De Travail Année :

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

(1) , (2)
1
2

Résumé

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, to our knowledge, 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.
Fichier principal
Vignette du fichier
charpoly.pdf (320.52 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02963147 , version 1 (09-10-2020)
hal-02963147 , version 2 (09-04-2021)

Identifiants

  • HAL Id : hal-02963147 , version 1

Citer

Vincent Neiger, Clément Pernet. Deterministic computation of the characteristic polynomial in the time of matrix multiplication. 2020. ⟨hal-02963147v1⟩
198 Consultations
210 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More