Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

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

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, 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.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-unilim.archives-ouvertes.fr/hal-02963147
Contributeur : Vincent Neiger <>
Soumis le : vendredi 9 avril 2021 - 18:03:39
Dernière modification le : mardi 21 septembre 2021 - 16:40:38

Fichier

charpoly.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Vincent Neiger, Clément Pernet. Deterministic computation of the characteristic polynomial in the time of matrix multiplication. Journal of Complexity, Elsevier, 2021, 67, ⟨10.1016/j.jco.2021.101572⟩. ⟨hal-02963147v2⟩

Partager

Métriques

Consultations de la notice

68

Téléchargements de fichiers

85