inria-00073549, version 1
Efficient Exact Evaluation of Signs of Determinants
Hervé Brönnimann 1Mariette Yvinec
N° RR-3140 (1997)
Résumé : 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.
- 1 : PRISME (INRIA Sophia Antipolis)
- INRIA
- Domaine : Informatique/Autre
- Mots-clés : COMPUTATIONAL GEOMETRY / EXACT ARITHMETIC / PRECISION / ROBUST ALGORITHMS
- Référence interne : RR-3140
- inria-00073549, version 1
- http://hal.inria.fr/inria-00073549
- oai:hal.inria.fr:inria-00073549
- Contributeur : Rapport De Recherche Inria
- Soumis le : Mercredi 24 Mai 2006, 13:10:28
- Dernière modification le : Mercredi 31 Mai 2006, 14:24:27






Documents associés

Exporter