#### 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.
*