On Efficient Sparse Integer Matrix Smith Normal Form Computations

摘要

We present a new algorithm to compute the Integer Smith normal form of large sparse matrices. We reduce the computation of the Smith form to independent, and therefore parallel, computations modulo powers of word-size primes. Consequently, the algorithm does not suffer from coefficient growth. We have implemented several variants of this al- gorithm (elimination and/or black box techniques) since practical performance depends sgrongly on the memory available.