Next: About this document ...
AM 583 - Advanced Computer Algebra:
Modular Computations
University of Western Ontario
Applied Mathematics Department
Date: September 11, 2009
Symbolic computations manipulate numbers by using their mathematical definitions rather than using floating point approximations. Consequently, their results are exact, complete and can be made canonical. However they can be huge! Moreover, intermediate expressions may be much bigger than the input and output.
One of the main successes of the Computer Algebra community in the last 30 years is the discovery of algorithms, called modular methods, that allow to keep the swell of the intermediate expressions under control. Even better: these methods fit almost each of the intermediate values in a machine word. Without these methods, many applications of Computer Algebra would not be possible and the impact of Computer Algebra in the scientific community would be severely reduced.
Today, modular computations are well-developed, especially for univariate and bivariate polynomial arithmetic and for linear algebra. This will be the main topic of this course. In particular, we will discuss polynomial multiplication based on the fast Fourier transform, polynomial factorization, polynomial gcd computation and modular linear algebra.
Comparing to the other Advanced Computer Algebra CS874, this course focusses much more on the theoretical and algorithmic aspects whereas the main concerns of CS874 are complexity results and practical efficiency.