Search

Indefinite summation essentially deals with the problem of inverting the difference operator Δ: f ( X ) → f ( X + 1) - f ( X ). In the case of rational functions over a field k we consider the following version of the problem: given α ϵ k ( X ), determine β, γ ϵ k ( X ) such that α = Δβ+γ, where γ is as "small" as possible (in a suitable sense). In particular, we address the question: what can be said about the denominators of a solution (β, γ) by looking at the denominator of α only? An "optimal" answer to this question can be given in terms of the Gosper-Petkovsek representation for rational functions, which was originally invented for the purpose of indefinite hypergeometric summation. This information can be used to construct a simple new algorithm for the rational summation problem.

The problem of computing a closed form for sums of special functions arises in many parts of mathematical and computer science, especially in combinatorics and complexity analysis. Here we discuss two algorithms for indefinite summation of rational functions, due to Abramov (1975) and Paule (1993). We describe some improvements and a parallel implementation on a workstation network in ‖ MAPLE ‖ (read: parallel Maple). Our best implementation achieves a speedup of up to eight over the fastest available sequential implementation. Finally, further applications of parallel computing in this field are outlined.