Fast deterministic computation of determinants of dense matrices
John Abbott, Manuel Bronstein, Thom Mulders · 1999
In this paper we consider deterministic computation of the exact determinant of a dense matrix M of integers. We present a new algorithm with worst case complexity O \\Gamma n 4 (log n + log jjM jj) + n 3 log 2 jjM jj \\Delta , where n is the dimension of the matrix and jjM jj is a bound on the entries in M , but with average expected complexity O \\Gamma n 4 + n 3 (log n + log jjM jj) 2 \\Delta , assuming some plausible properties about the distribution of M . We will also describe a practical version of the algorithm and include timing data to compare this algorithm with existing ones. Our result does not depend on "fast" integer or matrix techniques. 1 Introduction One of the most fundamental characteristics of a square matrix is its determinant. Its being 0 expresses the non-- invertibility of the matrix, i.e. the fact that it has a non-- trivial kernel. For a real matrix, its absolute value is the volume of the multi--dimensional parallelepiped with generating ed...