A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over Z[x]

doi:10.1016/j.tcs.2018.07.003

CSpace > 系统科学研究所

	A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over Z[x]
	Jing, Rui-Juan; Yuan, Chun-Ming; Gao, Xiao-Shan
	2019-01-10
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	755 页码:89-109
摘要	In this paper, we give the first polynomial time algorithm to compute the generalized Hermite normal form for a matrix F over Z[x], or equivalently, the reduced Grobner basis of the Z[x]-module generated by the column vectors of F. The algorithm has polynomial bit size computational complexities and is also shown to be practically more efficient than existing algorithms. The algorithm is based on three key ingredients. First, an F4 style algorithm to compute the Grobner basis is adopted, where a novel prolongation is designed such that the sizes of coefficient matrices under consideration are nicely controlled. Second, the complexity bound of the algorithm is achieved by a nice estimation for the degree and height bounds of the polynomials in the generalized Hermite normal form. Third, fast algorithms to compute Hermite normal forms of matrices over Z are used as the computational tool. (C) 2018 Elsevier B.V. All rights reserved.
关键词	Generalized Hermite normal form Grobner basis Polynomial-time algorithm Z[x] module
DOI	10.1016/j.tcs.2018.07.003
语种	英语
资助项目	NSFC[11688101]
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000456359300008
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/32138
专题	系统科学研究所
通讯作者	Gao, Xiao-Shan
作者单位	Chinese Acad Sci, Acad Math & Syst Sci, UCAS, KLMM, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Jing, Rui-Juan,Yuan, Chun-Ming,Gao, Xiao-Shan. A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over Z[x][J]. THEORETICAL COMPUTER SCIENCE,2019,755:89-109.
APA	Jing, Rui-Juan,Yuan, Chun-Ming,&Gao, Xiao-Shan.(2019).A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over Z[x].THEORETICAL COMPUTER SCIENCE,755,89-109.
MLA	Jing, Rui-Juan,et al."A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over Z[x]".THEORETICAL COMPUTER SCIENCE 755(2019):89-109.