Certified Numerical Computation of the Sign of a Matrix Determinant
Victor Y. Pan and Yanqiang Yu
Certified computation of the sign of a matrix determinant is a central problem in computational geometry. The certification by the known methods is practically difficult because the magnitude of the determinant of an integer input matrix $A$ may vary dramatically, from 1 to $\| A \|^n$, and the roundoff error bound of the determinant computation varies proportionally. Because of such a variation, high precision computation of det $A$ is required to ensure that the error bound is smaller than the magnitude of the determinant. We observe, however, that our certification task of determining only a single bit of det $A$, that is, the bit carrying the sign, does not require to estimate the latter roundoff error. Instead, we solve a much simpler task of computing numerically the factorizaion of a matrix by Gaussian elimination with pivoting and of estimating the minimum distance $1/\|A^{-1} \|$ from $A$ to a singular matrix. Such an estimate gives us a desired range for the roundoff error of the factorization such that the invariance of the sign of det $A$ is ensured as long as the error varies in this range. Based on these observations, we show the resulting simplified methods for the certified computation of the sign, compare them with other approaches, observe the possibility of effective combination of our methods with some known symbolic methods for this problem, and confirm the efficiency of our techniques by some numerical tests.