A Las Vegas algorithm for computing the smith form of a nonsingular integer matrix
Stavros Birmpilis, George Labahn, Arne Storjohann · 2020
We present a Las Vegas randomized algorithm to compute the Smith normal form of a nonsingular integer matrix. For an A ∈ Zn×n, the algorithm requires O(n3(log n + log ||A||)2 (log n)2) bit operations using standard integer and matrix arithmetic, where ||A|| = maxij |Aij | denotes the largest entry in absolute value. Fast integer and matrix multiplication can also be used, establishing that the Smith form can be computed in about the same number of bit operations as required to multiply two matrices of the same dimension and size of entries as the input matrix.