CS 4424a/9556a: Foundations of Computational Algebra
Éric Schost, Computer Science Department
eschost@uwo.ca
Lectures: MC320, Wednesday, 9:30am - 12:30am
Office Hours: MC415, Monday and Tuesday, 9:30am - 11am
Phone: 519 661 2111 ext 86994 (e-mail contact preferred!)
Overview
Symbolic computation develops algorithms to manipulate
mathematical objects (numbers, matrices, polynomials, ...)
formally. This course provides an overview of a few fundamental
aspects, with an emphasis on the design of fast algorithms, and the
study of their complexity. Explicitly, we will discuss
- Fast multiplication algorithms for polynomials and integers,
- Euclid's algorithm,
- Newton iteration and Hensel lifting,
- Linear algebra and the LLL algorithm,
- Factorization of univariate polynomials (tentatively).
Course outline
Here.
Course material
- Quick introduction / Polynomial multiplication
- Euclidean division
- Newton iteration
- GCD and Euclid's algorithm
- Factorization (sketch)
News
-
Project papers are available.
-
Third assignment is available.
-
Second assignment is available.
-
First assignment is available.
-
Class on September 24th is cancelled.
References
The course's textbook is Modern Computer
Algebra, by Joachim von zur Gathen and Jürgen Gerhard.
Projects
You are to pick a project in the following list, or come up with a
personal one. If you want to work on a project not in the list, it
will be subject to my approval. The projects are individual, but I
have no objection to you picking the same project, as long as you work
individually.
The projects I give here are oriented towards litterature review.
You will read one paper; you will have to explain their content in
your own words. When the papers are long, I mostly want you to
understand and extract the main ideas, and present them by yourself;
you must coordinate with me to decide what part of the paper to
focus on.
You are to submit a written report of about 5 to 15 pages (quality
matters, not quantity), and give a presentation, followed by
questions.
- J. van der Hoeven,
the Truncated Fourier Transform and its applications, ISSAC'04, 2004.
- C. Koc, T. Acar,
Montgomery multiplication in GF(2^k), Designs, codes and cryptography, 14(1) 57-69, 1998
- P. Montgomery, Five, six and seven terms Karatsuba-like formulae.pdf, IEEE
Transactions on computers, 54(3), 362-369, 2005.
- T. Mulders,
On short multiplications and divisions, AAECC 11, 69-88, 2000.
- B. Sunar, A generalized method for consructing subquadratic complexity GF(2^k) multipliers, IEEE Transactions on computers, 53(9), 1097-1105, 2004.
Student evaluation and schedule
Grades will be based on
- 3 assignments, each worth 12% of the final mark
- a midterm exam, worth 24%
- a project, worth 40%.
Schedule
- Assignment 1: due September 24
- Assignment 2: due October 8
- Assignment 3: due October 22
- Midterm Exam: November 5
- Project: due December 3