Next: A review of complexity notions Up: An introduction to Computer Algebra Previous: Algebraic systems

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

Next: A review of complexity notions Up: An introduction to Computer Algebra Previous: Algebraic systems
Marc Moreno Maza
2003-06-06