Conclusions

• 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.
• 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 $(2m + 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.