HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

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

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.
Keywords :
Document type :
Reports
Domain :
Complete list of metadata

https://hal.inria.fr/inria-00073641
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 1:23:57 PM
Last modification on : Friday, February 4, 2022 - 3:17:34 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:53:08 PM

### Identifiers

• HAL Id : inria-00073641, version 1

### Citation

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

Record views