A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix Original Research Article

A Las Vegas probabilistic algorithm is presented that finds the Smith normal form S set membership, variant Q[x]n × n of a nonsingular input matrix A set membership, variant Z[x]n × n. The algorithm requires an expected number of Onot, vert, similar (n3d(d + n2logshort parallelAshort parallel)) bit operations (where short parallelAshort parallel bounds the magnitude of all integer coefficients appearing in A, and d bounds the degrees of entries of A). In practice, the main cost of the computation is obtaining a nonunimodular triangularization of a polynomial matrix of the same dimension and with similar size entries to those of the input matrix. We show how to accomplish this in Onot, vert, similar (n5d(d + logshort parallelAshort parallel)logshort parallelAshort parallel) bit operations using standard integer, polynomial, and matrix arithmetic. These complexity results improve significantly on previous algorithms in both a theoretical and a practical sense.