Accelerating Indefinite Summation: Simple Classes of Summands

1. Abramov S.A.: The summation of rational functions. Ž. Vyčisl. Mat. i Mat. Fiz. 11, 1071–1075 (1971)

   MATH  MathSciNet  Google Scholar 

2. Abramov, S.A.: The rational component of the solution of a first order linear recurrence relation with rational right hand side. Ž. Vyčisl. Mat. i Mat. Fiz. 15(4), 1035–1039, 1090 (1975)

3. Abramov, S.A.: Indefinite sums of rational functions. In: Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, ISSAC ’95, pp 303–308. ACM, New York (1995)

4. Abramov, S.A., Bronstein, M., Petkovšek, M.: On polynomial solutions of linear operator equations. In: Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, ISSAC ’95, pp. 290–296. ACM, New York (1995)

5. Abramov, S.A., Petkovšek, M.: Rational normal forms and minimal decompositions of hypergeometric terms. J. Symb. Comput. 33(5), 521–543 (2002). Computer algebra (London, ON, 2001)

   Google Scholar 

6. Abramov S.A. et al.: Telescoping in the context of symbolic summation in Maple. J. Symb. Comput. 38(4), 1303–1326 (2004)

   Article  MathSciNet  Google Scholar 

7. Bachmann, O., Wang, P.S., Zima, E.V.: Chains of recurrences—a method to expedite the evaluation of closed-form functions. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC ’94, pp. 242–249. ACM, New York (1994)

8. Boole, G.: A Treatise on the Calculus of Finite Differences. Cambridge Library Collection. Cambridge University Press, Cambridge (2009) (Reprint of the 1860 original)

9. Bostan, A., Chyzak, F., Salvy, B., Cluzeau, T.: Low complexity algorithms for linear recurrences. In: Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, ISSAC ’06, pp. 31–38. ACM, New York, (2006)

10. Bostan, A., Salvy, B., Schost, E.: Power series composition and change of basis. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC ’08, pp. 269–276. ACM, New York (2008)

11. Egorychev, G.P., Zima, E.V. : On integral representation and algorithmic approaches to the evaluation of combinatorial sums. Technical Report CS-2002-02, School of Computer Science, University of Waterloo, January (2002)

12. Euler, L.: Foundations of Differential Calculus. Springer, New York (2000) Translated from the Latin by John D. Blanton

13. von zur Gathen J., Gerhard J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, New York (2003)

    Google Scholar 

14. Gerhard, J.: Modular algorithms in symbolic summation and symbolic integration. Lecture Notes in Computer Science, vol. 3218. Springer, Berlin (2004)

15. Gerhard, J., Giesbrecht, M., Storjohann, A., Zima, E.V. : Shiftless decomposition and polynomial-time rational summation. In: Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, pp. 119–126 (Melectronic). ACM, New York (2003)

16. Gosper, R.W. Jr.: Indefinite hypergeometric sums in MACSYMA. In: Proceedings of the 1977 MACSYMA Users’ Conference, pp. 237–251 (1977)

17. Gosper R.W. Jr: Decision procedure for indefinite hypergeometric summation. Proc. Nat. Acad. Sci. USA 75(1), 40–42 (1978)

    Article  MATH  MathSciNet  Google Scholar 

18. Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. Addison-Wesley Publishing Company Advanced Book Program, Reading (1989). A foundation for computer science

19. Jordan C.: Calculus of Finite Differences. Hungarian Agent Eggenberger Book-Shop, Budapest (1939)

    Google Scholar 

20. Jordan C.: Calculus of Finite Differences, 3rd edn. Introduction by Harry C Carver. . Chelsea Publishing Co., New York (1965)

    Google Scholar 

21. Karr, M.: Summation in finite terms (preliminary version). Technical Report CA-7602-2911, Massachusetts Computer Associates Inc., USA (1976)

22. Karr M.: Summation in finite terms. J. Assoc. Comput. Mach. 28(2), 305–350 (1981)

    Article  MATH  MathSciNet  Google Scholar 

23. Karr M.: Theory of summation in finite terms. J. Symb. Comput. 1(3), 303–315 (1985)

    Article  MATH  MathSciNet  Google Scholar 

24. Lafon J.C.: Summation in finite terms. In: Buchberger, B., Collins, G.E., Loos, R., Albrecht, R. (eds) Computer Algebra Symbolic and Algebraic Computation, pp. 71–77. Springer, Vienna (1983)

    Google Scholar 

25. Lisoněk P., Paule P., Strehl V.: Improvement of the degree setting in Gosper’s algorithm. J. Symb. Comput. 16(3), 243–258 (1993)

    Article  MATH  Google Scholar 

26. Malm D.E.G., Subramaniam T.N.: The summation of rational functions by an extended Gosper algorithm. J. Symb Comput. 19(4), 293–304 (1995)

    Article  MATH  MathSciNet  Google Scholar 

27. Man Y.-K.: On computing closed forms for indefinite summations. J. Symb. Comput. 16(4), 355–376 (1993)

    Article  MATH  MathSciNet  Google Scholar 

28. Matusevich L.F.: Rational summation of rational functions. Beiträge Algebra Geom. 41(2), 531–536 (2000)

    MATH  MathSciNet  Google Scholar 

29. Moenck, R.: On computing closed forms for summations. In: Proceedings of the 1977 MACSYMA Users’ Conference, pp. 225–236 (1977)

30. Paule P.: Greatest factorial factorization and symbolic summation. J. Symb. Comput. 20(3), 235–268 (1995)

    Article  MATH  MathSciNet  Google Scholar 

31. Pirastu, R.: A note on the minimality problem in indefinite summation of rational functions. In: Séminaire Lotharingien de Combinatoire (Saint-Nabor, 1993). Prépubl. Inst. Rech. Math. Av., vol. 1994/21 , pp. 95–101. Univ. Louis Pasteur, Strasbourg (1994)

32. Pirastu, R.: On combinatorial identities: symbolic summation and umbral calculus. PhD thesis, Johannes Kepler Universität, Linz, Austria (1996)

33. Pirastu R., Strehl V.: Rational summation and Gosper–Petkovšek representation. J. Symb. Comput. 20(5-6), 617–635 (1995)

    Article  MATH  MathSciNet  Google Scholar 

34. Polyakov S.P.: Indefinite summation of rational functions with additional minimization of the summable part. Program. Comput. Softw. 34(2), 48–53 (2008)

    MathSciNet  Google Scholar 

35. Polyakov S.P.: Indefinite summation of rational functions with factorization of denominators. Program. Comput. Softw. 37(6), 322–325 (2011)

    Article  MATH  MathSciNet  Google Scholar 

36. Schneider, C.: An implementation of Karr’s summation algorithm in Mathematica. Sém. Lothar. Combin. (electronic) 43:Art. S43b (1999)

37. Schneider, C.: Symbolic summation with single-nested sum extensions. In: ISSAC 2004, pp. 282–289. ACM, New York (2004)

38. Schneider C.: A new Sigma approach to multi-summation. Adv. Appl. Math. 34(4), 740–767 (2005)

    Article  MATH  Google Scholar 

39. Tweedie, C.: Nicole’s contribution to the foundations of the calculus of finite differences. Proc. Edinb. Math. Soc. 36, 22–39 (1917)

    Google Scholar 

40. van Hoeij, M.: Rational solutions of linear difference equations. In: Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, ISSAC ’98, pp. 120–123. ACM, New York (1998)

41. Zima, E.V.: Simplification and optimization transformations of chains of recurrences. In: Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, ISSAC ’95, pp. 42–50. ACM, New York (1995)

42. Zima, E.V.: Direct algorithm for indefinite quasi-rational summation. Technical Report CARGO-2010-03, CARGO lab, WLU (2010)

43. Zima, E.V.: Synthetic division in the context of indefinite rational summation. Technical Report CARGO-2011-01, CARGO lab, WLU (2011)

44. Zima, E.V.: Synthetic division in the context of indefinite summation. In: Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation, SNC ’11, pp. 151–152. ACM, New York (2011)

Download references