Creative telescoping using reductions - Laboratoire d'informatique de l'X (LIX) Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2018

Creative telescoping using reductions

Résumé

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 q-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.
Fichier principal
Vignette du fichier
redtel.pdf (633.05 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01773137 , version 1 (20-04-2018)
hal-01773137 , version 2 (08-06-2018)

Identifiants

  • HAL Id : hal-01773137 , version 1

Citer

Joris van der Hoeven. Creative telescoping using reductions. 2018. ⟨hal-01773137v1⟩
388 Consultations
118 Téléchargements

Partager

Gmail Facebook X LinkedIn More