s'authentifier
version française rss feed

inria-00073549, version 1

Efficient Exact Evaluation of Signs of Determinants

Hervé Brönnimann 1, Mariette 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.

  • Domaine : Informatique/Autre
  • Mots-clés : COMPUTATIONAL GEOMETRY / EXACT ARITHMETIC / PRECISION / ROBUST ALGORITHMS
  • Référence interne : RR-3140
 
  • inria-00073549, version 1
  • oai:hal.inria.fr:inria-00073549
  • Contributeur : 
  • Soumis le : Mercredi 24 Mai 2006, 13:10:28
  • Dernière modification le : Mercredi 31 Mai 2006, 14:24:27
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...