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

doi:10.1016/j.tcs.2018.07.003

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 系统科学研究所

	A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over Z[x]
	Jing, Rui-Juan; Yuan, Chun-Ming; Gao, Xiao-Shan
刊名	THEORETICAL COMPUTER SCIENCE
	2019-01-10
卷号	755 页码:89-109
关键词	Generalized Hermite normal form Grobner basis Polynomial-time algorithm Z[x] module
ISSN号	0304-3975
DOI	10.1016/j.tcs.2018.07.003
英文摘要	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.
资助项目	NSFC[11688101]
WOS研究方向	Computer Science
语种	英语
出版者	ELSEVIER SCIENCE BV
WOS记录号	WOS:000456359300008
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/32137]
专题	系统科学研究所
通讯作者	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.