GPGCD, an Iterative Method for Calculating Approximate GCD, for Multiple Univariate Polynomials

摘要

We present an extension of our GPGCD method, proposed by the present author, an iterative method for calculating approximate greatest common divisor (GCD) of univariate polynomials, to multiple polynomial inputs. For a given tuple of polynomials and a degree, our algorithm finds a tuple of polynomials which has a GCD of the given degree and whose coefficients are perturbed from those in the original inputs, making the perturbations as small as possible, along with the GCD. The problem of approximate GCD is transferred to a constrained minimization problem, then solved with the so-called modified Newton method, which is a generalization of the gradient-projection method, by searching the solution iteratively. While our previous methods accept a pair of two polynomials with the real or the complex coefficients as inputs and outputs, respectively, here we extend it to handle more than two polynomial inputs with the real coefficients.