CS 874 - Advanced Computer Algebra:
Asymptotically Fast Methods for Exact Computations

University of Western Ontario
Computer Science Department

Date: September 11, 2009

Asymptotically fast methods for exact computations have been known for a quarter of a century. Unfortunately their impact on computer algebra systems has been reduced since it was believed that they were irrelevant in practice. In this course we show that careful programing and accurate experimentation can lead to a successful implementation of these methods permitting to overcome the size of magnitude of effective computations.

Comparing to the other Advanced Computer Algebra AM583, this course focusses complexity results and practical efficiency whereas the main concerns of CS874 are theoretical and algorithmic aspects.

Lectures.

Based on the Modern Computer Algebra book and recent papers, the course presented efficient methods for computing polynomial gcd and resultants.

• Introduction.html
• EuclideanMethods.html
• Newton2Hensel.html
• ResultantGcd.html

Ressources.

These are links to the book and software used for the course.

• The Modern Computer Algebra book
• The Aldor compiler web site
• The AXIOM Computer Algebra System at NAG ltd
• More about AXIOM
• Algebra and Complexity Theory by Madhu Sudan