Low complexity algorithms for linear recurrences

ABSTRACT

We consider two kinds of problems: the computation of polynomial and rational solutions of linear recurrences with coefficients that are polynomials with integer coefficients; indefinite and definite summation of sequences that are hypergeometric over the rational numbers. The algorithms for these tasks all involve as an intermediate quantity an integer N (dispersion or root of an indicial polynomial) that is potentially exponential in the bit size of their input. Previous algorithms have a bit complexity that is at least quadratic in N. We revisit them and propose variants that exploit the structure of solutions and avoid expanding polynomials of degree N. We give two algorithms: a probabilistic one that detects the existence or absence of nonzero polynomial and rational solutions in O(√N log² N) bit operations; a deterministic one that computes a compact representation of the solution in O(N log³ N) bit operations. Similar speedups are obtained in indefinite and definite hypergeometric summation. We describe the results of an implementation.

REFERENCES

• 1: S. A. Abramov. Rational solutions of linear difference and q-difference equations with polynomial coefficients. Programming and computer software, 21(6):273--278, 1995.
• 2: S. A. Abramov, Applicability of Zeilberger's algorithm to hypergeometric terms, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.1-7, July 07-10, 2002, Lille, France [doi>10.1145/780506.780507]
• 3: Sergei A. Abramov , Manuel Bronstein , Marko Petkovšek, On polynomial solutions of linear operator equations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.290-296, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220384]
• 4: Sergei A. Abramov , Marko Petkovšek , Anna Ryabenko, Special formal series solutions of linear operator equations, Discrete Mathematics, v.210 n.1-3, p.3-25, Jan.6.2000 [doi>10.1016/S0012-365X(99)00118-1 ]
• 5: G. Boole. A treatise on the calculus of finite differences. Macmillan, London, 2nd edition, 1872.
• 6: A. Bostan, F. Chyzak, T. Cluzeau, and B. Salvy. Fast algorithms for polynomial and rational solutions of linear operators equations, In preparation.
• 7: Alin Bostan , Thomas Cluzeau , Bruno Salvy, Fast algorithms for polynomial solutions of linear differential equations, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.45-52, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073893]
• 8: A. Bostan, P. Gaudry, and É. Schost. Linear recurrences with polynomial coefficients and computation of the Cartier-Manin operator on hyperelliptic curves. In International Conference on Finite Fields and Applications (Toulouse, 2003), volume 2948 of Lecture Notes in Computer Science, pages 40--58. Springer-Verlag, 2004.
• 9: P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, Berlin, 1997.
• 10: D. V. Chudnovsky and G. V. Chudnovsky. Approximations and complex multiplication according to Ramanujan. In Ramanujan revisited, pages 375--472. Academic Press, Boston, MA, 1988.
• 11: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 12: Juergen Gerhard, Modular Algorithms In Symbolic Summation And Symbolic Integration (Lecture Notes in Computer Science), SpringerVerlag, 2006
• 13: J. Gerhard , M. Giesbrecht , A. Storjohann , E. V. Zima, Shiftless decomposition and polynomial-time rational summation, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.119-126, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860887]
• 14: R. W. Gosper. Decision procedure for indefinite hypergeometric summation. Proc. of the National Academy of Sciences USA, 75(1):40--42, Jan. 1978.
• 15: R. Loos. Computing rational zeros of integral polynomials by p?adic expansion. SIAM Journal on Computing, 12(2):286--293, May 1983.
• 16: Marko Petkovšek, Hypergeometric solutions of linear recurrences with polynomial coefficients, Journal of Symbolic Computation, v.14 n.2-3, p.243-264, Aug./Sept. 1992 [doi>10.1016/0747-7171(92)90038-6]
• 17: M. Petkovšek, H. S. Wilf, and D. Zeilberger. A = B. A. K. Peters, Wellesley, MA, 1996.
• 18: A. Schönhage, A. F. W. Grotefeld, and E. Vetter. Fast algorithms. Bibliographisches Institut, Mannheim, 1994. A multitape Turing machine implementation.
• 19: A. Schönhage and V. Strassen. Schnelle Multiplikation groβer Zahlen. Computing, 7:281--292, 1971.
• 20: H. S. Wilf and D. Zeilberger. An algorithmic proof theory for hypergeometric (ordinary and "q" multisum/integral identities. Inventiones Mathematicae, 108:575--633, 1992.
• 21: Doron Zeilberger, The method of creative telescoping, Journal of Symbolic Computation, v.11 n.3, p.195-204, March 1991 [doi>10.1016/S0747-7171(08)80044-2]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

General Terms:
Algorithms, Experimentation, Theory

Keywords:
complexity, computer algebra, creative telescoping, linear recurrences, polynomial and rational solutions, summation