Efficient exact evaluation of signs of determinants
Hervé Brönnimann, Mariette Yvinec · 1997
This paper presents a theoretical and experimental study on two different methods to evaluate the sign of a determinant with integer entries. The ilrst one is a method based on the Gram-Schmidt ortho,gonalisation process which has been proposed by Clark:son [Cla92]. We review the analysis of Clarkson and propose a variant of his method. The second method is arAextension ton x n determinants of the ABDPY method [ABD+94] which works only for 2 x 2 and 3 x 3 determinants. Both methods compute the signs of a n x n determinants whose entries are integers on b bits, by using an exact arithmetic on only b + O(n) bits. Furthermore, both methods are adaptive, dealing quickly with easy cases and resorting to the full-length computation only for null determinants.