Parallel algorithms for hermite normal form of an integer matrix

ABSTRACT

The main problem in the integral matrices triangularization is the 'intermediate coefficients swell'. This aspect limits the dimension of treated matrices. Since 1985, we have at our disposal, the lliopoulos algorithm to compute the Hermite Normal Form of an Integer Matrix controlling the coefficients growth by mean of the determinant. We present here two parallelizations of this algorithm and their implementations on a MIMD machine, with 16 processors.

REFERENCES

• 1: Gordon H. Bradley, Algorithm and bound for the greatest common divisor of n integers, Communications of the ACM, v.13 n.7, p.433-436, July 1970 [doi>10.1145/362686.362694]
• 2: Bradley G.H., "Algorithms for Hermite and Smith Normal Matrices and linear Diophantine Equations", Mathematics of Computation 25(116), pp. 897-907, October 1971,
• 3: Chou T-W.J., & Collins G.E., "Algorithms for the Solution of Systems of Linear Diophantine Equations", SIAM J. Computing 11 (4), p. 687-708, November 1982.
• 4: P. D. Domich , R. Kannan , L. E. Trotter, Jr., Hermite normal form computation using modulo determinant arithmetic, Mathematics of Operations Research, v.12 n.1, p.50-59, Feb. 1987 [doi>10.1287/moor.12.1.50]
• 5: Gerasoulis A. and Nelken i., "Gaussian Elimination and Gauss-lordan on Mired architectures", LCSR-TR-105, Rutgers University, 1988.
• 6: Ravindran Kannan, The size of numbers in the analysis of certain algorithms, 1980
• 7: Kannan R., & Bachem A., "Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an integer Matrix", SIAM J. Computing 8(4), p. 499-507, November 1979.
• 8: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 9: Costas S. Iliopuolos, Gaussian Elimination over a Euclidean Ring, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.29-30, April 01-03, 1985
• 10: Jean-Louis Roch , Pascale Sénéchaud , Françoise Roch-Siebert , Gilles Villard, Computer Algebra on MIMD Machine, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.423-439, July 04-08, 1988
• 11: Roch J.L., "Towards a Parallel Computer Algebra coprocessor", Proc. of First International Workshop on Computer Algebra and Parallelism, Grenoble, june 1988.
• 12: Saad Y., "Communication Complexity of the Gaussian Elimination on a Multiprocessor", Lin. Alg. Appl. (77), 1986.
• 13: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 14: Villard G., "Calcul Formel et Parall~lisme' R6solution de Syst~mes Lin6aires ", PH.D. Thesis, 'Institut National Polytechnique de Grenoble', December 1988.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms, Theory