An output-sensitive variant of the baby steps/giant steps determinant algorithm
Erich Kaltofen · 2002
This paper provides an adaptive version of the unblocked baby steps/giant steps algorithm [20, Section 2]. The result is most easily stated when b |#| where # is the determinant to be computed and # with 1 is not known. Note that by Hadamard's bound |#|#n(b +log 2 (n)/2), so # = 0 covers the worst case. We describe a Monte Carlo algorithm that produces #in(n bit operations, again with standard matrix arithmetic. The corresponding bit complexity of the early termination Gaussian elimination method is 4-# , which is always more, and that of the algorithm by [10] is (n 1+1/2 Our adaptive determinant algorithm can be speeded by use of subcubic matrix multiplication algorithms so as to outperform an early termination Gaussian elimination algorithm that employs subcubic matrix multiplication. Such results seem, however, of purely theoretical interest; see Section 4 for a more in-depth discussion. Here we add that the exponent "+o(1)" in the version that uses cubic matrix multiplication and that has bit complexity (n is introduced (except when b n) because the moduli of the Chinese remainder algorithm cannot be chosen of fixed magnitude. However, for all practical purposes primes with 32 or 64 bit will su#ce to recover determinants of any reasonable length, say of fewer 10 binary digits. Therefore the polylogarithmic factors in our complexity estimates do not degrade the practical performance of our method