Affordable Access

Publisher Website

On Efficient Sparse Integer Matrix Smith Normal Form Computations

Authors
Journal
Journal of Symbolic Computation
0747-7171
Publisher
Elsevier
Publication Date
Volume
32
Identifiers
DOI: 10.1006/jsco.2001.0451
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract 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 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 computation of the homology of some large simplicial complexes.

There are no comments yet on this publication. Be the first to share your thoughts.