banner

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

About me Research Publications Students Teaching Talks Links

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.

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