__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
*p*(*x*) and*q*(*x*) be two univariate polynomials over the integer numbers and with degrees*n*and*m*respectively such that*n*<*m*. - Suppose we want to decide whether
*p*(*x*) divides*q*(*x*). - One can show that the division with remainder of
*q*(*x*) by*p*(*x*) requires at most (2*m*+ 1)(*n*-*m*+ 1) operations in the coefficient ring. - If
*p*(*x*) divides*q*(*x*) then for a given integer value*x*_{0}of*x*the integer*p*(*x*_{0}) divides*q*(*x*_{0}). - Computing
*p*(*x*_{0}) and*q*(*x*_{0}) require 2*n*+ 2*m*+ 2 operations in the coefficient ring. - So trying whether
*p*(*x*_{0}) divides*q*(*x*_{0}) (before computing the remainder of*q*(*x*) by*p*(*x*)) will save time (and space) in the average.

- Let

2004-04-27