Skip to Main content Skip to Navigation
Reports

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

https://hal.inria.fr/inria-00073641
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 1:23:57 PM
Last modification on : Saturday, January 27, 2018 - 1:31:02 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:53:08 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

367

Files downloads

197