Assignments
Assignment 1 (.pdf)
C code for FFT1 (.pdf)
C code for FFT2 (.pdf)
Assignment 2 (.pdf)
Assignment 3 (.pdf)
Assignment 4 (.pdf)
Assignment 5 (.pdf)
Project (.pdf)
Solutions
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
Content
- 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.
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%.
References
Algorithms for Computer Algebra by Geddes, Czapor and Labahn
Modern Computer Algebra by von zur Gathen and Gerhard
On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, W.S. Brown, 1971.
On the Design and Implementation of Brown’s Algorithm over the Integers and Number Fields, Monagan and Wittkopf, 2000.
Probabilistic algorithms for interpolating polynomials. by R. Zippel, 1979.
Interpolating polynomials from their values. by R. Zippel, 1990.
A Deterministic Algorithm for Interpolating Sparse Multivariate Polynomials by M. Ben-Or and P. Tiwari.
Example of Ben-Or/Tiwari algorithm Maple worksheet (.mw) and a (.pdf) version.
P-adic Reconstruction of Rational Numbers by Guy, Davenport and Wang.
Maximal Quotient Rational Reconstruction by Monagan.
Algebraic Factoring and Rational Function Integration by B. Trager.
Sparse Polynomial Arithmetic by Stephen Johnson.
Analysis of Algorithms, A Case Study: Determinants of Matrices with Polynomial Entries by Gentleman and Johnson
Lazy and Forgetful Polynomial Arithmetic and Applications by Vrbik and Monagan.