Hermite and Smith normal form algorithms over Dedekind domains

Cohen, Henri

doi:10.1090/S0025-5718-96-00766-1

Hermite and Smith normal form algorithms over Dedekind domains

Author: Henri Cohen
Journal: Math. Comp. 65 (1996), 1681-1699
MSC (1991): Primary 11Y40
DOI: https://doi.org/10.1090/S0025-5718-96-00766-1
MathSciNet review: 1361805
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We show how the usual algorithms valid over Euclidean domains, such as the Hermite Normal Form, the modular Hermite Normal Form and the Smith Normal Form can be extended to Dedekind rings. In a sequel to this paper, we will explain the use of these algorithms for computing in relative extensions of number fields.

W. Bosma and M. Pohst, Computations with finitely generated modules over Dedekind rings, Proceedings ISSAC’91 (1991), 151–156.

Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206

H. Cohen, F. Diaz y Diaz and M. Olivier, Algorithmic computations in relative extensions of number fields, in preparation.

P. D. Domich, R. Kannan, and L. E. Trotter Jr., Hermite normal form computation using modulo determinant arithmetic, Math. Oper. Res. 12 (1987), no. 1, 50–59. MR 882842, DOI https://doi.org/10.1287/moor.12.1.50

James L. Hafner and Kevin S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), no. 6, 1068–1083. MR 1135749, DOI https://doi.org/10.1137/0220067

G. Havas and B. Majewski, Hermite normal form computation for integer matrices, Congr. Numer. 105 (1994), 184–193.

Ravindran Kannan and Achim Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8 (1979), no. 4, 499–507. MR 573842, DOI https://doi.org/10.1137/0208040

P. Montgomery, in preparation.