Bezoutの終結式行列を用いたGPGCD法による1変数多項式の近似GCDの計算 (Computer Algebra : Theory and its Applications)

Abstract

我々は, これまでに1変数多項式に対する近似GCD計算の反復算法であるGPGCD法を提案している. GPGCD法は, 与えられた多項式および次数と, 近似GCDの次数に対し, 可能な限り摂動を小さくし, その時の摂動および近似GCDを求める算法である. 本算法では, Sylvesterの終結式行列を用い, 与えられた近似GCD計算問題を制約付き最適化問題に帰着させ, 最適化問題を修正Newton法で解いている. 本稿では, 元のGPGCD法に用いたSylvesterの終結式行列に代えて, Bezoutの終結式行列を用いたGPGCD算法を提案する.

We have presented the GPGCD algorithm, which is an iterative algorithm for calculating approximate greatest common divisor (GCD) of univariate polynomials with real or complex coefficients. For a given pair of polynomials and a degree of the approximate GCD, our algorithm finds a pair of polynomials which has the GCD of the given degree, and makes the perturbations of whose coefficients from those in given polynomials as small as possible. We transfer the approx mate GCD problem to a constrained minimization problem with the Sylvester matrix, then solve it with so-called the modified Newton method. In this paper, in place of the Sylvester matrix, we present an algorithm which uses the Bezout matrix to transfer the problem.