Towards certified irreducibility testing of bivariate approximate polynomials
Towards certified irreducibility testing of bivariate approximate polynomials
复制标题
迈向二元近似多项式的认证不可约性测试
DOI：
10.1145/780506.780531
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Kosaku Nagasaka
中科院分区：
文献类型：
--
作者：
Kosaku Nagasaka
设<i>F</i>(<i>x, u</i>)是一个给定的二元多项式，ε是一个小正数。我们考虑的近似因子分解F <我> < / i >:找到多项式<我> G H < / i >和Δ<正> <我> F < / i > < /正>,<我> F = GH < / i > +Δ<正> <我> F < / i > < /正>,为Δ<正> <我> F < / i > < /正>为/为F <我> < / i >为=ε,为P <我> < / i >为代表的2-norm多项式<我> P。首先，我们引入了<i>F</i>的不可约性与某矩阵的奇异值之间的关系。利用这一关系和二元多项式幂级数根的变分上界，给出了系数在给定容差范围内扰动的多项式的绝对不可约检验算法。此外，我们给出了给定二元多项式近似分解的容忍度的下界。下界是使给定多项式可约的摄动的必要大小。
Let <i>F</i>(<i>x, u</i>) be a given bivariate polynomial and ε be a small positive number. We consider the approximate factorization of <i>F</i>: find polynomials <i>G, H</i> and Δ<inf><i>F</i></inf> such that <i>F = GH</i> + Δ<inf><i>F</i></inf> and ‖Δ<inf><i>F</i></inf>‖ / ‖<i>F</i>‖= ε, where ‖<i>P</i>‖ denotes 2-norm of polynomial <i>P.</i> At first, we introduce a relation between the irreducibility of <i>F</i> and the singular value of a certain matrix. By this relation and an upper bound of variations of the power-series roots of a bivariate polynomial, we give an algorithm for an absolute irreducibility test of a polynomial whose coefficients are perturbed within a given tolerance. In addition, we give a lower bound for a tolerance of the approximate factorization of a given bivariate polynomial. The lower bound is the necessary magnitude of perturbations which make a given polynomial reducible.