CS 4424a/9556a: Foundations of Computational Algebra
Éric Schost, Computer Science Department
eschost@uwo.ca
Lectures: TC 341, Wednesday, 9:30am - 12:30am
Office Hours: MC415, Tuesday, 9:30am - 11:30am
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,
- Applications to decoding Reed-Solomon codes
Course outline
Here.
Course material
- Quick introduction / Polynomial multiplication
- slides
- In the text: a subset of Chapter 8
- Euclidean division
- slides
and code
- In the text: a subset of Chapter 9
- For more on Sage, see here.
- Newton iteration
- slides
- In the text: only the iteration for inverse is covered, in Chapter 9
- GCD and Euclid's algorithm
- slides
- In the text: parts of Chapters 3, 4 and 11
- Sparse linear systems
- slides
- In the text: parts of Chapter 12
- Reed-Solomon codes
- slides
- In the text: parts of Chapter 7
- Matrix multiplication
- slides
- In the text: parts of Chapter 12
- The exponent of linear algebra
- slides
- In the text: parts of Chapter 12
News, assignments, etc
-
The first assignment is available
here (due Sept. 28)
-
The second assignment is available
here (due Oct. 12)
- No class on Wednesday, October 5. The second assignment is now due October 19.
-
The third assignment is available
here. (due Nov. 2nd)
Prerequisites
- Antirequisite(s): The former Computer Science 422a/b.
- Prerequisite(s): Registration in the fourth year of a module in Computer Science or in one of the Mathematical Sciences.
Unless you have either the prerequisites for this course or written
special permission from your Dean to enroll in it, you will be removed from
this course and it will be deleted from your record. This decision may not
be appealed. You will receive no adjustment to your fees in the event that
you are dropped from a course for failing to have the necessary prerequisites
References
The course's textbook is Modern Computer
Algebra, by Joachim von zur Gathen and Jürgen Gerhard.
Another useful text is Knuth's The Art of Computer Computer
Programming volume 2; part of the material is also in
Introduction to Algorithms, by Cormen, Leiserson, Rivest, Stein.
Projects
You will pick a project from a list I will provide, 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 several students picking the same project, as
long as they work individually.
The projects will be 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.
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 28
- Assignment 2: due October 12
- Assignment 3: due October 26
- Midterm Exam: November 2
- Project: due November 30