Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

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 :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [72 références]  Voir  Masquer  Télécharger

https://hal-unilim.archives-ouvertes.fr/hal-02963147
Contributeur : Vincent Neiger <>
Soumis le : vendredi 9 octobre 2020 - 17:59:45
Dernière modification le : jeudi 15 octobre 2020 - 14:09:11

Fichier

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

Identifiants

  • HAL Id : hal-02963147, version 1

Collections

Citation

Vincent Neiger, Clément Pernet. Deterministic computation of the characteristic polynomial in the time of matrix multiplication. 2020. ⟨hal-02963147⟩

Partager

Métriques

Consultations de la notice

14

Téléchargements de fichiers

6