MATH 895-4 Reading for Summer 2019

 Title: Topics in Computer Algebra

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

 Lectures Tuesdays and Thursdays 9:30am-12:00 noon in BLU 10901

 Prerequisite: MACM 401 or MATH 701 or MATH 801.

 Instructor: Michael Monagan 
     Email: mmonagan@cecm.sfu.ca
     Office: K10501
     Phone: (778) 782 4279

 References
 
   o Modern Computer Algebra by von zur Gathen and Gerhard.
   o Algorithms for Computer Algebra by Geddes, Czapor and Labahn.

 Grading:
 
   Assignments       60%  (five assignments, one per topic).
   Course Project    40%  (presentation as a written report).

  For the Course Project students may choose a research problem
  from a list of pre-selected topics provided by the instructor,
  or a topic of their own choice in consultation with the instructor.
  The project will involve reading selected papers from the literature,
  implementing one or more algorithms, studying the mathematical
  basis for the algorithm(s), comparing algorithms both theoretically
  and experimentally and presenting their work as a report in LaTeX
  of between 15 and 20 pages in length.
 
Topics and Lecture Schedule
 
 1 The Fast Fourier Transform
   Lectures May 7, 9.  Assignment due May 20th.
   - The FFT as an affine transformation.
   - The polynomial Newton iteration.
   - Fast division using the FFT.
   - Fast multi-point evaluation using the FFT.

 2 Computational Linear Algebra
   Lectures May 14, 16, 21.  Assignment due May 29th
   - The Bareiss fraction-free algorithm for computing det(A) and solving Ax=b.
   - The Berkowitz division free algorithm for computing det(A - lambda I)
   - Solving Ax=b over Q using p-adic lifting + rational reconstruction.

 3 Multivariate Polynomial Interpolation  
   Lectures May 23, 28, 30.  Assignment due June 10th
   - Browns' algorithm for multivariate polynomial GCDs.
   - The Black Box model of computation.
   - Zippel's sparse interpolation.
   - Ben-Or/Tiwari sparse interpolation.
   - Rational function interpolation.

June 3-7 break

 4 Algebraic Number Fields
   Lectures June 11, 13.  Assignment due June 21st
   - Representation of elements in Q(alpha) and calculating norms.
   - The Trager-Kronecker algorithm for factoring polynomials in Q(alpha)[x].
   - A modular gcd algorithm for Q(alpha)[x]
   - Cyclotomic fields and solving Ax=b over Q(alpha).

 5 Polynomial Data Structures and Algorithms
   Lectures June 18, 20.  Assignment due July 5th
   - Multivariate polynomial representations and term orderings.
   - Polynomial multiplication and division using heaps.
   - The Kronecker substitution.

 6 Course Project and Additional Topics
   Lectures  June 25th, 27th.  Project due August 14th.
   - Course project selection.
   - Writing papers using LaTex.
   - Automatic Differentiation.
   - Multivariate Hensel Lifting.