Using Sparse Interpolation in Hensel Lifting
Using Sparse Interpolation in Hensel Lifting
复制标题
DOI：
10.1007/978-3-319-45641-6_25
复制
发表时间：
2016-09
期刊：
影响因子：
--
通讯作者：
M. Monagan;Baris Tuncer
中科院分区：
文献类型：
--
作者：
M. Monagan;Baris Tuncer
多变量多项式因式分解的标准方法是将单变量图像因子化，然后使用Hensel提升来恢复多变量因子，一次一个变量地提升图像的因子值。每一步都要解一个多元多项式丢番图方程。对于具有多项式的多元多项式，我们发现解这些多元丢番图方程支配分解时间。在这篇文章中，我们探索了稀疏内插方法的使用，该方法最初是由Zippel引入的，以加速这一过程。我们在Maple上的实验结果表明，我们能够显著地加速这一过程，从而实现对多元多项式因式分解的良好改进。
The standard approach to factor a multivariate polynomial inis to factor a univariate image inthen lift the factors of the image one variable at a time using Hensel lifting to recover the multivariate factors. At each step one must solve a multivariate polynomial Diophantine equation. For polynomials in many variables with many terms we find that solving these multivariate Diophantine equations dominates the factorization time. In this paper we explore the use of sparse interpolation methods, originally introduced by Zippel, to speed this up. We present experimental results in Maple showing that we are able to dramatically speed this up and thereby achieve a good improvement for multivariate polynomial factorization.