Combining Algebraic and Numerical Techniques for Computing Matrix Determinant

Abstract

Computing the sign of the determinant or the value of the determinant of an n × n matrix A is a classical well-know problem and it is a challenge for both numerical and algebraic methods. In this paper, we review, modify and combine various techniques of numerical linear algebra and rational algebraic computations (with no error) to achieve our main goal of decreasing the bit-precision for computing det A or its sign and enable us to obtain the solution with few arithmetic operations. In particular, we improved the precision bits of the p -adic lifting algorithm ( H = 2 h for a natural number h ), which may exceed the computer precision β (see Section 5.2), to at most bits (see Section 6). The computational cost of the p -adic lifting can be performed in O ( hn 4 ). We reduced this cost to O ( n 3 ) by employing the faster p -adic lifting technique (see Section 5.3).