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 polynomial 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₀ of x the integer p(x₀) divides q(x₀).
  • Computing p(x₀) and q(x₀) require 2 n + 2 m + 2 operations in the coefficient ring.
  • So trying whether p(x₀) divides q(x₀) (before computing the remainder of q(x) by p(x)) will save time (and space) in the average.