next up previous
Next: Relation between gcds in [x] Up: Advanced Computer Algebra: The resultant Previous: Advanced Computer Algebra: The resultant

Coefficients growth in the Euclidean Algorithm over $ \mbox{${\mathbb Q}$}$[x]

We saw in the first chapter that running the Euclidean Algorithm in $ \mbox{${\mathbb Q}$}$[x] can lead to a significant expression swell. Let us try to estimate how coefficients grow. That is, we want to estimate the maximal space needed to store one coefficient of an intermediate polynomial. Let N be the number of bits of a machine word.

Definition 1   For an integer a $ \in$ $ \mbox{${\mathbb Z}$}$ we define $ \lambda$(a) the length of a as the minimum number of words to encode a. Hence for a $ \neq$ 0 we have

$\displaystyle \lambda$(a) = $\displaystyle \lfloor$log2(a)/N$\displaystyle \rfloor$ + 1    and    $\displaystyle \lambda$(0) = 0 (1)

For a rational number a = b/c with b, c $ \in$ $ \mbox{${\mathbb Z}$}$ and gcd(c, d )= 1 we define $ \lambda$(a), the length of a, as the maximum among $ \lambda$(b) and $ \lambda$(c).

Definition 2   For a polynomial a $ \in$ $ \mbox{${\mathbb Q}$}$[x] of degree n $ \geq$ 0 such that all coefficients have denominator b and such that the numerators an, an-1,..., a1, a0 have gcd 1 then we define the length of a as

$\displaystyle \lambda$(a) = max($\displaystyle \lambda$(b),$\displaystyle \max_{{{0 \leq i \leq n}}}^{{}}$($\displaystyle \lambda$(ai))) (2)

Remark 1   A polynomial a $ \in$ $ \mbox{${\mathbb Q}$}$[x] of degree n $ \geq$ 0 can be represented with

$\displaystyle \lambda$(a)$\displaystyle \left(\vphantom{ 2 + {\deg}(a) }\right.$2 + deg(a)$\displaystyle \left.\vphantom{ 2 + {\deg}(a) }\right)$ (3)

words.

Proposition 1   Let a, b be univariate polynomials over $ \mbox{${\mathbb Z}$}$ in x. Then we have
  1. $ \lambda$(a + b$ \leq$  max($ \lambda$(a),$ \lambda$(b)) + 1.
  2. $ \lambda$(ab$ \leq$  $ \lambda$(a) + $ \lambda$(b) + $ \lambda$(min(deg(a), deg(b)) + 1).

Proof. See [vzGG99]. $ \qedsymbol$

Proposition 2   Let a, b be univariate polynomials over $ \mbox{${\mathbb Z}$}$ in x. We assume that a and b are monic and that deg(a) = deg(b) + 1 holds. Let q and r be the quotient and the remainder of a w.r.t. b. Then we have

$\displaystyle \lambda$(r$\displaystyle \leq$  $\displaystyle \lambda$(a) + 2$\displaystyle \lambda$(b) + 3 (4)

Proof. We define

a  =  xn + an-1xn-1 + ... + a0    and    b  =  xn-1 + bn-2xn-2 + ... + b0 (5)

It is not hard to see that

q  =  x + an-1 - bn-2 (6)

Then

$\displaystyle \lambda$(q$\displaystyle \leq$  max($\displaystyle \lambda$(a),$\displaystyle \lambda$(b)) + 1 (7)

Thus

$\displaystyle \lambda$(bq$\displaystyle \leq$  max($\displaystyle \lambda$(a),$\displaystyle \lambda$(b)) + 1 + $\displaystyle \lambda$(b) + $\displaystyle \lambda$(deg(q) + 1) (8)

Recall that

r  =  a - bq (9)

Since $ \lambda$(bq) $ \geq$ $ \lambda$(a) we obtain

$\displaystyle \lambda$(r) $\displaystyle \leq$ max($\displaystyle \lambda$(a),$\displaystyle \lambda$(b)) + 1 + $\displaystyle \lambda$(b) + $\displaystyle \lambda$(deg(q) + 1) + 1
  $\displaystyle \leq$ $\displaystyle \lambda$(a) + 2$\displaystyle \lambda$(b) + 3
(10)

Indeed max($ \lambda$(a),$ \lambda$(b))  $ \leq$  $ \lambda$(a) + $ \lambda$(b) and $ \lambda$(deg(q) + 1)  =  $ \lambda$(2)  $ \leq$  1. $ \qedsymbol$

Remark 2   A similar result as Proposition 2 holds for monic polynomials a, b $ \in$ $ \mbox{${\mathbb Q}$}$[x] such that deg(a) = deg(b) + 1. See [vzGG99]. These results provide us with an exponential upper bound for the coefficient of the gcd computed by the Euclidean Algorithm. But in fact a polynomial bound can be established. Moreover there is an efficient modular approach for computing gcds in $ \mbox{${\mathbb Q}$}$[x] and $ \mbox{${\mathbb Z}$}$[x] as we shall see in the next sections.


next up previous
Next: Relation between gcds in [x] Up: Advanced Computer Algebra: The resultant Previous: Advanced Computer Algebra: The resultant
Marc Moreno Maza
2004-04-27