A modular algorithm to compute the generalized Hermite normal form for Z[x]-lattices. (July 2017)

• Record Type: Journal Article
• Authors: Jing, Rui-Juan; Yuan, Chun-Ming
• Is Part Of: Journal of symbolic computation. Volume 81(2017)
• Page Start: 97
• Page End: 118
• Publication Date: 2017-07
• Subjects: Generalized Hermite normal form -- Reduced Gröbner bases -- Modular algorithm -- Hensel Lifting; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.12.005
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: In this paper, a modular algorithm is given to compute the generalized Hermite normal form of matrices over Z [ x ], or equivalently, the reduced Gröbner basis of Z [ x ] -modules in Z [ x ] n . The main advantage of the algorithm is that the special structure of the Gröbner basis of ideals in Z [ x ] is taken into consideration. The algorithm is deterministic and seems to be the most efficient available algorithm for inputs with relatively low degrees.