Safe and Effective Determinant Evaluation
| Author(s) : | Kenneth L. Clarkson, |
| Publisher : | N/A |
| Publication Date : | 1992 |
| ISSN : | N/A |
| Abstract : | The problem of evaluating the sign of the determinant of a small matrix arises in many geometric algorithms. Given an n \Theta n matrix A with integer entries, whose columns are all smaller than M in Euclidean norm, the algorithm given here evaluates the sign of the determinant det A exactly. The algorithm requires an arithmetic precision of less than 1:5n + 2 lg M bits. The number of arithmetic operations needed is O(n 3, |