Skip to Main content Skip to Navigation

Some applications of differential-difference algebra to creative telescoping

Shaoshi Chen 1
1 ALGORITHMS - Algorithms
Inria Paris-Rocquencourt
Abstract : Since the 1990's, Zeilberger's method of creative telescoping has played an important role in the automatic verification of special-function identities. The long-term goal initiated in this work is to obtain fast algorithms and implementations for definite integration and summation in the framework of this method. Our contributions include new practical algorithms, complexity analyses of algorithms, and theoretical criteria for the termination of existing algorithms. On the practical side, we present a new algorithm for computing minimal telescopers for bivariate rational functions. This algorithm is based on Hermite reduction. We also improve the classical Almkvist and Zeilberger's algorithm for rational-function inputs. The Hermite-reduction based algorithm and improved Almkvist and Zeilberger's algorithm are analyzed in terms of field operations. Both complexity analysis and experimental results show that our algorithms are superior to other known ones for rational-function inputs. On the theoretic side, we present a structure theorem for multivariate hyperexponential-hypergeometric functions. This theorem is based on (multivariate) Christopher's theorem for hyperexponential functions, the Ore-Sato theorem for hypergeometric terms, and our generalization of a recent result by Feng, Singer, and Wu on compatible bivariate continuous-discrete rational functions. The structure theorem allows us to decompose a hyperexponential-hypergeometric function as a product of a rational function, several exponential and power functions, and factorial terms. Furthermore, we derive two criteria for the existence of telescopers for bivariate hyperexponential-hypergeometric functions: one is with respect to the continuous variable, and the other with respect to the discrete one. The two criteria solve the termination problem of the continuous-discrete analogue of Zeilberger's algorithms.
Document type :
Complete list of metadatas
Contributor : Shaoshi Chen <>
Submitted on : Tuesday, March 15, 2011 - 2:57:48 PM
Last modification on : Friday, May 25, 2018 - 12:02:05 PM
Long-term archiving on: : Thursday, June 16, 2011 - 3:00:36 AM


  • HAL Id : pastel-00576861, version 1



Shaoshi Chen. Some applications of differential-difference algebra to creative telescoping. Symbolic Computation [cs.SC]. Ecole Polytechnique X, 2011. English. ⟨pastel-00576861⟩



Record views


Files downloads