MATH 895-4 Reading

 Title: Topics in Computer Algebra

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

 Lectures Tuesdays and Thursdays 9:30am-11:30am May 9 to July 6.

 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, worth 12% each).
   Course Project    40%  (presentation as a poster or 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 either as a poster
  at the department's anual symposium on mathematics and computation
  or as a report in LaTeX of between 10 and 15 pages in length.
 

Topics and Lecture Schedule
 
 1 The Fast Fourier Transform  
   Lectures May 9, 11. Assignment due May 18th.
   - The FFT as an affine transformation.
   - The radix 2 and radix 4 FFT.
   - The polynomial Newton iteration.
   - Application to fast division.

 2 Multivariate Polynomial Interpolation  
     Lectures May 16, 18, 23.  Assignment due June 1st.
   - Browns' algorithm for multivariate polynomial GCDs.
   - The Black Box model of computation.
   - Zippel's sparse interpolation.
   - Ben-Or and Tiwari sparse interpolation.

 3 Computational Linear Algebra  
     Lectures May 25, 30, June 1. Assignment due June 15th
   - 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.

June 5-9 break

 4 Algebraic Number Fields
   Lectures June 13, 15. Assignment due June 22nd
   - 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 20, 22. Assignment due July 6th
   - Multivariate polynomial representations and term orderings.
   - Polynomial multiplication and division using heaps.
   - The Kronecker substitution.

 6 Course Project and Additional Topics
     Lectures  July 4th, 6th
     Project due August 15th (August 17th is the last day of exams)
   - Automatic Differentiation
   - Course project selection