@inproceedings{BoChClSa06,
author = {Bostan, Alin and Chyzak, Fr{\'e}d{\'e}ric and Cluzeau,
Thomas and Salvy, Bruno},
title = {Low Complexity Algorithms for Linear Recurrences},
booktitle = {ISSAC'06},
year = {2006},
editor = {Dumas, Jean-Guillaume},
publisher = {ACM Press},
pages = {31--38},
doi = {10.1145/1145768.1145781},
arxiv = {abs/cs/0605068},
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.},
}