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
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|