A Complete Analysis of Clarkson's Algorithm for Safe Determinant Evaluation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 1996

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

Mariette Yvinec

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-3051.pdf (407.96 Ko) Télécharger le fichier

Dates et versions

inria-00073641 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00073641 , version 1

Citer

Hervé Brönnimann, Mariette Yvinec. A Complete Analysis of Clarkson's Algorithm for Safe Determinant Evaluation. RR-3051, INRIA. 1996. ⟨inria-00073641⟩
237 Consultations
142 Téléchargements

Partager

Gmail Facebook X LinkedIn More