Skip to Main content Skip to Navigation
Conference papers

Low Complexity Algorithms for Linear Recurrences

Alin Bostan 1 Frédéric Chyzak 1 Thomas Cluzeau 2 Bruno Salvy 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
2 CAFE - Computer algebra and functional equations
CRISAM - Inria Sophia Antipolis - Méditerranée
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(\sqrt{N}\log^{2}N)$ bit operations; a deterministic one that computes a compact representation of the solution in~$O(N\log^{3}N)$ bit operations. Similar speed-ups are obtained in indefinite and definite hypergeometric summation. We describe the results of an implementation.
Document type :
Conference papers
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download
Contributor : Bruno Salvy <>
Submitted on : Monday, May 15, 2006 - 4:40:07 PM
Last modification on : Thursday, March 5, 2020 - 5:34:15 PM
Long-term archiving on: : Saturday, April 3, 2010 - 11:22:56 PM




Alin Bostan, Frédéric Chyzak, Thomas Cluzeau, Bruno Salvy. Low Complexity Algorithms for Linear Recurrences. ISSAC International Symposium on Symbolic and Algebraic Computations, Jul 2006, Genova, Italy, Italy. pp.31-38, ⟨10.1145/1145768.1145781⟩. ⟨inria-00068922⟩