Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs

doi:10.1016/j.jsc.2019.10.005

CSpace

	Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs
	Huang, Qiao-Long 1,2; Gao, Xiao-Shan 1,2
	2020-11-01
发表期刊	JOURNAL OF SYMBOLIC COMPUTATION
ISSN	0747-7171
卷号	101 页码:367-386
摘要	In this paper, we propose new deterministic and Monte Carlo interpolation algorithms for sparse multivariate polynomials represented by straight-line programs. Let f be an n-variate polynomial given by a straight-line program, which has a total degree bound D and a term bound T. Our deterministic algorithm is quadratic in n, T and cubic in log D in the Soft-Oh sense, which has better complexities than existing deterministic interpolation algorithms in most cases. Our Monte Carlo interpolation algorithms have better complexities than existing Monte Carlo interpolation algorithms and are the first algorithms whose complexities are linear in nT and polynomial in log D in the Soft-Oh sense. (C) 2019 Elsevier Ltd. All rights reserved.
关键词	Black box Interpolation Kronecker substitution
DOI	10.1016/j.jsc.2019.10.005
收录类别	SCI
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Theory & Methods ; Mathematics, Applied
WOS记录号	WOS:000540697500019
出版者	ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/51642
专题	中国科学院数学与系统科学研究院
通讯作者	Gao, Xiao-Shan
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, KLMM, Beijing, Peoples R China 2.Univ Chinese Acad Sci, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Huang, Qiao-Long,Gao, Xiao-Shan. Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs[J]. JOURNAL OF SYMBOLIC COMPUTATION,2020,101:367-386.
APA	Huang, Qiao-Long,&Gao, Xiao-Shan.(2020).Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs.JOURNAL OF SYMBOLIC COMPUTATION,101,367-386.
MLA	Huang, Qiao-Long,et al."Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs".JOURNAL OF SYMBOLIC COMPUTATION 101(2020):367-386.