A modular algorithm to compute the generalized Hermite normal form for Z[x]-lattices

DOI10.1016/J.JSC.2016.12.005MaRDI QIDQ504418zbMATH OpenOpenAlexFDO

Authors Rui-Juan Jing, Chunming Yuan

Publication date 16 January 2017

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2016.12.005

zbMATH Keywords

generalized Hermite normal formHensel liftingmodular algorithmreduced Gröbner bases

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Symbolic computation and algebraic computation (68W30)

Review text

The Hermite normal form is a standard representation for matrices over principal ideal domains. \textit{X. S. Gao} et al. in [``Binomial difference ideal and toric difference variety, Preprint, \url{arXiv:1404.7580}] generalized this concept for matrices over \(\mathbb{Z}[x]\). Furthermore, they proved that a matrix \([\mathbf{f_1},\dots ,\mathbf{f_m}]\in \mathbb{Z}[x]^{m \times n}\) is a generalized Hermite normal form if and only if the set of its column vectors \(F=\{\mathbf{f_1},\dots ,\mathbf{f_m}\}\) forms a reduced Gröbner basis of the \(\mathbb{Z}[x]\)-module generated by \(F\) for a certain monomial ordering. In the paper under review, the authors present a modular algorithm to compute the generalized Hermite normal form of matrices over \(\mathbb{Z}[x]\). For this purpose, they study the structure of Gröbner bases in \(\mathbb{Z}[x]\). It was shown that the proposed algorithm is efficient for the inputs containing low degree polynomials.

Recommendations

• A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over \(\mathbb{Z} [x]\)
• Modular algorithm for reducing matrices to the Smith normal form
• A polynomial time algorithm for computing the HNF of a module over the integers of a number field
• Hermite Normal Form Computation Using Modulo Determinant Arithmetic
• scientific article; zbMATH DE number 1254301

Cites work

• A p-adic approach to the computation of Gröbner bases
• Computing a Gröbner basis of a polynomial ideal over a Euclidean domain
• Fast computation of GCDs
• Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices
• Hermite Normal Form Computation Using Modulo Determinant Arithmetic
• scientific article; zbMATH DE number 1254301 (Why is no real title available?)
• Ideal basis and primary decompositions: case of two variables
• Modular algorithms for computing Gröbner bases.
• Normal forms for general polynomial matrices
• On lattice reduction for polynomial matrices
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Polynomial division and its computational complexity
• Using Algebraic Geometry

Cited in

(7)

• A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over \(\mathbb{Z} [x]\)
• Toric P-difference varieties
• Hermite Normal Form Computation Using Modulo Determinant Arithmetic
• Extended GCD and Hermite Normal Form Algorithms via Lattice Basis Reduction (addenda and errata)
• Hermite and Smith normal form algorithms over Dedekind domains
• An extension of the fpLLL library to Hermitian lattices
• A Formal Proof of the Computation of Hermite Normal Form in a General Setting

This page was built for publication: A modular algorithm to compute the generalized Hermite normal form for \(\mathbb{Z}[x]\)-lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q504418)