## Topics in Computer Algebra, Summer 2015

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

### Content

• The Fast Fourier Transform. (May 13 and 20)
The FFT as a linear transformation.
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.

## 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 · f. (778) 782-4947 · Shrum Science K 10501 · Department of Mathematics · 8888 University Drive · Burnaby · BC · V5A 1S6 · Canada