**
**

**
University of Western Ontario
Computer Science Department
**

**Date:** September 7, 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.
**

**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:
**

*
*

- Overview of Computer Algebra and Computer Algebra systems.
- Fast polynomial multiplication algorithms (FFT, Karatsuba).
- Chinese remaindering algorithm.
- Newton's iteration and Hensel lifting.
- Exact Linear Algebra. Fast Linear Algebra.
- Polynomial gcds and resultants.

**Outlines.**- This presents the contents of the course, its assignments, quizzes and projects.
`outline.html` **Lectures.**- There are based on
`the`and recent papers. The notes from Winter 2005 to Winter 2007 appear below.*Modern Computer Algebra*book **MAPLE Worksheets and AXIOM programs.****Other useful documents.****Lecture topics (Winter 2008).**Week Jan. 7-13 Introduction to Computer Algebra Week Jan. 14-20 The Euclidean Algorithm Week Jan. 21-27 Modular Arithmetic Week Jan. 28-3 Modular Computation Week Feb. 4-10 Interpolation and Rational Reconstruction Week Feb. 11-17 FFT and Fast Univariate Polynomial Multiplication Week Feb. 18-24 FFT and Fast Univariate Polynomial Multiplication Week Mar. 3-9 Fast Division and Fast Euclidean Algorithm Week Mar. 10-16 Fast Division and Fast Euclidean Algorithm Week Mar. 17-23 P-adic Expansions and Approximations Week Mar. 24-30 Symbolic Newton Iteration Week Apr. 31-6 Hensel Lifting Week Apr. 7-13 Project Presentations **Assignments and projects for Winter 2008.**`Assignment 1 (compressed postscript).``Assignment 1 (html pages).`Posted Jan. 31 Due Feb. 14 `Assignment 2+3 (compressed postscript).``Assignment 2+3 (html pages).`Posted March. 18 Due April. 8 **Quizzes from Winter 2007.**`Quiz 1 (html pages).``Quiz 1 (compressed postscript).``Quiz 2 (html pages).``Quiz 2 (compressed postscript).`**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).``Quiz 4 (html pages).``Quiz 4 (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.
**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*Finite Field Linear Algebra Subroutines*by Jean-Guillaume Dumas, Thierry Gautier and Clément Pernet*Variations On Computing Reciprocals Of Power Series*by Arnold Schönage*Comparing Several GCD Algorithms*by Jebelean*Solving Sparse Linear Equations Over Finite Fields*by DOUGLAS H. WIEDEMANN*Simple Multivariate Polynomial Multiplication*by Victor Pan

*
*