Combining Algebraic and Numerical Techniques for Computing Matrix Determinant

• 作者: Mohammad M. Tabanjeh
• 来源期刊: 美国计算数学期刊(英文)
• 学科: 数学
• 关键词: MATRIX DETERMINANT Sign of the DETERMINANT P-ADIC Lifting Modular DETERMINANT MATRIX FACTORIZATION Bit-Precision
• 年，卷（期）: 2014,（5）
• 页码范围: 464-473
• 页数: 10页
• 分类号: O1

摘要

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 detA 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 = 2h 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(hn4). We reduced this cost to O(n3) by employing the faster p-adic lifting technique (see Section 5.3).