Computing the sign or the value of the determinant of an integrer matrix, a complexity survey - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 2002

Computing the sign or the value of the determinant of an integrer matrix, a complexity survey

Résumé

Certified computation of the sign of the determinant of a matrix and determinant itself is a challenge for both numerical and exact methods. We survey the complexity of existing methods to solve these problems when the input is an n x n matrix A with integer entries. We study the bit-complexities of the algorithms asymptotically in n and the norm of A. Existing approaches rely on numerical approximate computations, on exact computations, or on both types of arithmetic in combination.
Calculer le signe du déterminant d'une matrice ou calculer le déterminant lui-même est gestion importante aussi bien pour les approches numériques que pour les approches exactes. Nous proposons un tour d’horizon des complexités des méthodes pour résoudre ces problèmes quand la matrice en entrées est un matrice n x n à coefficients entiers. Nous regardons les complexités binaires asymptotiquement en n et en la norme de A. Les approches existantes reposent sur des calculs numériques approchés, sur des calculs exacts ou même surs l’utilisation combinée des deux types d’arithmétiques
Fichier principal
Vignette du fichier
RR2002-02.pdf (344.05 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101855 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101855 , version 1

Citer

Erich Kaltofen, Gilles Villard. Computing the sign or the value of the determinant of an integrer matrix, a complexity survey. [Research Report] LIP RR-2002-2, Laboratoire de l'informatique du parallélisme. 2002, 2+14p. ⟨hal-02101855⟩
27 Consultations
193 Téléchargements

Partager

More