CS 424 / CS 556 - Foundations of Computational Algebra
University of Western Ontario
Computer Science Department
Date: Winter 2007
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.
Based on these techniques and by integrating advanced programming language features, Computer Algebra systems have become powerful tools for scientific computing, with applications in cryptography, robotics, theoretical physics and other areas.
In the last decade, the growing demand of speed, accuracy, and reliability in scientific and engineering computing has been accelerating the merging of symbolic and numeric computations, two types of computation coexisting in mathematics yet separated in traditional research of mathematical computation. This recent development adds a new strength to Computer Algebra systems and allow them to increase the range of their applications. This includes areas where experimental measurements (which are necessarily approximate values) are involved, such as biology, chemistry and economy.
The main topics of this course are listed below:
|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|
|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|