View article

We present algorithms to compute the Smith Normal Form of matrices over two families of local rings. The algorithms use the black-box model which is suitable for sparse and structured matrices. The algorithms depend on a number of tools, such as matrix rank computation over finite fields, for which the best-known time- and memory-efficient algorithms are probabilistic.

For an n x n matrix A over the ring F[z]/(f^e), where f^e is a power of an irreducible polynomial f ∈ F[z] of degree d, our algorithm requires O(ηde²n) operations in F, where our black-box is assumed to require O(η) operations in F to compute a matrix-vector product by a vector over F[z]/(f^e) (and η is assumed greater than nde). The algorithm only requires additional storage for O(nde) elements of F. In particular, if η = O(nde), then our algorithm requires only O(n²d²e³) operations in F, which is an improvement on known dense methods for small d and e …