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 ...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.展开更多
基金supported by the National Natural Science Foundation of China under Grant No.11688101
文摘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.