Polynomial remainder sequence and approximate GCD

ABSTRACT

Let P1 and P2 be polynomials, univariate or multivariate, and let (P1, P2, P3,…, Pi,…) be a polynomial remainder sequence. Let Ai and Bi (i = 3, 4,…) be polynomials such that AiP1 + BiP2 = Pi, deg(Ai) < deg(P2) - deg(Pi), deg(Bi) < deg(P1) - deg(Pi), where the degree is for the main variable. We derive relations such as CiP1 = -Bi+1Pi + BiPi+1 and CiP2 = Ai+1Pi - AiPi+1, where Ci is independent of the main variable. Using these relations, we discuss approximate common divisors calculated by polynomial remainder sequence.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Theory, Verification