CS 4424a/9556a: Foundations of Computational Algebra
Éric Schost, Computer Science Department
eschost@uwo.ca
Lectures: MC105B, Wednesday, 9:30am  12:30am
Office Hours: MC415, Tuesday, 9:30am  11:30am
Phone: 519 661 2111 ext 86994 (email 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 ReedSolomon codes
Course outline
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
 ReedSolomon 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.
 R. Bradshaw et al, Congruent numbers up to 1000000000000.
 R. W. Gosper, Decision procedure for indefinite hypergeometric summation.
 H. W. Lenstra, Jr., Factoring integers with elliptic curves.
 F. Bellard, Computation of 2700 billion decimal digits of Pi using a desktop computer.
 H. Fan and A. Hasan,
Comments on "Five, six, and seventerm Karatsubalike formulae",
IEEE Transactions on Computers, 56 (5), 2007.
 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) 5769, 1998
 T. Mulders,
On short multiplications and divisions, AAECC 11, 6988, 2000.
 H. Fan and A. Hasan, A New approach to subquadratic space complexity parallel multipliers for extended binary fields
 M. Bodrato and A. Zanoni, What about ToomCook matrices optimality?
 R. Brent and H. Kung, Fast algorithms for manipulating formal power series
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