Approximate-GCD by Hribernig and Stetter

The approximate-GCD, which is called near-GCD in [8], of two polynomials $f_1, f_2 \in C[x]$, where C[x] is a complex number coefficient polynomial, is stated as the following concept.

Definition 3.1 (Hribernig and Stetter)   At the accuracy level $\alpha$, two polynomials $\tilde{f}_i\in C[x]$, i=1,2, possess a near-GCD $\tilde{g}$ if there exist polynomials $f^{\ast}_i\in C[x]$, i=1,2, which satisfy

$$GCD(f^{\ast}_1,f^{\ast}_2)=\tilde{g},\ and\ \Vert\tilde{f}_i-f^{\ast}_i\Vert\leq\alpha, i=1,2,$$ (5)

and deg $(\tilde{g})$ is the highest possible degree for (5). Equivalently, a near-GCD $\tilde{g}$ of $\tilde{f}_1$ and $\tilde{f}_2$satisfies

$$\tilde{f}_i=\tilde{g}\cdot\tilde{q}_i+\tilde{r}_i\ with\ \Vert\tilde{r}_i\Vert\leq\alpha, i=1,2.$$ (6)

A near-GCD at accuracy level $\alpha$ will be denoted by $\alpha\mbox{-}GCD(\tilde{f}_1,\tilde{f}_2)$.

Here, the norm of the polynomial means L₁ norm. A near-GCD $\tilde{g}$ is computed via Euclidean Algorithm and a relaxed termination criterion which should be imposed at a given accuracy level $\alpha$. The algorithm to compute $\alpha$-GCD of f₁ and f₂ is summarized as follows:

Algorithm 3.1 (tex2html_wrap_inline$$-GCD)  
Input: $f_1, f_2, \alpha$
Output: $\alpha$-GCD of f₁ and f₂
Method:

1.

Compute

$$f_{j-1}=f_j\cdot q_j+f_{j+1}$$

and

$$s_j^{(i)}=q_js_{j-1}^{(i)}+s_{j-2}^{(i)},\ j>i$$

for $j=2,3,\cdots$ and i=1,2 with

s_i-1⁽ⁱ⁾=0, s_i⁽ⁱ⁾=1.

2.

if $\Vert s_{j-1}^{(i)}f_{j+1}\Vert\leq\alpha$, then

$$f_j=\alpha\mbox{-}GCD(f_1,f_2).$$

 

The polynomials f_j generated by the algorithm, f₁ and f₂ are represented as

$$f_i=s^{(i)}_jf_j+s^{(i)}_{j-1}f_{j+1},\ j>i\geq 1.$$ (7)

In our case, f₁ and f₂ should be read as P(x) and Q(x), respectively. Also s⁽¹⁾_j,s⁽²⁾_j, and f_j should be read as p(x), q(x) and g(x), respectively. Therefore (7) is expressed as

$$\left\{\begin{array}{ccc} P(x) &=& p(x)g(x)+\delta P(x),\\ Q(x) &=& q(x)g(x)+\delta Q(x), \end{array}\right.$$ (8)

where $\delta P(x)=s^{(1)}_{j-1}f_{j+1}$ and $\delta Q(x)=s^{(2)}_{j-1}f_{j+1}$.