Creative Telescoping for Parametrised Integration and Summation
Journées Nationales de Calcul Formel. 14 – 18 Novembre 2011, Les cours du CIRM, no. 1 (2011), Talk no. 2, 37 p.
DOI: 10.5802/ccirm.14
Chyzak, Frédéric 1

1 INRIA (France)
@article{CCIRM_2011__2_1_A2_0,
     author = {Chyzak, Fr\'ed\'eric},
     title = {Creative {Telescoping} for {Parametrised} {Integration} and {Summation}},
     booktitle = {Journ\'ees Nationales de Calcul Formel. 14 {\textendash} 18 Novembre 2011},
     series = {Les cours du CIRM},
     note = {talk:2},
     pages = {1--37},
     publisher = {CIRM},
     number = {1},
     year = {2011},
     doi = {10.5802/ccirm.14},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/ccirm.14/}
}
TY  - JOUR
AU  - Chyzak, Frédéric
TI  - Creative Telescoping for Parametrised Integration and Summation
BT  - Journées Nationales de Calcul Formel. 14 – 18 Novembre 2011
AU  - Collectif
T3  - Les cours du CIRM
N1  - talk:2
PY  - 2011
SP  - 1
EP  - 37
IS  - 1
PB  - CIRM
UR  - http://www.numdam.org/articles/10.5802/ccirm.14/
DO  - 10.5802/ccirm.14
LA  - en
ID  - CCIRM_2011__2_1_A2_0
ER  - 
%0 Journal Article
%A Chyzak, Frédéric
%T Creative Telescoping for Parametrised Integration and Summation
%B Journées Nationales de Calcul Formel. 14 – 18 Novembre 2011
%A Collectif
%S Les cours du CIRM
%Z talk:2
%D 2011
%P 1-37
%N 1
%I CIRM
%U http://www.numdam.org/articles/10.5802/ccirm.14/
%R 10.5802/ccirm.14
%G en
%F CCIRM_2011__2_1_A2_0
Chyzak, Frédéric. Creative Telescoping for Parametrised Integration and Summation, in Journées Nationales de Calcul Formel. 14 – 18 Novembre 2011, Les cours du CIRM, no. 1 (2011), Talk no. 2, 37 p. doi : 10.5802/ccirm.14. http://www.numdam.org/articles/10.5802/ccirm.14/

[1] Abramov, S. A. Applicability of Zeilberger’s algorithm to hypergeometric terms, Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, New York (2002), p. 1-7 (electronic) | DOI

[2] Abramov, S. A. When does Zeilberger’s algorithm succeed?, Adv. in Appl. Math., Volume 30 (2003) no. 3, pp. 424-441 | DOI

[3] Abramov, S. A. Rational solutions of linear differential and difference equations with polynomial coefficients, U.S.S.R. Comput. Math. and Math. Phys., Volume 29 (1991) no. 6, pp. 7-12 Translation from Zh. Vychisl. Mat. i Mat. Fiz. 29(11), 1611–1620 (1989)

[4] Abramov, S. A. Rational solutions of linear difference and q-difference equations with polynomial coefficients, Program. Comput. Software, Volume 21 (1995) no. 6, pp. 273-278 Translation from Programmirovanie 6, 3–11 (1995)

[5] Abramov, S. A.; Le, H. Q. Applicability of Zeilberger’s algorithm to rational functions, Formal power series and algebraic combinatorics (Moscow, 2000), Springer, Berlin, 2000, pp. 91-102

[6] Abramov, S. A.; Le, H. Q. A criterion for the applicability of Zeilberger’s algorithm to rational functions, Discrete Math., Volume 259 (2002) no. 1-3, pp. 1-17 | DOI

[7] Abramov, S. A.; Petkovšek, M. On the structure of multivariate hypergeometric terms, Adv. in Appl. Math., Volume 29 (2002) no. 3, pp. 386-411 | DOI

[8] Apagodu, Moa The sharpening of Wilf-Zeilberger theory, ProQuest LLC, Ann Arbor, MI, 2006 Thesis (Ph.D.)–Rutgers The State University of New Jersey - New Brunswick

[9] Askey, Richard The world of q, CWI Quarterly, Volume 5 (1992) no. 4, pp. 251-269

[10] Apagodu, Moa; Zeilberger, Doron Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory, Adv. in Appl. Math., Volume 37 (2006) no. 2, pp. 139-152 | DOI

[11] Almkvist, Gert; Zeilberger, Doron The method of differentiating under the integral sign, J. Symbolic Comput., Volume 10 (1990) no. 6, pp. 571-591

[12] Bostan, Alin; Chyzak, Frédéric; Lairez, Pierre 3 pages. In preparation, 2011

[13] Bostan, Alin; Chyzak, Frédéric; van Hoeij, Mark; Pech, Lucien Explicit formula for the generating series of diagonal 3D rook paths, Sém. Loth. Comb. (2011) (27 pp. Accepted)

[14] Bernšteĭn, I. N. Modules over a ring of differential operators. An investigation of the fundamental solutions of equations with constant coefficients, Funkcional. Anal. i Priložen., Volume 5 (1971) no. 2, pp. 1-16

[15] Bernšteĭn, I. N. Analytic continuation of generalized functions with respect to a parameter, Funkcional. Anal. i Priložen., Volume 6 (1972) no. 4, pp. 26-40

[16] Böing, Harald; Koepf, Wolfram Algorithms for q-hypergeometric summation in computer algebra, J. Symbolic Comput., Volume 28 (1999) no. 6, pp. 777-799 (Orthogonal polynomials and computer algebra) | DOI

[17] Blodgelt, R. J. Problem E3376, Amer. Math. Monthly (1990)

[18] Bronstein, Manuel; Petkovšek, Marko Ore rings, linear operators and factorization, Programmirovanie (1994) no. 1, pp. 27-44

[19] Bronstein, Manuel; Petkovšek, Marko An introduction to pseudo-linear algebra, Theoret. Comput. Sci., Volume 157 (1996) no. 1, pp. 3-33 Algorithmic complexity of algebraic and geometric models (Creteil, 1994) | DOI

[20] Chen, Shaoshi; Chyzak, Frédéric; Feng, Ruyong; Li, Ziming On the Existence of Telescopers for Hyperexponential-Hypergeometric Sequences (2011) (21 pages. In preparation)

[21] Chen, Shaoshi Some applications of differential-difference algebra to creative telescoping, École polytechnique, February (2011) (Ph. D. Thesis)

[22] Chen, William Y. C.; Hou, Qing-Hu; Mu, Yan-Ping Applicability of the q-analogue of Zeilberger’s algorithm, J. Symbolic Comput., Volume 39 (2005) no. 2, pp. 155-170 | DOI

[23] Chyzak, Frédéric An extension of Zeilberger’s fast algorithm to general holonomic functions, Discrete Math., Volume 217 (2000) no. 1-3, pp. 115-134 Formal power series and algebraic combinatorics (Vienna, 1997)

[24] Chyzak, Frédéric Fonctions holonomes en calcul formel, École polytechnique (1998) http://algo.inria.fr/chyzak/Publications/these.ps (Ph. D. Thesis INRIA, TU 0531. 227 pages.)

[25] Chyzak, Frédéric Gröbner bases, symbolic summation and symbolic integration, Gröbner bases and applications (Linz, 1998) (London Math. Soc. Lecture Note Ser.), Volume 251, Cambridge Univ. Press, Cambridge, 1998, pp. 32-60

[26] Chyzak, Frédéric; Kauers, Manuel; Salvy, Bruno A non-holonomic systems approach to special function identities, ISSAC 2009—Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2009, pp. 111-118

[27] Chyzak, F.; Quadrat, A.; Robertz, D. Effective algorithms for parametrizing linear control systems over Ore algebras, Appl. Algebra Engrg. Comm. Comput., Volume 16 (2005) no. 5, pp. 319-376

[28] Chen, William Y. C.; Sun, Lisa H. Extended Zeilberger’s algorithm for identities on Bernoulli and Euler polynomials, J. Number Theory, Volume 129 (2009) no. 9, pp. 2111-2132 | DOI

[29] Chyzak, Frédéric; Salvy, Bruno Non-commutative elimination in Ore algebras proves multivariate identities, J. Symbolic Comput., Volume 26 (1998) no. 2, pp. 187-227

[30] Doetsch, Gustav Integraleigenschaften der Hermiteschen Polynome, Math. Z., Volume 32 (1930) no. 1, pp. 587-599 | DOI

[31] Ekhad, Shalosh B.; Zeilberger, Doron A high-school algebra, “formal calculus”, proof of the Bieberbach conjecture [after L. Weinstein], Jerusalem combinatorics ’93 (Contemp. Math.), Volume 178, Amer. Math. Soc., Providence, RI, 1994, pp. 113-115

[32] Ekhad, Shalosh B.; Zeilberger, Doron A WZ proof of Ramanujan’s formula for π, Geometry, Analysis, and Mechanics (Rassias, J. M., ed.), World Scientific, Singapore, 1994, pp. 107-108

[33] Ekhad, Shalosh B.; Zeilberger, Doron The number of solutions of X 2 =0 in triangular matrices over GF(q), Electron. J. Combin., Volume 3 (1996) no. 1, Research Paper 2, 2 pp. pages http://www.combinatorics.org/Volume_3/Abstracts/v3i1r2.html

[34] Fasenmyer, Mary Celine Some generalized hypergeometric polynomials, University of Michigan (1945) (Ph. D. Thesis)

[35] Fasenmyer, Mary Celine A note on pure recurrence relations, Amer. Math. Monthly, Volume 56 (1949), pp. 14-17

[36] Galligo, André Some algorithmic questions on ideals of differential operators, EUROCAL ’85, Vol. 2 (Linz, 1985) (Lecture Notes in Comput. Sci.), Volume 204, Springer, Berlin, 1985, pp. 413-421

[37] Gessel, Ira M. Applications of the classical umbral calculus, Algebra Universalis, Volume 49 (2003) no. 4, pp. 397-434 (Dedicated to the memory of Gian-Carlo Rota) | DOI

[38] Gel’fand, I. M.; Graev, M. I.; Retakh, V. S. General hypergeometric systems of equations and series of hypergeometric type, Russian Math. Surveys, Volume 47 (1992) no. 4, pp. 1-88 Translation from Uspekhi Matematicheskikh Nauk 47(4(286)), 3–82 | DOI

[39] Guo, Qiang-Hui; Hou, Qing-Hu; Sun, Lisa H. Proving hypergeometric identities by numerical verifications, J. Symbolic Comput., Volume 43 (2008), pp. 895-907

[40] Glasser, M. L.; Montaldi, E. Some integrals involving Bessel functions, J. Math. Anal. Appl., Volume 183 (1994) no. 3, pp. 577-590 | DOI

[41] Gosper, R. William Jr. Decision procedure for indefinite hypergeometric summation, Proc. Nat. Acad. Sci. U.S.A., Volume 75 (1978) no. 1, pp. 40-42

[42] Hornegger, Joachim Hypergeometrische Summation und polynomiale Rekursion, Universität Erlangen–Nürnberg (1992) (Diplomarbeit)

[43] Hou, Qing-Hu k-free recurrences of double hypergeometric terms, Adv. in Appl. Math., Volume 32 (2004) no. 3, pp. 468-484 | DOI

[44] Jacobson, N. Pseudo-linear transformations, Ann. of Math. (2), Volume 38 (1937) no. 2, pp. 484-507 | DOI

[45] Kashiwara, Masaki On the holonomic systems of linear differential equations. II, Invent. Math., Volume 49 (1978) no. 2, pp. 121-135 | DOI

[46] Kauers, Manuel Summation algorithms for Stirling number identities, J. Symbolic Comput., Volume 42 (2007) no. 10, pp. 948-970 | DOI

[47] Koornwinder, Tom H. On Zeilberger’s algorithm and its q-analogue, Proceedings of the Seventh Spanish Symposium on Orthogonal Polynomials and Applications (VII SPOA) (Granada, 1991), Volume 48 (1993) no. 1-2, pp. 91-111 | DOI

[48] Koutschan, Christoph A fast approach to creative telescoping, Math. Comput. Sci., Volume 4 (2010) no. 2-3, pp. 259-266 | DOI

[49] Kandri-Rody, A.; Weispfenning, V. Noncommutative Gröbner bases in algebras of solvable type, J. Symbolic Comput., Volume 9 (1990) no. 1, pp. 1-26

[50] Le, Kha On the q-analogue of Zeilberger’s algorithm for rational functions, Programmirovanie (2001) no. 1, pp. 49-58 | DOI

[51] Lipshitz, L. The diagonal of a D-finite power series is D-finite, J. Algebra, Volume 113 (1988) no. 2, pp. 373-378

[52] Lipshitz, L. D-finite power series, J. Algebra, Volume 122 (1989) no. 2, pp. 353-373

[53] Majewicz, John E. WZ-style certification and Sister Celine’s technique for Abel-type sums, J. Differ. Equations Appl., Volume 2 (1996) no. 1, pp. 55-65 | DOI

[54] Majewicz, John E. WZ certification of Abel-type identities and Askey’s positivity conjecture, ProQuest LLC, Ann Arbor, MI, 1997 Thesis (Ph.D.)–Temple University

[55] Mohammed, Mohamud; Zeilberger, Doron Sharp upper bounds for the orders of the recurrences output by the Zeilberger and q-Zeilberger algorithms, J. Symbolic Comput., Volume 39 (2005) no. 2, pp. 201-207 | DOI

[56] Nakayama, Hiromasa; Nishiyama, Kenta An algorithm of computing inhomogeneous differential equations for definite integrals, Proceedings of the Third international congress conference on Mathematical software (ICMS’10), Springer-Verlag, Berlin, Heidelberg (2010), pp. 221-232 http://dl.acm.org/citation.cfm?id=1888390.1888442

[57] Oaku, Toshinori Algorithms for integrals of holonomic functions over domains defined by polynomial inequalities, http://arxiv.org/abs/1108.4853v1, 2011 (29 pages)

[58] Oaku, Toshinori An algorithm of computing b-functions, Duke Math. J., Volume 87 (1997) no. 1, pp. 115-132 | DOI

[59] Ore, Oystein Sur les fonctions hypergéométriques de plusieurs variables, Comptes Rendus des Séances de l’Académie des Sciences, Volume 189 (1929), pp. 1238-1241

[60] Ore, Oystein Sur la forme des fonctions hypergéométriques de plusieurs variables, Journal de Mathématiques Pures et Appliquées, Volume 9 (1930) no. 9, pp. 311-326

[61] Ore, Oystein Linear equations in non-commutative fields, Ann. of Math. (2), Volume 32 (1931) no. 3, pp. 463-477 | DOI

[62] Ore, Oystein Theory of non-commutative polynomials, Ann. of Math. (2), Volume 34 (1933) no. 3, pp. 480-508 | DOI

[63] Oaku, Toshinori; Takayama, Nobuki Algorithms for D-modules—restriction, tensor product, localization, and local cohomology groups, J. Pure Appl. Algebra, Volume 156 (2001) no. 2-3, pp. 267-308 | DOI

[64] Oaku, Toshinori; Takayama, Nobuki Integrals of modules and their applications, Sūrikaisekikenkyūsho Kōkyūroku (1998) no. 1038, pp. 163-169 Research on the theory and applications of computer algebra (Japanese) (Kyoto, 1997)

[65] Oaku, Toshinori; Takayama, Nobuki; Walther, Uli A localization algorithm for D-modules, J. Symbolic Comput., Volume 29 (2000) no. 4-5, pp. 721-728 Symbolic computation in algebra, analysis, and geometry (Berkeley, CA, 1998) | DOI

[66] Paule, Peter Greatest factorial factorization and symbolic summation, J. Symbolic Comput., Volume 20 (1995) no. 3, pp. 235-268 | DOI

[67] Paule, Peter; Riese, Axel A Mathematica q-analogue of Zeilberger’s algorithm based on an algebraically motivated approach to q-hypergeometric telescoping, Special functions, q-series and related topics (Toronto, ON, 1995) (Fields Inst. Commun.), Volume 14, Amer. Math. Soc., Providence, RI, 1997, pp. 179-210

[68] Prodinger, Helmut Descendants in heap ordered trees, or, A triumph of computer algebra, Electron. J. Combin., Volume 3 (1996) no. 1, Research Paper 29, 9 pp. pages http://www.combinatorics.org/Volume_3/Abstracts/v3i1r29.html

[69] Paule, Peter; Schorn, Markus A Mathematica version of Zeilberger’s algorithm for proving binomial coefficient identities, J. Symbolic Comput., Volume 20 (1995) no. 5-6, pp. 673-698 Symbolic computation in combinatorics Δ 1 (Ithaca, NY, 1993) | DOI

[70] Piessens, R.; Verbaeten, P. Numerical solution of the Abel integral equation, Nordisk Tidskr. Informationsbehandling (BIT), Volume 13 (1973), pp. 451-457

[71] Rainville, Earl D. Special functions, The Macmillan Co., New York, 1960

[72] Riese, Axel Fine-tuning Zeilberger’s algorithm. The methods of automatic filtering and creative substituting, Symbolic computation, number theory, special functions, physics and combinatorics (Gainesville, FL, 1999) (Dev. Math.), Volume 4, Kluwer Acad. Publ., Dordrecht, 2001, pp. 243-254

[73] Riese, Axel qMultiSum—a package for proving q-hypergeometric multiple summation identities, J. Symbolic Comput., Volume 35 (2003) no. 3, pp. 349-376 | DOI

[74] Riese, Axel A generalization of Gosper’s algorithm to bibasic hypergeometric summation, Electron. J. Combin., Volume 3 (1996) no. 1, Research Paper 19, 16 pp. pages http://www.combinatorics.org/Volume_3/Abstracts/v3i1r19.html

[75] Sato, Mikio Theory of prehomogeneous vector spaces (algebraic part)—the English translation of Sato’s lecture from Shintani’s note, Nagoya Math. J., Volume 120 (1990), pp. 1-34 http://projecteuclid.org/getRecord?id=euclid.nmj/1118782193 (Notes by Takuro Shintani, Translated from the Japanese by Masakazu Muro)

[76] Saito, Mutsumi; Sturmfels, Bernd; Takayama, Nobuki Gröbner deformations of hypergeometric differential equations, Algorithms and Computation in Mathematics, 6, Springer-Verlag, Berlin, 2000

[77] Sturmfels, Bernd; Takayama, Nobuki Gröbner bases and hypergeometric functions, Gröbner bases and applications (Linz, 1998) (London Math. Soc. Lecture Note Ser.), Volume 251, Cambridge Univ. Press, Cambridge, 1998, pp. 246-258

[78] Stanley, R. P. Differentiably finite power series, European J. Combin., Volume 1 (1980) no. 2, pp. 175-188

[79] Stanley, Richard P. Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999

[80] Strehl, Volker Binomial identities—combinatorial and algorithmic aspects, Discrete Math., Volume 136 (1994) no. 1-3, pp. 309-346 (Trends in discrete mathematics) | DOI

[81] Sylvester, James Joseph A method of determining by mere inspection the derivatives from two equations of any degree, Philosophical Magazine, Volume XVI (1840), pp. 132-135 Available from his Collected Mathematical Pepers (http://www.archive.org/details/collectedmathema00sylv).

[82] Takayama, Nobuki Gröbner basis and the problem of contiguous relations, Japan J. Appl. Math., Volume 6 (1989) no. 1, pp. 147-160 | DOI

[83] Takayama, Nobuki An algorithm of constructing the integral of a module — an infinite dimensional analog of Gröbner basis, Symbolic and Algebraic Computation, ACM and Addison-Wesley (1990), pp. 206-211 Proceedings of ISSAC’90 (Kyoto, Japan)

[84] Takayama, Nobuki Gröbner basis, integration and transcendental functions, Symbolic and Algebraic Computation, ACM and Addison-Wesley (1990), pp. 152-156 Proceedings of ISSAC’90 (Kyoto, Japan)

[85] Takayama, Nobuki An approach to the zero recognition problem by Buchberger algorithm, J. Symbolic Comput., Volume 14 (1992) no. 2-3, pp. 265-282

[86] Tefera, Akalu Improved algorithms and implementations in the multi-WZ theory, ProQuest LLC, Ann Arbor, MI, 2000 Thesis (Ph.D.)–Temple University

[87] Tefera, Akalu MultInt, a MAPLE package for multiple integration by the WZ method, J. Symbolic Comput., Volume 34 (2002) no. 5, pp. 329-353 | DOI

[88] Tsai, Harrison Weyl closure of a linear differential operator, J. Symbolic Comput., Volume 29 (2000) no. 4-5, pp. 747-775 Symbolic computation in algebra, analysis, and geometry (Berkeley, CA, 1998) | DOI

[89] Tsai, Harrison Algorithms for associated primes, Weyl closure, and local cohomology of D-modules, Local cohomology and its applications (Guanajuato, 1999) (Lecture Notes in Pure and Appl. Math.), Volume 226, Dekker, New York, 2002, pp. 169-194

[90] van der Poorten, Alfred A proof that Euler missed...Apéry’s proof of the irrationality of ζ(3), Math. Intelligencer, Volume 1 (1979) no. 4, pp. 195-203 (An informal report) | DOI

[91] Verbaeten, Petrus The automatic construction of pure recurrence relations, Proceedings of Eurosam 74, Sigsam Bulletin (1974), pp. 96-98 https://lirias.kuleuven.be/handle/123456789/132545

[92] Verbaeten, Pierre Rekursiebetrekkingen voor lineaire hypergeometrische funkties, Department of Computer Science, K. U. Leuven, Leuven, Belgium (1976) (Ph. D. Thesis 239 pp.)

[93] Wegschaider, Kurt Computer generated proofs of binomial multi-sum identities, RISC, J. Kepler University, May (1997) (Diplomarbeit 99 pp.)

[94] Wilf, Herbert S.; Zeilberger, Doron An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities, Invent. Math., Volume 108 (1992) no. 3, pp. 575-633

[95] Wilf, Herbert S.; Zeilberger, Doron Rational function certification of multisum/integral/“q” identities, Bull. Amer. Math. Soc. (N.S.), Volume 27 (1992) no. 1, pp. 148-153

[96] Yen, Lily Contributions to the proof theory of hypergeometric identities, University of Pennsylvania (1993) (Ph. D. Thesis)

[97] Yen, Lily A two-line algorithm for proving terminating hypergeometric identities, J. Math. Anal. Appl., Volume 198 (1996) no. 3, pp. 856-878 | DOI

[98] Yen, Lily A two-line algorithm for proving q-hypergeometric identities, J. Math. Anal. Appl., Volume 213 (1997) no. 1, pp. 1-14 | DOI

[99] Zeilberger, Doron The algebra of linear partial difference operators and its applications, SIAM J. Math. Anal., Volume 11 (1980) no. 6, pp. 919-932

[100] Zeilberger, Doron Sister Celine’s technique and its generalizations, J. Math. Anal. Appl., Volume 85 (1982) no. 1, pp. 114-145

[101] Zeilberger, Doron A fast algorithm for proving terminating hypergeometric identities, Discrete Math., Volume 80 (1990) no. 2, pp. 207-211

[102] Zeilberger, Doron A holonomic systems approach to special functions identities, J. Comput. Appl. Math., Volume 32 (1990) no. 3, pp. 321-368

[103] Zeilberger, Doron The method of creative telescoping, J. Symbolic Comput., Volume 11 (1991) no. 3, pp. 195-204

[104] Zeilberger, Doron Towards a WZ evaluation of the Mehta integral, SIAM J. Math. Anal., Volume 25 (1994) no. 2, pp. 812-814 | DOI

[105] Zhang, Bao-Yin A new elementary algorithm for proving q-hypergeometric identities, J. Symbolic Comput., Volume 35 (2003) no. 3, pp. 293-303 | DOI

Cited by Sources: