New Arithmetic Filter for the Sign of the Determinant of a Matrix
Victor Pan
Certified sign of the determinant of a matrix is very frequently required in various geometric and algebraic computations. The computations go faster when they are performed numerically, with floating point and rounding to a single precision. In this case, however, 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, slower computation of det $A$ with a high precision is frequently required to ensure that the output error bound is smaller than the magnitude of the determinant, and by experiments, the single precision computations tend to produce correct answer even where the above certification fails. 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 factorization of a matrix by Gaussian elimination with pivoting (which is a subroutine of LAPACK and LINPACK) 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 such observations, we improve substatially the known arithmetic filters for the certification of the sign.