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 <>
Submitted on : Wednesday, May 24, 2006 - 1:10:28 PM
Last modification on : Saturday, January 27, 2018 - 1:31:31 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

235

Files downloads

536