Near optimal algorithms for computing Smith normal forms of integer matrices
Arne Storjohann · 1996
We present new algorithms for computing Smith normal forms of matrices over the integers and over the integers modulo d. For the case of matrices over ZZ d , we present an algorithm that computes the Smith form S of an A 2 ZZ n\\Thetam d in only O(n `\\Gamma1 m) operations from ZZ d . Here, ` is the exponent for matrix multiplication over rings: two n \\Theta n matrices over a ring R can be multiplied in O(n ` ) operations from R. We apply our algorithm for matrices over ZZ d to get an algorithm for computing the Smith form S of an A 2 ZZ n\\Thetam in O~(n `\\Gamma1 m \\Delta M(n log jjAjj)) bit operations (where jjAjj = max jA i;j j and M(t) bounds the cost of multiplying two dte-bit integers). These complexity results improve significantly on the complexity of previously best known Smith form algorithms (both deterministic and probabilistic) which guarantee correctness. 1 Introduction The Smith normal form is a canonical diagonal form for equivalence of matrices over a princ...