Fast computation of the Smith normal form of an integer matrix
Mark W. Giesbrecht · 1995
We present two new probabilistic algorithms for computing the Smith normal form of an A 2 Z m\\Thetan . The first requires an expected number of O(m 2 n \\Delta M(m log kAk)) bit operations (ignoring logarithmic factors) and is of the Las Vegas type; that is, it never produces an incorrect answer. Here kAk = max ij jA ij j and M(l) bit operations are sufficient to multiply two l-bit integers (M(l) = l 2 using standard arithmetic) . This improves on the previously best known (deterministic) algorithm of Hafner and McCurley, which requires about O(m 3 n log kAk \\Delta M(m log kAk)) bit operations. We also present an even faster, more space efficient algorithm which requires an expected number of O((m 3 n log kAk + m 3 log 2 kAk) \\Delta log(1=ffl)) bit operations using standard integer arithmetic. This algorithm is of the Monte Carlo type: it returns the correct result with probability at least 1 \\Gamma ffl for a user specified tolerance ffl ? 0. This algorithm also require...