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

Erich Kaltofen (1) , Gilles Villard (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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

Mots clés: Approximate Computation; Bit-Complexity; Integer Matrix; Randomized Algorithms

Mots clés: Déterminant; Matrice d'entiers; Calcul approché; Calcul exact; Algorithme probabiliste

Domaines: Informatique [cs]

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⟩