An Improved Early Termination Sparse Interpolation Algorithm for Multivariate Polynomials

doi:10.1007/s11424-017-6143-3

CSpace

	An Improved Early Termination Sparse Interpolation Algorithm for Multivariate Polynomials
	Huang, Qiaolong
	2018-04-01
发表期刊	JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY
ISSN	1009-6124
卷号	31 期号:2 页码:539-551
摘要	This paper presents an improved early termination algorithm for sparse black box multivariate polynomials, which reduces the interpolation problem into several sub-interpolation problems with less variables and fewer terms. Actually, all interpolations are eventually reduced to the interpolation of a list of polynomials with less terms than that of the original polynomial. Extensive experiments show that the new algorithm is much faster than the original algorithm.
关键词	Ben-Or and Tiwari's algorithm early termination algorithm recursive sparse interpolation
DOI	10.1007/s11424-017-6143-3
语种	英语
资助项目	National Natural Science Foundation of China[11688101]
WOS研究方向	Mathematics
WOS类目	Mathematics, Interdisciplinary Applications
WOS记录号	WOS:000427907200013
出版者	SPRINGER HEIDELBERG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/29828
专题	中国科学院数学与系统科学研究院
通讯作者	Huang, Qiaolong
作者单位	Chinese Acad Sci, Key Lab Math Mechanizat, Acad Math & Syst Sci, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Huang, Qiaolong. An Improved Early Termination Sparse Interpolation Algorithm for Multivariate Polynomials[J]. JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,2018,31(2):539-551.
APA	Huang, Qiaolong.(2018).An Improved Early Termination Sparse Interpolation Algorithm for Multivariate Polynomials.JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,31(2),539-551.
MLA	Huang, Qiaolong."An Improved Early Termination Sparse Interpolation Algorithm for Multivariate Polynomials".JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY 31.2(2018):539-551.