Assignments
Assignment 1 (.pdf)
Assignment 2 (.pdf)
Assignment 3 (.pdf)
Assignment 4 (.pdf)
Assignment 5 (.pdf)
Notes for A5 (.mws)
Topics in Computer Algebra, Summer 2007
Meet, Wednesdays, 2:30-4:30pm, K9509
Content
- The fast Fourier transform, fast integer multiplication, and the fast Euclidean algorithm.
- Data structures for polynomial division: "dynamic arrays", "geo-buckets" and "pointer heaps".
- Sparse polynomial interpolation and its application to multivariate polynomial GCD computation.
- Rational number reconstruction, p-adic lifting and their application to solving Ax=b over the rationals.
- Computing with algebraic numbers, factoring polynomials and solving linear systems over algebraic number fields.
References
Algorithms for Computer Algebra by Geddes, Czapor and Labahn
Modern Computer Algebra by von zur Gathen and Gerhard
Polynomial division using dynamic arrays, heaps and packed exponent vectors by Monagan and Pearce.
Algorithms for the non-monic case of the sparse modular gcd algorithm by de Kleine, Monagan and Wittkopf.
Maximal Quotient Rational Reconstruction by Monagan.
Solving Linear Systems over Cyclotomic Fields by Chen and Monagan.