Efficient exact evaluation of signs of determinants
type: Item
instance of: scholarly article
title: Efficient exact evaluation of signs of determinants
zbMATH Open document ID: 0947.65053
author: Mariette Yvinec
author: Hervé Brönnimann
published in: Algorithmica
publication date: 2000-06-22T00:00:00Z
full work available at URL: RR-3140.pdf
review text: 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.
Mathematics Subject Classification ID: 65F40
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 1444097
zbMATH Keywords: signs of determinants
zbMATH Keywords: computational geometry
zbMATH Keywords: computer graphics
zbMATH Keywords: nonnumerical algorithms
zbMATH Keywords: geometric algorithms
zbMATH Keywords: reorthogonalization method
zbMATH Keywords: Gram-Schmidt orthogonalization
zbMATH Keywords: lattice method
describes a project that uses: Hull
MaRDI profile type: Publication
OpenAlex ID: W2013279615
DOI: 10.1007/S004530010003
description: scientific article; zbMATH DE number 1444097