banner

CECM | CAG | Department of Mathematics | SFU | MITACS | IRMACS | PIMS

About me Research Publications Students Teaching Talks Links

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.

p. (778) 782-4279 · f. (778) 782-4947 · Shrum Science K 10501 · Department of Mathematics · 8888 University Drive · Burnaby · BC · V5A 1S6 · Canada