Manuel Kauers Hagenberg, December 17, 2002 RISC-Linz

Computer Algebra Exercises

Solution 2

Ex. (6) By the definition of polynomial multiplication,

( ∑_{i=0}^{r} u_{i}x^{i}) · ( ∑_{i=0}^{s} v_{i}x^{i}) = ∑_{i=0}^{r+s} c_{i}x_{i}  with  c_{i} = ∑_{k=0}^{i} u_{k} · v_{i−k}

where u_{k}, v_{k} = 0 for k < 0 or k greater than the polynomial’s degree.

The sum in the definition of c_{i} can have at most min{r, s} summands: If k > min{r, s}, then k − min{r, s} coefficients of the shorter polynomial vanish. It follows, that

|c_{max}| = | ∑_{k=0}^{min{r,s}} u_{k} · v_{i−k}| ≤ ∑_{k=0}^{min{r,s}} |u_{k} · v_{i−k}| ≤ ∑_{k=0}^{min{r,s}} m_{1}m_{2}
= min{r, s} · m_{1} · m_{2}.

It is obvious that this bound is sharp, just consider the special example u_{i} = m_{1} (i = 0, …, r), v_{i} = m_{2} (i = 0, …, s). .

Ex. (7) Let F be a finite field, and p, q ∈ F [x] of degree less than or equal to n. Write them as

p = p_{1}X^{n/2} + p_{0}, q = q_{1}X^{n/2} + q_{0}.

Then, according to Karatsuba’s trick, we compute p_{1} · q_{1}, p_{0} · q_{0}, and (p_{0} + p_{1}) · (q_{0} + q_{1}) recursively and return

p_{1} · q_{1}X^{n} + ((p_{0} + p_{1}) · (q_{0} + q_{1}) − p_{0} · q_{0} − p_{1} · q_{1})X^{n/2} + p_{0} · q_{0}

which is equal to p · q.

Since F is finite, arithmetic operations on coefficients are of constant cost, and so the complexity function is defined by the recurrence

T (1) = O(1), T (n) = 3T (n/2) + O(n)

which, by use of the Master Theorem, leads to T (n) = O(n^{log_{2} 3}) as desired.

Ex. (8) Given the following two polynomials over the integers:

u(x) = x^{6} + x^{5} − x^{4} + 2x^{3} + 3x^{2} − x + 2, v(x) = 2x^{3} + 2x^{2} − x + 3 ∈ ℤ[x].

We want to compute pseudo quotient and pseudo remainder of u and v.

2^{3} · ( x^{6} + x^{5} − x^{4} + 2x^{3} + 3x^{2} − x + 2) = v(x) · (4x^{3} − 2x + 4)
−(8x^{6} + 8x^{5} − 4x^{4} + 12x^{3})  + (14x^{2} + 2x + 4).
−4x^{4} + 4x^{3} + 24x^{2} − 8x + 16
−( −4x^{4} − 4x^{3} + 2x^{2} − 6x)
8x^{3} + 22x^{2} − 2x + 16
−( 8x^{3} + 8x^{2} − 4x + 12)
14x^{2} + 2x + 4

It turns out that

pquot(u, v) = 4x^{3} − 2x + 4,
prem(u, v) = 14x^{2} + 2x + 4.

Ex. (9) Evaluation of a polynomial at a certain point along the definition of the polynomial, i.e. evaluation of terms which are sumed up, takes O(n^{2}) multiplications: Evaluation of one term takes up to O(n) steps, and there are n terms. To sum up n terms, we need O(n) additions.

On the other hand, evaluation of a polynomial by Horner’s scheme takes only O(n) additions and multiplications: Both, the number of additions and multiplications satisfy the recurence relation

T (n) = T (n − 1) + O(1)

which clearly means T (n) = O(n).

Horner’s rule can be viewed as polynomial division by linear monic divisors. (However, it can also be generalized to non-linear divisors.) By direct evaluation, one sees that the parenteses evaluate to the coefficients of p(x)/(x − α). The remainder of this division is p(α).

(a_{n}x^{n} + a_{n−1}x^{n−1} + …) : (x − α) = a_{n}x^{n−1} + (a_{n−1} + αa_{n})x^{n−1} + …

Ex. (10) First, we compute p_{1} = a · b by the classical algorithm.

(α^{3} + α + 2) · (3α^{4}  + 2α^{2} − α)
3α^{7} + 3α^{5} + 6α^{4}
2α^{5}  + 2α^{3} + 4α^{2}
− α^{4}  − α^{2} − 2α
3α^{7} + 5α^{5} + 5α^{4} + 2α^{3} + 3α^{2} − 2α

Over ℚ[x]/(x^{5} − 3), this result reduces to

a · b = 5α^{4} + 2α^{3} + 12α^{2} − 2α + 15.

Now, we use MAPLE to compute c^{−1} using the extended Euclidian algorithm. This leads to

c^{−1} = \frac{1}{3691}(−128α^{4} + 281α^{3} − 69α^{2} + 411α + 280).

Finally, using again MAPLE, we find

(a · b)/c = \frac{1}{3691}(−1088α^{4} + 7925α^{3} + 4950α^{2} + 1648α + 20835).