Creative telescoping is a popular method for proving combinatorial identities and the computation of parametric integrals that involve special functions. Traditional implementations of this method admit an exponential bit complexity and it is an open problem under which conditions creative telescoping can be achieved in polynomial time. More efficient reduction-based algorithms were recently introduced in order to get a better grip on such complexity issues. Initially, reduction-based algorithms only applied to special cases such as rational, algebraic, or hyperexponential functions. More recently, constructions of reductions appeared for larger classes of Fuchsian D-finite and general differentially-finite functions.

In this paper, we show how to construct reductions for mixed differential-difference systems, where the difference operators are either shift operators or -difference operators. We recall how this yields an algorithm for creative telescoping and specify under which precise conditions on singularities this algorithm works. For creative telescoping of differential type, we next examine the complexity of our algorithms and prove a polynomial complexity bound. The algorithm for which this bound holds computes generators for a D-finite ideal of telescopers, but not necessarily a Gröbner basis for the ideal of all telescopers.

Keywords: creative telescoping, holonomic function, Hermite reduction, residues

View: Html, TeXmacs, Pdf, BibTeX