Residual hermite normal form computations
- 1 September 1989
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 15 (3) , 275-286
- https://doi.org/10.1145/66888.66892
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.Keywords
This publication has 9 references indexed in Scilit:
- Hermite Normal Form Computation Using Modulo Determinant ArithmeticMathematics of Operations Research, 1987
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer MatrixSIAM Journal on Computing, 1979
- Polynomial time algorithms in the theory of linear diophantine equationsLecture Notes in Computer Science, 1977
- Theorems on factorization and primality testingMathematical Proceedings of the Cambridge Philosophical Society, 1974
- The Exact Solution of Systems of Linear Equations with Polynomial CoefficientsJournal of the ACM, 1973
- Algorithms for Hermite and Smith normal matrices and linear Diophantine equationsMathematics of Computation, 1971
- Systems of distinct representatives and linear algebraJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967
- Algorithm 287: matrix triangulation with integer arithmetic [F1]Communications of the ACM, 1966
- A method of computing exact inverses of matrices with integer coefficientsJournal of Research of the National Bureau of Standards, 1952