MATH 895-4 Reading Fall 2021

 Title: Topics in Computer Algebra
 Prerequisite: MACM 401 or MATH 701 or MATH 801.
 Lectures: Thursdays 9:30am to 11:30am and Fridays 10:30am to 12:30pm

 Course Webpage: http://www.cecm.sfu.ca/~mmonagan/teaching/TopicsinCA21

 Instructor: Michael Monagan   mmonagan@sfu.ca
 Office: K10501  Phone: (778) 782 4279
 Office hours: Tuesdays 3pm-5pm 

 Course Outline
 
 1 The FFT and Fast Polynomial Arithmetic.
   o Two versions of the FFT.  The FFT as an affine transformation.
   o Fast division.  Fast multi-point evaluation.
   September 9, 10

 2 Data Structures and Algorithms for Multivariate Polynomials.
   o Term orderings and division.  Multivariate polynomial data structures.
   o Polynomial multiplication and division using binary heaps.
   September 16, 17

 3 Computational Exact Linear Algebra
   o The Gentleman-Johnson minor expansion algorithm for computing det(A).
   o The Bareiss-Edmonds fraction-free algorithm for computing det(A).
   o Solving Ax=b over Q using p-adic lifting and rational reconstruction.
   o The Berkowitz division free algorithm for computing det(A - lambda I).
   September 23, 24, Oct 1  (no class on September 30th)

 4 Multivariate Polynomial Interpolation
   o Brown's dense modular GCD algorithm for Z[x1,...,xn].
   o Sparse polynomials.  Black box representations.  The Schwartz-Zippel Lemma.
   o Zippel's sparse interpolation.  Polynomial GCD computation.
   o Ben-Or Tiwari sparse interpolation.  Discrete logarithms.
   October 7, 8, 14, 15
 
 5 Groebner Bases and Applications  (new for 2021)
   o Ideals in polynomial rings, varieties in affine space, and their relationship.
   o Monomial orderings.  Ideal membership and polynomial division.  
   o Dickson's lemma and the Hilbert basis theorem.  
   o Groebner bases and Buchberger's algorithm.
   o The elimination theorem.  Applications.  Groebner bases in Maple.
   October 21, 22, 28, 29

Grading:
 
  Assignments      60%  (five assignments, one per topic, 12% each).
  Course Project   40%
 
References and Reading List
 
   o Modern Computer Algebra by von zur Gathen and Gerhard.
   o Algorithms for Computer Algebra by Geddes, Czapor and Labahn.
   o Ideals, Varieties and Algorithms by Cox, Little and O'Shea.
   o Research papers for some specific topics.

Course Project

For the Course Project students may choose a research problem from a list of pre-selected
topics provided by the instructor.  The project will involve reading selected paper(s)
from the literature, implementing one or more algorithms, studying the mathematical basis
for the algorithm(s) and comparing algorithms theoretically and/or experimentally.