#### Assignments

Assignment 1 (.pdf)

Assignment 2 (.pdf)

Assignment 3 (.pdf)

Assignment 4 (.pdf)

Assignment 5 (.pdf)

## Topics in Computer Algebra, Summer 2009

Meet, Wednesdays, 3:30-5:00pm, K9509

### Content

- Applications of the Fast Fourier Transform: fast integer multiplication the fast Euclidean algorithm.
- Sparse polynomial multiplication and division using geobuckets and heaps.
- Algebraic number fields: minimal polynomials, norms, cyclotomic fields. The Trager-Kronecker algorithm for factoring polynomials in Q(alpha)[x].
- Computing multivariate polynomial GCDs over the integers:

- Brown's dense interpolation algorithm and

- Zippel's sparse interpolation algorithm. - Introduction to computational linear algebra:

- 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
*Polynomial division using dynamic arrays, heaps and packed exponent vectors* by Monagan and Pearce.
*Algebraic Factoring and Rational Function Integration* by B. Trager.
*Maximal Quotient Rational Reconstruction* by Monagan.