Integer Smith form via the valence: experience with large sparse matrices from homology

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.

REFERENCES

• 1: E. Babson, A. BjSrner, S. Linusson, J. Shareshian, and V. Welker. Complexes of not i-connected graphs. Topology, 38(2):271-299, 1999.
• 2: E. H. Bareiss. Sylvester's identity and multistep integer-preserving Gaussian elimination. Mathematics of Computation, 22(103):565-578, July 1968.
• 3: A. BjSerner, L. Lov~sz, S. Vredica, and R. T. Zivaljevid. Chessboard complexes and matching complexes. Journal of the London Mathematical Society, H. Set. ~9, No.l, 25-39, 1994.
• 4: Anders Björner , Volkmar Welker, Complexes of Directed Graphs, SIAM Journal on Discrete Mathematics, v.12 n.4, p.413-424, Oct. 1999 [doi>10.1137/S0895480198338724]
• 5: A. Brauer. Limits for the characteristic roots of a matrix. Duke Mathematical Journal, 14:21-26, 1947.
• 6: R. A. Brualdi and S. Mellendorf. Regions in the complex plane containing the eigenvalues of a matrix. American Mathematical Monthly, 101(10):975-985, Dec. 1994.
• 7: Dixon, John D. Exact solution of linear equations using p-adic expansions. Numerische Mathematik, 40:137-141, 1982.
• 8: J.-G. Dumas. David and Goliath: computing the rank of sparse matrices. Technical report, Sept. 1999. Internal report, Linbox group.
• 9: J.-G. Dumas. Calcul du polyn6me minimal entier en athapascan-1 et linbox. In RenPar '2000. Acres des douzi~mes rencontres francophones du paralllismes, June 19-22 2000.
• 10: J.-G. Dumas, F. Heckenbach, B. D. Saunders, and V. Welker. Simplicial Homology, a share package for GAP, Mar. 2000. Manual (htt p://www, cis. udel. edu/~heckenba/Homology).
• 11: Wayne Eberly , Erich Kaltofen, On randomized Lanczos algorithms, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.176-183, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258776]
• 12: F. R. Gantmacher. The Theory of Matrices. Chelsea, New York, 1959.
• 13: Mark Giesbrecht, Probabilistic Computation of the Smith Normal Form of a Sparse Integer Matrix, Proceedings of the Second International Symposium on Algorithmic Number Theory, p.173-186, May 18-23, 1996
• 14: Mark Giesbrecht, Efficient parallel solution of sparse systems of linear diophantine equations, Proceedings of the second international symposium on Parallel symbolic computation, p.1-10, July 20-22, 1997, Maui, Hawaii, United States [doi>10.1145/266670.266678]
• 15: Costas S. Iliopoulos, Worst-case complexity bounds on algorithms for computing the canonical structure of finite Abelian groups and the Hermite and Smith normal forms of an integer matrix, SIAM Journal on Computing, v.18 n.4, p.658-669, Aug. 1989 [doi>10.1137/0218045]
• 16: Erich Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation, v.64 n.210, p.777-806, April 1995 [doi>10.2307/2153451]
• 17: E. Kaltofen, M. S. Krishnamoorthy, and B. D. Saunders. Parallel algorithms for matrix normal forms. Linear Algebra and its Applications, 136:189-208, 1990.
• 18: Erich Kaltofen , B. David Saunders, On Wiedemann's Method of Solving Sparse Linear Systems, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.29-38, October 07-11, 1991
• 19: Hong R. Lee , B. David Saunders, Fraction free Gaussian elimination for sparse matrices, Journal of Symbolic Computation, v.19 n.5, p.393-402, May 1995 [doi>10.1006/jsco.1995.1022]
• 20: R. H. Lewis. Fermat, a computer algebra system for polynomial and matrix computations, 1997. http://www, bway. net / ~lewis.
• 21: J.-P. Massias and G. Robin. Bornes effectives pour certaines fonctions concernant les nombres premiers. Journal de Th~orie des Nombres de Bordeaux, 8:213-238, 1996.
• 22: M. Mignotte. Math~matiques pour le calcul formel, chapter Majoration de la taille des facteurs d'un polyn6me, page 168. PUF, 1989.
• 23: Thom Mulders , Arne Storjohann, Diophantine linear system solving, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.181-188, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309905]
• 24: J. R. Munkres. Elements of algebraic topology, chapter The computability of homology groups, pages 53-61. Advanced Book Program. The Benjamin/Cummings Publishing Company, Inc., 1994.
• 25: J. A. Reeds and N. J. A. Sloane. Shift-register synthesis (modulo m). SIAM Journal on Computing, 14(3):505-513, Aug. 1985.
• 26: Ernest E. Sibert , Harold F. Mattson , Paul Jackson, Finite Field Arithmetic Using the Connection Machine, Proceedings of the Second International Workshop on Computer Algebra and Parallelism, p.51-61, May 09-11, 1990
• 27: Arne Storjohann, Near optimal algorithms for computing Smith normal forms of integer matrices, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.267-274, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.237084]
• 28: O. Taussky. Bounds for characteristic roots of matrices. Duke Mathematical Journal, 15:1043-1044, 1948.
• 29: G. Villard, Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems (extended abstract), Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.32-39, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258742]
• 30: G. Villard. Applications of sparse pre-conditioners over finite fields. Technical report, Feb. 1999. Internal report, Linbox group.
• 31: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 32: D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing); Computations on matrices

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Performance, Theory, Verification

Keywords:
Gaussian elimination, Valence algorithm, Wiedemann algorithm, black box, homology groups, integer Smith form, large sparse matrix, simplicial complexes