@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.},
}