A Complete Analysis of Clarkson's Algorithm for Safe Determinant Evaluation

Hervé Brönnimann 1 Mariette Yvinec
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper, we give a complete and self-contained analysis of Clarkson's algorithm that performs safe and efficient determinant evaluation of an $n\times n$ matrix with integer coefficients that can be expressed with $b$ bits. Clarkson's original paper is generally felt difficult to read. We complete the gaps in his exposition, simplifying the analysis where we can. The number of extra bits needed by this analysis is roughly equivalent to the number of bits needed by Clarkson's analysis. We show that the algorithm performs sign evaluation correctly if $b+O(n)$ bits are available. We give a table of the maximum numbers $b$ of bits available for the entries as a function of $n$, when the arithmetic is performed using a floating point processor complying with the IEEE 754 standard for double precision arithmetic (with $53$ bits available for the mantissa). We also gain some insight into the practical behavior of the algorithm by experimenting. In particular, we provide experimental evidence that the algorithm evaluates correctly the sign of determinants of order up to 15 with $48$-bit coefficients.
Type de document :
Rapport
RR-3051, INRIA. 1996
Liste complète des métadonnées

https://hal.inria.fr/inria-00073641
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:23:57
Dernière modification le : samedi 27 janvier 2018 - 01:31:02
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:53:08

Fichiers

Identifiants

  • HAL Id : inria-00073641, version 1

Collections

Citation

Hervé Brönnimann, Mariette Yvinec. A Complete Analysis of Clarkson's Algorithm for Safe Determinant Evaluation. RR-3051, INRIA. 1996. 〈inria-00073641〉

Partager

Métriques

Consultations de la notice

258

Téléchargements de fichiers

149