×

Trading order for degree in creative telescoping. (English) Zbl 1241.33021

Summary: We analyze the differential equations produced by the method of creative telescoping applied to a hyperexponential term in two variables. We show that equations of low order have high degree, and that higher order equations have lower degree. More precisely, we derive degree bounding formulas which allow to estimate the degree of the output equations from creative telescoping as a function of the order. As an application, we show how the knowledge of these formulas can be used to improve, at least in principle, the performance of creative telescoping implementations, and we deduce bounds on the asymptotic complexity of creative telescoping for hyperexponential terms.

MSC:

33F10 Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.)
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abramov, S. A.; Carette, J. J.; Geddes, K. O.; Le, H. Q., Telescoping in the context of symbolic summation in Maple, Journal of Symbolic Computation, 38, 4, 1303-1326 (2004) · Zbl 1137.05326
[2] Almkvist, G.; Zeilberger, D., The method of differentiating under the integral sign, Journal of Symbolic Computation, 11, 6, 571-591 (1990) · Zbl 0717.33004
[3] Apagodu, M.; Zeilberger, D., Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory, Advances in Applied Mathematics, 37, 2, 139-152 (2006) · Zbl 1108.05010
[4] Beckermann, B.; Labahn, G., A uniform approach for the fast computation of matrix-type Padé approximants, SIAM Journal on Matrix Analysis and Applications, 15, 3, 804-823 (1994) · Zbl 0805.65008
[5] Bostan, A., Chen, S., Chyzak, F., Li, Z., 2010. Complexity of creative telescoping for bivariate rational functions. In: Proceedings of ISSAC’10, pp. 203-210.; Bostan, A., Chen, S., Chyzak, F., Li, Z., 2010. Complexity of creative telescoping for bivariate rational functions. In: Proceedings of ISSAC’10, pp. 203-210. · Zbl 1321.68524
[6] Bostan, A., Chyzak, F., Salvy, B., Lecerf, G., Schost, É., 2007. Differential equations for algebraic functions. In: Proceedings of ISSAC’07, pp. 25-32.; Bostan, A., Chyzak, F., Salvy, B., Lecerf, G., Schost, É., 2007. Differential equations for algebraic functions. In: Proceedings of ISSAC’07, pp. 25-32. · Zbl 1190.68085
[7] Bronstein, M., Li, Z., Wu, M., 2005. Picard-vessiot extensions for linear functional systems. In: Proceedings of ISSAC’05, pp. 68-75.; Bronstein, M., Li, Z., Wu, M., 2005. Picard-vessiot extensions for linear functional systems. In: Proceedings of ISSAC’05, pp. 68-75. · Zbl 1360.12005
[8] (Caviness, B. F.; Johnson, J. R., Quantifier Elimination and Cylindrical Algebraic Decomposition. Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation (1998), Springer) · Zbl 0906.03033
[9] Christopher, C., Liouvillian first integrals of second order polynomial differential equations, Electronic Journal of Differential Equations, 49, #7, 1-7 (1999) · Zbl 0939.34002
[10] Chyzak, F., 1998. Fonctions holonomes en calcul formel. Ph.D. Thesis, INRIA Rocquencourt.; Chyzak, F., 1998. Fonctions holonomes en calcul formel. Ph.D. Thesis, INRIA Rocquencourt.
[11] Chyzak, F., An extension of Zeilberger’s fast algorithm to general holonomic functions, Discrete Mathematics, 217, 115-134 (2000) · Zbl 0968.33011
[12] Chyzak, F.; Kauers, M.; Salvy, B., A non-holonomic systems approach to special function identities, (May, J., Proceedings of ISSAC’09 (2009)), 111-118 · Zbl 1237.33001
[13] Collins, G. E., Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition, (Lecture Notes in Computer Science, vol. 33 (1975)), 134-183
[14] Gosper, W., 1978. Decision procedure for indefinite hypergeometric summation. In: Proceedings of the National Academy of Sciences of the United States of America 75, pp. 40-42.; Gosper, W., 1978. Decision procedure for indefinite hypergeometric summation. In: Proceedings of the National Academy of Sciences of the United States of America 75, pp. 40-42. · Zbl 0384.40001
[15] Kauers, M.; Paule, P., The Concrete Tetrahedron (2011), Springer · Zbl 1225.00001
[16] Koepf, W., Hypergeometric Summation (1998), Vieweg
[17] Koutschan, C., 2009. Advanced applications of the holonomic systems approach. Ph.D. Thesis, RISC-Linz, Johannes Kepler Universität Linz.; Koutschan, C., 2009. Advanced applications of the holonomic systems approach. Ph.D. Thesis, RISC-Linz, Johannes Kepler Universität Linz. · Zbl 1344.68301
[18] Koutschan, C., A fast approach to creative telescoping, Mathematics in Computer Science, 4, 2-3, 259-266 (2010) · Zbl 1218.68205
[19] Mohammed, M.; Zeilberger, D., Sharp upper bounds for the orders of the recurrences outputted by the Zeilberger and \(q\)-Zeilberger algorithms, Journal of Symbolic Computation, 39, 2, 201-207 (2005) · Zbl 1121.33023
[20] Paule, P.; Schorn, M., A Mathematica version of Zeilberger’s algorithm for proving binomial coefficient identities, Journal of Symbolic Computation, 20, 5-6, 673-698 (1995) · Zbl 0851.68052
[21] Petkovšek, M.; Wilf, H.; Zeilberger, D., \(A = B (1997)\), AK Peters, Ltd
[22] Schneider, C., The summation package Sigma: underlying principles and a rhombus tiling application, Discrete Mathematics and Theoretical Computer Science, 6, 2, 365-386 (2004) · Zbl 1066.68164
[23] Schneider, C., Solving parameterized linear difference equations in terms of indefinite nested sums and products, Journal of Difference Equations and Applications, 11, 9, 799-821 (2005) · Zbl 1087.33011
[24] Storjohann, A., Villard, G., 2005. Computing the rank and a small nullspace basis of a polynomial matrix. In: Proceedings of ISSAC’05, pp. 309-316.; Storjohann, A., Villard, G., 2005. Computing the rank and a small nullspace basis of a polynomial matrix. In: Proceedings of ISSAC’05, pp. 309-316. · Zbl 1360.68957
[25] Strzeboński, A., Solving systems of strict polynomial inequalities, Journal of Symbolic Computation, 29, 471-480 (2000) · Zbl 0962.68183
[26] Strzeboński, A., Cylindrical algebraic decomposition using validated numerics, Journal of Symbolic Computation, 41, 9, 1021-1038 (2006) · Zbl 1124.68123
[27] Verbaeten, P., The automatic construction of pure recurrence relations, ACM Sigsam Bulletin, 8, 96-98 (1974)
[28] Verbaeten, P., 1976. Rekursiebetrekkingen voor lineaire hypergeometrische funkties. Ph.D. Thesis, Department of Computer Science, K.U.Leuven, Leuven, Belgium.; Verbaeten, P., 1976. Rekursiebetrekkingen voor lineaire hypergeometrische funkties. Ph.D. Thesis, Department of Computer Science, K.U.Leuven, Leuven, Belgium.
[29] Wegschaider, K., 1997. Computer generated proofs of binomial multi-sum identities. Master’s Thesis, RISC-Linz.; Wegschaider, K., 1997. Computer generated proofs of binomial multi-sum identities. Master’s Thesis, RISC-Linz.
[30] Wilf, H. S., generatingfunctionology (1989), AK Peters, Ltd · Zbl 0831.05001
[31] Zeilberger, D., A fast algorithm for proving terminating hypergeometric identities, Discrete Mathematics, 80, 207-211 (1990) · Zbl 0701.05001
[32] Zeilberger, D., The method of creative telescoping, Journal of Symbolic Computation, 11, 195-204 (1991) · Zbl 0738.33002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.