A HYBRID APPROACH FOR DETERMINANT SIGNS OF MODERATE-SIZED MATRICES Academic Article uri icon

abstract

  • Many geometric computations have at their core the evaluation of the sign of the determinant of a matrix. A fast, failsafe determinant sign operation is often a key part of a robust implementation. While linear problems from 3D computational geometry usually require determinants no larger than six, non-linear problems involving algebraic curves and surfaces produce larger matrices. Furthermore, the matrix entries often exceed machine precision, while existing approaches focus on machine-precision matrices. In this paper, we describe a practical hybrid method for computing the sign of the determinant of matrices of order up to 60. The stages include a floating-point filter based on the singular value decomposition of a matrix, an adaptive-precision implementation of Gaussian elimination, and a standard modular arithmetic determinant algorithm. We demonstrate our method on a number of examples encountered while solving polynomial systems.

published proceedings

  • International Journal of Computational Geometry & Applications

author list (cited authors)

  • CULVER, T., KEYSER, J., MANOCHA, D., & KRISHNAN, S.

citation count

  • 1

complete list of authors

  • CULVER, TIM||KEYSER, JOHN||MANOCHA, DINESH||KRISHNAN, SHANKAR

publication date

  • October 2003