On efficient sparse integer matrix Smith normal form computations

We present a new algorithm to compute the Integer Smith normal form of larg e sparse matrices. We reduce the computation of the Smith form to independe nt, and therefore parallel, computations module powers of word-size primes. Consequently, the algorithm does not suffer from coefficient growth. We ha ve implemented several variants of this algorithm (elimination and/or black box techniques) since practical performance depends strongly on the memory available. Our method has proven useful in algebraic topology for the comp utation of the homology of some large simplicial complexes. (C) 2001 Academ ic Press.