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