banner

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

About me Research Publications Students Teaching Talks Links

Topics in Computer Algebra, Summer 2013

We will meet in K9509 on Tuesdays and Thursdays from 9:30-11:30pm.

To register for the course, please contact Diane Pogue in Mathematics

Content

  • The Fast Fourier Transform.
    Fast multiplication and fast division.
    The Schoenhage-Strassen multiplication algorithm.
    The Fast Euclidean algorithm.
  • Polynomial Interpolation.
    Brown's GCD algorithm using dense interpolation.
    Zippel's sparse interpolation algorithm.
    Ben-Or and Tiwari sparse interpolation.
  • Symbolic Linear Algebra.
    The Bareiss fraction-free algorithm for solving Ax=b over an integral domain.
    Division free algorithms: minor expansion and the Berkowitz algorithms.
    Rational number reconstruction and solving Ax=b over Q using p-adic lifting.
  • Algebraic Number Fields.
    Minimal polynomials, norms, cyclotomic fields.
    The Trager-Kronecker algorithm for factoring polynomials in Q(alpha)[x].
    Solving Ax=b over Q(alpha) using a modular method.
  • Polynomial Data Structures.
    Polynomial multiplication and division using geobuckets.
    Polynomial multiplication and division using heaps.
    Generic data structures and generic coding.

Poster

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)

Maple

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

Assessment

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

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