Some applications of differential-difference algebra to creative telescoping - PASTEL - Thèses en ligne de ParisTech Accéder directement au contenu
Thèse Année : 2011

Some applications of differential-difference algebra to creative telescoping

Quelques applications de l'algébre différentielle et aux différences pour le télescopage créatif

Shaoshi Chen
  • Fonction : Auteur
  • PersonId : 895504

Résumé

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.
Depuis les années 90, la méthode de création télescopique de Zeilberger a joué un rôle important dans la preuve automatique d'identités mettant en jeu des fonctions spéciales. L'objectif de long terme que nous attaquons dans ce travail est l'obtension d'algorithmes et d'implantations rapides pour l'intégration et la sommation définies dans le cadre de cette création télescopique. Nos contributions incluent de nouveaux algorithmes pratiques et des critères théoriques pour tester la terminaison d'algorithmes existants. Sur le plan pratique, nous nous focalisons sur la construction de télescopeurs minimaux pour les fonctions rationnelles en deux variables, laquelle a de nombreuses applications en lien avec les fonctions algébriques et les diagonales de séries génératrices rationnelles. En considérant cette classe d'entrées contraintes, nous parvenons à mâtiner la méthode générale de création télescopique avec réduction bien connue d'Hermite, issue de l'intégration symbolique. En outre, nous avons obtenu pour cette sous-classe quelques améliorations des algorithmes classiques d'Almkvist et Zeilberger. Nos résultats expérimentaux ont montré que les algorithmes à base de réduction d'Hermite battent tous les autres algorithmes connus, à la fois en ce qui concerne la complexité au pire et en ce qui concerne les mesures de temps sur nos implantations. Sur le plan théorique, notre premier résultat est motivé par la conjecture de Wilf et Zeilberger au sujet des fonctions hyperexponentielles-hypergéométriques holonomes. Nous présentons un théorème de structure pour les fonctions hyperexponentielles-hypergéométriques de plusieurs variables, indiquant qu'une telle fonction peut s'écrire comme le produit de fonctions usuelles. Ce théorème étend à la fois le théorème d'Ore et Sato pour les termes hypergéométriques en plusieurs variables et le résultat récent par Feng, Singer et Wu. Notre second résultat est relié au problème de l'existence de télescopeurs. Dans le cas discret à deux variables, Abramov a obtenu un critère qui indique quand un terme hypergéométrique a un télescopeur. Des résultats similaires ont été obtenus pour le $q$-décalage par Chen, Hou et Mu. Ces résultats sont fondamentaux pour la terminaison des algorithmes s'inspirant de celui de Zeilberger. Dans les autres cas mixtes continus/discrets, nous avons obtenu deux critères pour l'existence de télescopeurs pour des fonctions hyperexponentielles-hypergéométriques en deux variables. Nos critères s'appuient sur une représentation standard des fonctions hyperexponentielles-hypergéométriques en deux variables, sur sur deux décompositions additives.
Fichier principal
Vignette du fichier
PhDThesis_Chen.pdf (771.75 Ko) Télécharger le fichier
Chen_Defense_Slides.pdf (273.4 Ko) Télécharger le fichier
Format : Autre

Dates et versions

pastel-00576861 , version 1 (15-03-2011)

Identifiants

  • HAL Id : pastel-00576861 , version 1

Citer

Shaoshi Chen. Some applications of differential-difference algebra to creative telescoping. Symbolic Computation [cs.SC]. Ecole Polytechnique X, 2011. English. ⟨NNT : ⟩. ⟨pastel-00576861⟩
254 Consultations
1324 Téléchargements

Partager

Gmail Facebook X LinkedIn More