Low Complexity Algorithms for Linear Recurrences
<|reference_start|>Low Complexity Algorithms for Linear Recurrences: 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.<|reference_end|>
@article{bostan2006low,
    title={Low Complexity Algorithms for Linear Recurrences},
    author={Alin Bostan (INRIA Rocquencourt), Fr'ed'eric Chyzak (INRIA
  Rocquencourt), Bruno Salvy (INRIA Rocquencourt), Thomas Cluzeau (INRIA Sophia
  Antipolis)},
    journal={ISSAC'06, pages 31--38, ACM Press, 2006},
    year={2006},
    doi={10.1145/1145768.1145781},
    archivePrefix={arXiv},
    eprint={cs/0605068},
    primaryClass={cs.SC}
}