# CS 4424a/9556a: Foundations of Computational Algebra

Éric Schost, Computer Science Department
eschost@uwo.ca

Lectures: MC-105B, 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

Here.

### Course material

• Quick introduction / Polynomial multiplication
• slides
• In the text: a subset of Chapter 8
• Euclidean division
• slides
• In the text: a subset of Chapter 9
• 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
• Hypergeometric summation
• slides
• In the text: nowhere, I think

### News, assignments, etc

• The first assignment is available here (due Sept. 25)
• The second assignment is available here (due Oct. 11). Because I was late on putting the assignment online, the submission date is postponed by 2 days, so it's a Friday.
• The third assignment is available here. (due Oct. 25, again a Friday)
• A few old midterms are here, here and here.
• Projects are uploaded.

### 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 25
• Assignment 2: due October 9
• Assignment 3: due October 23
• Midterm Exam: November 6
• Project: due December 4