A Complete Analysis of Clarksons Algorithm for Safe Determinant EvaluationReport as inadecuate




A Complete Analysis of Clarksons Algorithm for Safe Determinant Evaluation - Download this document for free, or read online. Document in PDF available to download.

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+On$ 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 : COMPUTATIONAL GEOMETRY EXACT ARITHMETIC





Author: Hervé Brönnimann - Mariette Yvinec

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents