[PDF][PDF] Efficient exact evaluation of signs of determinants

H Brönnimann, M Yvinec - … of the thirteenth annual symposium on …, 1997 - dl.acm.org
H Brönnimann, M Yvinec
Proceedings of the thirteenth annual symposium on Computational geometry, 1997dl.acm.org
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 xn 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 anxn …
Abstract
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 xn 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 anxn 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.
ACM Digital Library