A Fast and Numerically Stable Euclidean-Like Algorithm for Detecting Relatively Prime Numerical Polynomials
A Fast and Numerically Stable Euclidean-Like Algorithm for Detecting Relatively Prime Numerical Polynomials
复制标题
DOI：
10.1006/jsco.1998.0235
复制
发表时间：
1998-12
期刊：
影响因子：
--
通讯作者：
B. Beckermann;G. Labahn
中科院分区：
文献类型：
--
作者：
B. Beckermann;G. Labahn
在本文中，我们提供了一个快速的，数值稳定的算法来确定两个给定的多项式a和B是相对的素数，即使在其系数的小扰动保持相对素。这样的问题是重要的，在许多应用程序中，输入数据只能达到一定的精度。卡贝的延伸Pade近似的Meleshko算法？通常比先前已知的稳定方法快一个数量级。因此，它可以被用作一种廉价的测试，可以在试图计算“数值GCD”之前应用，通常是一项困难得多的任务。我们证明了该算法是数值稳定的，并给出实验验证的数值行为。最后，我们讨论了我们的方法，可以应用到实际计算的数值GCD的问题可能的扩展。
In this paper we provide a fast, numerically stable algorithm to determine when two given polynomialsa and b are relatively prime and remain relatively prime even after small perturbations of their coefficients. Such a problem is important in many applications where input data are only available up to a certain precision.Our method?an extension of the Cabay?Meleshko algorithm for Pade approximation?is typically an order of magnitude faster than previously known stable methods. As such it may be used as an inexpensive test which may be applied before attempting to compute a “numerical GCD”, in general a much more difficult task. We prove that the algorithm is numerically stable and give experiments verifying the numerical behaviour. Finally, we discuss possible extensions of our approach that can be applied to the problem of actually computing a numerical GCD.