Residual hermite normal form computations

ABSTRACT

This paper extends the class of Hermite normal form solution procedures that use modulo determinant arithmetic. Given any relatively prime factorization of the determinant value, integral congruence relations are used to compute the Hermite normal form. A polynomial-time complexity bound that is a function of the length of the input string exists for this class of procedures. Computational results for this new approach are given.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: W. A. Blankinship, Algorithm 287: matrix triangulation with integer arithmetic [F1], Communications of the ACM, v.9 n.7, p.513, July 1966 [doi>10.1145/365719.365970]
• 3: BRADLEY, G.H. Algorithms for Hermite and Smith normal form matrices and linear diophantine equations. Math. Comput. 25 (1971), 897-907.
• 4: Tsu-Wu Joseph Chou, Algorithms for the solution of systems of linear diophantine equations, 1979
• 5: DOMICH, P.D. Three new polynomially-time bounded Hermite normal form algorithms. Master's thesis, School of Operations Research and industrial Engineering, Cornell Univ., ithaca, N.Y., 1983.
• 6: Paul David Domich, Residual methods for computing hermite and smith normal forms (congruence, determinant, sparsity), 1985
• 7: 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]
• 8: EDMONDS, j. Systems of distinct representatives and linear algebra. J. Res. N.B.S. 71B (1967), 241-245.
• 9: FRUMKIN, M.A. Polynomial time algorithms in the theory of linear diophantine equations. In Fundamentals of Computation Theory, M. Karpinski, Ed. Lecture Notes in Computer Science 56 Springer, New York, 1977, pp. 386-392.
• 10: George Havas , Leon Sterling, Integer matrices and Abelian groups (invited), Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.431-451, June 01, 1979
• 11: HERMITE, C. Sur l'introduction des variables continues dans la theorie des nombres. J. Reine Angew. Math. 41 (1951), 191-216.
• 12: HERSTEIN, I.N. Topics in Algebra. J. Wiley, New York, 1975, p. 20.
• 13: KANNAN, R., AND BACHEM, A. Polynomial algorithms for computing and the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput. 9 (1979), 499-507.
• 14: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 15: LENSTRA, J. K., RINNOOY KAN, A. H. G., AND VAN EMDE BOAS, P. An appraisal of computational complexity for operations researchers. Mathematisch Centrum BW Tech. Rep. 159/82, Amsterdam, The Netherlands, 1982.
• 16: LINDAMOND, G. n. Numerical analysis in residue number systems. Computer Science Rep. TR-64-7, Univ. of Maryland, College Park, Md., 1964.
• 17: Michael T. McClellan, The Exact Solution of Systems of Linear Equations with Polynomial Coefficients, Journal of the ACM (JACM), v.20 n.4, p.563-588, Oct. 1973 [doi>10.1145/321784.321787]
• 18: POLLARD, S.M.Theorems on factorization and primality testing. Proc. Camb. Phil. Soc. 76 (1974), 251-258.
• 19: ROSSER, J. B. A method of computing exact inverse of matrices with integer coefficients. J. Res. N.B.S. 49 (1952), 349-358.
• 20: SIMS, C.C. The influence of computers in algebra. In Proceedings of the Symposium on Applied Mathematics, 20 (Missoula, Mont., Aug. 1973). American Mathematical Society, Providence, R.I., 1973, pp. 13-30.
• 21: SMITH, D. A. A basis algorithm for finitely generated Abelian groups. Math. Algorithms 1 (1966), 13-26.

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