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

Abstract : 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.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101855
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:08:11 AM
Last modification on : Thursday, November 21, 2019 - 2:34:03 AM

File

RR2002-02.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101855, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

3

Files downloads

14