Approximate Radical for Clusters: A Global Approach Using Gaussian Elimination or SVD
Approximate Radical for Clusters: A Global Approach Using Gaussian Elimination or SVD
复制标题
簇的近似根式：使用高斯消元法或 SVD 的全局方法
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Á. Szántó
中科院分区：
文献类型：
--
作者：
Itnuit Janovitz;L. Rónyai;Á. Szántó
摘要：我们引入一个轨迹矩阵，附加到零维理想
$$ ilde{I}$$
。我们证明了迹矩阵可以成为处理具有聚类根的多项式方程组的有用工具。我们提出了一种基于迪克森引理的方法来计算“近似根式”
$$ ilde{I}$$
在
$${mathbb{C}}[x_1,ldots, x_m]$$
它具有零个簇：对于足够小的簇，近似激进理想在每个簇中恰好有一个根。我们的方法是“全局”的，因为它同时适用于所有集群：问题被简化为计算迹线矩阵的数值零空间，该矩阵可以从生成多项式有效计算
$$ ilde{I}$$
。为了计算轨迹矩阵的数值零空间，我们建议使用高斯消去法和旋转或奇异值分解。我们证明如果
$$ ilde{I}$$
具有 k 个不同的零簇，每个簇的半径在 ∞-范数中最大为 ɛ，则迹矩阵上的 k 步高斯消元会产生一个子矩阵，其中所有条目均渐近等于 ɛ2。我们还证明了迹矩阵的第 (k + 1) 个奇异值与 ɛ2 成正比。生成的近似根在每个簇中都有一个根，其坐标是该簇的算术平均值，直到误差项渐近等于 ɛ2。在单变量情况下，我们的方法提供了已知近似无平方因式分解算法的替代方案，该算法更简单并且其准确性更好地被理解。
Abstract.We introduce a matrix of traces, attached to a zero dimensional ideal
$$ ilde{I}$$
. We show that the matrix of traces can be a useful tool in handling systems of polynomial equations with clustered roots. We present a method based on Dickson’s lemma to compute the “approximate radical” of
$$ ilde{I}$$
in
$${mathbb{C}}[x_1,ldots, x_m]$$
which has zero clusters: the approximate radical ideal has exactly one root in each cluster for sufficiently small clusters. Our method is “global” in the sense that it works simultaneously for all clusters: the problem is reduced to the computation of the numerical nullspace of the matrix of traces, a matrix efficiently computable from the generating polynomials of
$$ ilde{I}$$
. To compute the numerical nullspace of the matrix of traces we propose to use Gaussian elimination with pivoting or singular value decomposition. We prove that if
$$ ilde{I}$$
has k distinct zero clusters each of radius at most ɛ in the ∞-norm, then k steps of Gaussian elimination on the matrix of traces yields a submatrix with all entries asymptotically equal to ɛ2. We also show that the (k + 1)-th singular value of the matrix of traces is proportional to ɛ2. The resulting approximate radical has one root in each cluster with coordinates which are the arithmetic mean of the cluster, up to an error term asymptotically equal to ɛ2. In the univariate case our method gives an alternative to known approximate square-free factorization algorithms which is simpler and its accuracy is better understood.