CECM | CAG | Department of Mathematics | SFU | MITACS | IRMACS | PIMS

About me Research Publications Students Teaching Talks Links

Topics in Computer Algebra, Summer 2015

We will meet in K9509 on Mondays and Wednesdays from 9:30-11:30pm.

To register for the course, please contact the Graduate secretary in Mathematics


  • The Fast Fourier Transform. (May 13 and 20)
    The FFT as a linear transformation.
    The radix 2 and radix 4 FFT.
    Fast multiplication and fast division.
    The Fast Euclidean algorithm.
  • Polynomial Interpolation. (May 25 and 27)
    Brown's GCD algorithm using dense interpolation.
    Zippel's sparse interpolation algorithm.
    Ben-Or and Tiwari sparse interpolation.
  • Symbolic Linear Algebra. (June 1 and 3)
    The Bareiss fraction-free algorithm for solving Ax=b over an integral domain.
    Rational number reconstruction and solving Ax=b over Q using p-adic lifting.
  • Algebraic Number Fields. (June 8 and 10)
    Minimal polynomials, norms, cyclotomic fields.
    The Trager-Kronecker algorithm for factoring polynomials in Q(alpha)[x].
    Cyclotomic fields and solving Ax=b over Q(alpha) using a modular method.
  • Polynomial Data Structures. (June 22 and 24)
    Multivariate polynomial representations and term orderings.
    Polynomial multiplication and division using heaps.
    The Kronecker substitution.


Here is a sample poster for you to use.
  poster (.tex) LaTeX file
  poster (.pdf) Sample .pdf
  poster (.zip) zip archive with figures (.pdf files)


We will use Maple for programming and calculations. The following Maple worksheet has some notes for programming in Maple: MapleNotes.mws


Five assigments worth 15% each plus a course project worth 25%.

p. (778) 782-4279 · f. (778) 782-4947 · Shrum Science K 10501 · Department of Mathematics · 8888 University Drive · Burnaby · BC · V5A 1S6 · Canada