McGill University - School of Computer Science

Algorithms Seminar 2005

Everybody is welcome!

DATE: Wednesday, February 23rd 2004.
TIME: 4:30 PM - 5:30 PM
PLACE: McConnell 320
TITLE: Space-efficient Evaluation of Hypergeometric Series
SPEAKER: Ethan Kim, University of Lethbridge, Canada

Hypergeometric series are used to approximate many important constants, such as $e$ and Apery's constant $\zeta (3)$. We consider the evaluation of the hypergeometric series
S(N)=\sum_{n=0}^{N-1} \frac{a(n)}{b(n)} \prod_{i=0}^n \frac{p(i)}{q(i)}
where $a$,$b$,$p$, and $q$ are polynomials with integer coefficients.

One traditional method to evaluate such series is binary splitting, a divide-and-conquer algorithm followed by integer division. However, the numerator and the denominator computed by binary splitting usually contain a very large common factor. In this talk, we describe how standard computer algebra techniques, including modular computation and rational reconstruction, can be used to overcome the shortcomings of the binary splitting method.

The space complexity of our algorithm is the same as a bound on size of the reduced numerator and denominator of the series approximation. We show that when our algorithm is applied to compute $\zeta(3)$, the memory requirement is significantly reduced compared to the binary splitting approach.

This work was done jointly with Howard Cheng, Barry Gergel from University of Lethbridge, and Eugene Zima from University of Waterloo.

mailing list info: