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.
Type de document :
RR-3140, INRIA. 1997
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:10:28
Dernière modification le : samedi 27 janvier 2018 - 01:31:31
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:49:52



  • HAL Id : inria-00073549, version 1



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



Consultations de la notice


Téléchargements de fichiers