CS 424 / CS 556 - Foundations of Computational Algebra

University of Western Ontario
Computer Science 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. They form the foundation for all modern algorithms in Computer Algebra. This will be the main topic of this course. In particular, we will discuss

• Fast multiplication algorithms (FFT, Karatsuba, Strassen)
• Chinese remaindering algorithm
• Newton's iteration and Hensel lifting
• Fast Linear Algebra
• Polynomial gcds and resultants
• Factorization of Univariate Polynomials

Outlines.

This presents the contents of the course, its assignments, quizzes and projects. outline.html

Lectures.

There are based on the Modern Computer Algebra book and recent papers. Note that the set of topics covered in Winter 2006 will be different from that of Winter 2005. The notes from Winter 2005 appear below. Those chapters which will be covered also this Winter 2006 will be replaced by updated versions.

• Introduction.html
• Introduction.ps.gz
• EuclideanMethods.html
• EuclideanMethods.ps.gz
• FastMultiplication.html
• FastMultiplication.ps.gz
• FastDivisionAndGcd.html
• FastDivisionAndGcd.ps.gz
• Newton.html
• Newton.ps.gz
• Hensel.html
• Hensel.ps.gz
• ResultantGcd.html (TO BE UPDATED)
• ResultantGcd.ps.gz (TO BE UPDATED)

MAPLE Worksheets and AXIOM programs.

• Bareiss.mw
• firstContact.mw
• polynomials.input

Lecture topics (tentative schedule).

Week Jan. 9-15	Introduction to Computer Algebra
Week Jan. 16-22	The Euclidean Algorithm
Week Jan. 23-29	Modular Arithmetic
Week Jan. 30-5	Modular Computation
Week Feb. 6-12	Interpolation and Rational Reconstruction
Week Feb. 13-19	FFT and Fast Univariate Polynomial Multiplication
Week Feb. 20-26	FFT and Fast Univariate Polynomial Multiplication
Week Mar. 6-12	Fast Division and Fast Euclidean Algorithm
Week Mar. 13-19	Fast Division and Fast Euclidean Algorithm
Week Mar. 20-26	P-adic Expansions and Approximations
Week Mar. 27-2	Symbolic Newton Iteration
Week Apr. 3-9	Hensel Lifting
Week Apr. 10-16	Project Presentations

Assignments and projects for Winter 2006.

Assignment 1 (compressed postscript).	Assignment 1 (html pages).	Posted Jan. 20	Due Feb. 6
Assignment 2 (compressed postscript).	Assignment 2 (html pages).	Posted Feb. 8	Due Feb. 24
Assignment 3 (compressed postscript).	Assignment 3 (html pages).	Posted March. 2	Due Mar. 26
Project	Posted Mar. 17	Due Apr. 17

Quizzes from Winter 2006.

Quiz 1 (html pages). Quiz 1 (compressed postscript). Quiz 2 (html pages). Quiz 2 (compressed postscript). Quiz 3 (html pages). Quiz 3 (compressed postscript).

Quizzes from Winter 2005.

Quiz 1 (html pages). Quiz 1 (compressed postscript). Quiz 2 (html pages). Quiz 2 (compressed postscript). Quiz 3 (html pages). Quiz 3 (compressed postscript).

Assignments and Projects from Winter 2005.

Assignment 1 (html pages). Assignment 1 (compressed postscript). Project 1 (html pages). Project 1 (compressed postscript). Projects 2 (html pages). Projects 2 (compressed postscript).

Ressources.

These are links to some books and software related to the course.

• The Modern Computer Algebra book
• The Aldor web site
• The AXIOM Computer Algebra System at NAG ltd
• Doanload AXIOM

Some Papers on Fast Arithmetic

Fast Algorithms for Manipulating Formal Power Series by R.P. Brent and H.T. Kung

Practical Fast Polynomial Multiplication by Robert T.Moenck

Notes on the Truncated Fourier Transform by Joris van der Hoeven

A long note on Mulders' short product by G. Hanrot, P. Zimmermann