MITACS Seminar Series on Mathematics of Computer Algebra and Analysis

Fast arithmetic for triangular sets: from theory to practice.

Xin Li, University of Western Ontario

10:15am, Wednesday December 5th, 2007 in K9509.

Abstract: 

We study arithmetic operations for triangular families of polynomials,
concentrating on multiplication in dimension zero. By a suitable extension of
fast univariate Euclidean division, we obtain theoretical and practical
improvements over a direct recursive approach; for a family of special
cases, we reach quasi-linear complexity. The main outcome we have in
mind is the acceleration of higher-level algorithms, by interfacing our
low-level implementation with languages such as AXIOM or Maple.
We show the potential for huge speed-ups, by comparing two AXIOM
implementations of van Hoeij and Monagan's modular GCD algorithm.