Approximate factorization of multivariate polynomials via differential equations
Approximate factorization of multivariate polynomials via differential equations
复制标题
DOI：
10.1145/1005285.1005311
复制
发表时间：
2004-07
期刊：
影响因子：
--
通讯作者：
Shuhong Gao;E. Kaltofen;Jon P. May;Zhengfeng Yang;L. Zhi
中科院分区：
文献类型：
--
作者：
Shuhong Gao;E. Kaltofen;Jon P. May;Zhengfeng Yang;L. Zhi
我们算法的输入是一个多元多项式，它的复数有理系数被认为是不精确的，有一个未知的误差，导致f在复数c上不可约。我们试图用一个小的量来扰动系数，这样得到的多项式因子超过c。理想情况下，人们希望在一些选定的距离测量中最小化扰动，但目前还没有有效的算法。本文给出了一种数值多元最大公约数算法，并将其应用于rupert和S. Gao算法的数值变体。我们的数值因子分解器反复使用奇异值分解。我们在大量实验数据上证明了我们的算法是实用的，并且可以在与输入误差相对大小大致相同的距离内找到可分解的多项式，即使输入中的相对误差很大（10-3）。
The input to our algorithm is a multivariate polynomial, whose complex rational coefficients are considered imprecise with an unknown error that causes f to be irreducible over the complex numbers C. We seek to perturb the coefficients by a small quantitity such that the resulting polynomial factors over C. Ideally, one would like to minimize the perturbation in some selected distance measure, but no efficient algorithm for that is known. We give a numerical multivariate greatest common divisor algorithm and use it on a numerical variant of algorithms by W. M. Ruppert and S. Gao. Our numerical factorizer makes repeated use of singular value decompositions. We demonstrate on a significant body of experimental data that our algorithm is practical and can find factorizable polynomials within a distance that is about the same in relative magnitude as the input error, even when the relative error in the input is substantial (10-3).