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

https://hal.inria.fr/inria-00068922
Contributor : Bruno Salvy <>
Submitted on : Monday, May 15, 2006 - 4:40:07 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Saturday, April 3, 2010 - 11:22:56 PM

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

206

Files downloads

173