*
*

- OBSERVATIONS.
- Computer algebra algorithms perform symbolic computations: numbers are manipulated by using their mathematical definitions.
- Hence results are exact and complete.
- However they can be huge!
- Moreover intermediate expressions may be much bigger than the input and output.

- OBJECTIVES.
- Our main interest will be here to study the implementation of algorithms
- that keep the swell of the intermediate expressions under control
- and offer
*optimal*time complexity.

- Sine this is obviously a vast subject we will focus on univariate polynomials, bivariate polynomials and matrix operations.
- But in fact these algorithms benefit to many other Computer algebra algorithms.

- Our main interest will be here to study the implementation of algorithms
- TYPICAL (TRIVIAL) EXAMPLE.
- Let and be two univariate polynomials over the integer numbers and with degrees and respectively such that .
- Suppose we want to decide whether divides .
- One can show that the division with remainder of by requires at most operations in the coefficient ring.
- If divides then for a given integer value of the integer divides .
- Computing and require operations in the coefficient ring.
- So trying whether divides (before computing the remainder of by ) will save time (and space) in the average.

*
*

2008-01-07