HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Efficient Exact Evaluation of Signs of Determinants

Hervé Brönnimann 1 Mariette Yvinec
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : This paper presents a theoretical and experimental study on two different methods to evaluate the sign of a determinant with integer entries. The first one is a method based on the Gram-Schmidt orthogonalisation process which has been proposed by Clarkson. We review the analysis of Clarkson and propose a variant of his method. The second method is an extension to $n \times n$ determinants of the ABDPY method which works only for $2 \times 2$ and $3 \times 3$ determinants. Both methods compute the signs of a $n \times n$ determinant whose entries are integers on $b$ bits, by using an exact arithmetic on only $b +O(n)$ bits. Furthermore, both methods are adaptive, dealing quickly with easy cases and resorting to the full-length computation only for null determinants.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00073549
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 1:10:28 PM
Last modification on : Friday, February 4, 2022 - 3:18:46 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:49:52 PM

Identifiers

  • HAL Id : inria-00073549, version 1

Collections

Citation

Hervé Brönnimann, Mariette Yvinec. Efficient Exact Evaluation of Signs of Determinants. RR-3140, INRIA. 1997. ⟨inria-00073549⟩

Share

Metrics

Record views

82

Files downloads

453