**
**

**
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`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.*Modern Computer Algebra*book **MAPLE Worksheets and AXIOM programs.****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.
**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

*
*

moreno 2009-09-11