Efficient exact evaluation of signs of determinants (Q1977117)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient exact evaluation of signs of determinants |
scientific article |
Statements
Efficient exact evaluation of signs of determinants (English)
0 references
22 June 2000
0 references
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.
0 references
signs of determinants
0 references
computational geometry
0 references
computer graphics
0 references
nonnumerical algorithms
0 references
geometric algorithms
0 references
reorthogonalization method
0 references
Gram-Schmidt orthogonalization
0 references
lattice method
0 references