×

Hermite and Smith normal form algorithms over Dedekind domains. (English) Zbl 0853.11100

Summary: 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.

MSC:

11Y40 Algebraic number theory computations
13P99 Computational aspects and applications of commutative rings
11R99 Algebraic number theory: global fields
13F05 Dedekind, Prüfer, Krull and Mori rings and their generalizations
11R04 Algebraic numbers; rings of algebraic integers
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] W. Bosma and M. Pohst, Computations with finitely generated modules over Dedekind rings, Proceedings ISSAC’91 (1991), 151–156. · Zbl 0930.11088
[2] Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. · Zbl 0786.11071
[3] H. Cohen, F. Diaz y Diaz and M. Olivier, Algorithmic computations in relative extensions of number fields, in preparation. · Zbl 0987.11079
[4] 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. · Zbl 0624.65036
[5] James L. Hafner and Kevin S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), no. 6, 1068 – 1083. · Zbl 0738.68050
[6] G. Havas and B. Majewski, Hermite normal form computation for integer matrices, Congr. Numer. 105 (1994), 184–193. CMP 96:10 · Zbl 0836.65060
[7] 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. · Zbl 0446.65015
[8] P. Montgomery, in preparation.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.