Efficient exact evaluation of signs of determinants (Q1977117)

The reorthogonalization and the lattice methods are studied to evaluate the sign of a determinant with \(b\)-bit (absolute value is less than \(2^b\)) integer entries for dimensions up to at least 15. Theory and experiments are dealt with. The reorthogonalization method is a variant of the Gram-Schmidt orthogonalization process by \textit{K. L. Clarkson} [Proc. 33rd Ann. IEEE Symp. Found. Comput. Sci., 1992, 387-395 (1992; Zbl 0927.68040)]. The lattice method extends the ABDPY method [cf. \textit{F. Avnaim}, \textit{J.-D. Boissonnat}, \textit{O. Devilers}, \textit{F. P. Preparata} and \textit{M. Yvinec}, Algorithmica 17, No. 2, 111-132 (1997; Zbl 0865.68119)] to higher dimensions. Geometric algorithms are described such that a robust implementation can be obtained using only inaccurate but fast arithmetics provided by floating-point processors.