Combining Algebraic and Numerical Techniques for Computing Matrix Determinant

Mohammad M. Tabanjeh

Department of Mathematics and Computer Science, Virginia State University, Petersburg, USA.

DOI: 10.4236/ajcm.2014.45039                

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 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 = 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⁴). We reduced this cost to O(n³) by employing the faster p-adic lifting technique (see Section 5.3).

Keywords

Matrix Determinant, Sign of the Determinant, p-Adic Lifting, Modular Determinant, Matrix Factorization, Bit-Precision

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Muir, T. (1960) The Theory of Determinants in Historical Order of Development. Vol. I-IV, Dover, New York.
[2]	Fortune, S. (1992) Voronoi Diagrams and Delaunay Triangulations. In: Du, D.A. and Hwang, F.K., Eds., Computing in Euclidean Geometry, World Scientific Publishing Co., Singapore City, 193-233.
[3]	Br?nnimann, H., Emiris, I.Z., Pan, V.Y. and Pion, S. (1997) Computing Exact Geometric Predicates Using Modular Arithmetic. Proceedings of the 13th Annual ACM Symposium on Computational Geometry, 174-182.
[4]	Br?nnimann, H. and Yvinec, M. (2000) Efficient Exact Evaluation of Signs of Determinant. Algorithmica, 27, 21-56. http://dx.doi.org/10.1007/s004530010003
[5]	Pan, V.Y. and Yu, Y. (2001) Certification of Numerical Computation of the Sign of the Determinant of a Matrix. Algorithmica, 30, 708-724. http://dx.doi.org/10.1007/s00453-001-0032-8
[6]	Clarkson, K.L. (1992) Safe and Effective Determinant Evaluation. Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 387-395.
[7]	Avnaim, F., Boissonnat, J., Devillers, O., Preparata, F.P. and Yvinec, M. (1997) Evaluating Signs of Determinants Using Single-Precision Arithmetic. Algorithmica, 17, 111-132. http://dx.doi.org/10.1007/BF02522822
[8]	Pan, V., Yu, Y. and Stewart, C. (1997) Algebraic and Numerical Techniques for Computation of Matrix Determinants. Computers & Mathematics with Applications, 34, 43-70. http://dx.doi.org/10.1016/S0898-1221(97)00097-7
[9]	Golub, G.H. and Van Loan, C.F. (1996) Matrix Computations. 3rd Edition, John Hopkins University Press, Baltimore.
[10]	Edmonds, J. (1967) Systems of Distinct Representatives and Linear Algebra. Journal of Research of the National Bureau of Standards, 71, 241-245. http://dx.doi.org/10.6028/jres.071B.033
[11]	Bareiss, E.H. (1969) Sylvester’s Identity and Multistep Integer-Preserving Gaussian Elimination. Mathematics of Computation, 22, 565-578.
[12]	Bini, D. and Pan, V.Y. (1994) Polynomial and Matrix Computations, Fundamental Algorithms. Vol. 1, Birkhäuser, Boston. http://dx.doi.org/10.1007/978-1-4612-0265-3
[13]	Conte, S.D. and de Boor, C. (1980) Elementary Numerical Analysis: An Algorithm Approach. McGraw-Hill, New York.