Assignments
Assignment 1 (.pdf)
Assignment 2 (.pdf)
Assignment 3 (.pdf)
Assignment 4 (.pdf)
Assignment 5 (.pdf)
Topics in Computer Algebra, Summer 2011
Meet, Wednesdays, 9:30-11:30pm, K9509
Content
- May 12. Applications of the Fast Fourier Transform:
Fast multiplication, fast division and the fast Euclidean algorithm. - May 25. Sparse polynomial multiplication and division using geobuckets and heaps.
- June 7. Computing over Algebraic Number Fields.
- Minimal polynomials, norms, cyclotomic fields.
- The Trager-Kronecker algorithm for factoring polynomials in Q(alpha)[x]. - Sparse polynomial interpolation and computing multivariate polynomial GCDs over the integers.
- Brown's GCD algorithm using dense interpolation.
- Zippel's sparse interpolation algorithm.
- Ben-Or/Tiwari sparse interpolation. - Introduction to computational linear algebra and rational reconstruction.
- 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.
References
Algorithms for Computer Algebra by Geddes, Czapor and Labahn
Modern Computer Algebra by von zur Gathen and Gerhard
Sparse Polynomial Arithmetic by Stephen Johnson.
Polynomial division using dynamic arrays, heaps and packed exponent vectors by Monagan and Pearce.
Algebraic Factoring and Rational Function Integration by B. Trager.
A Deterministic Algorithm for Interpolating Sparse Multivariate Polynomials by M. Ben-Or and P. Tiwari.
Maximal Quotient Rational Reconstruction by Monagan.