Computer Science – Symbolic Computation
Scientific paper
2006-05-16
ISSAC'06, pages 31--38, ACM Press, 2006
Computer Science
Symbolic Computation
This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution
Scientific paper
10.1145/1145768.1145781
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.
Bostan Alin
Chyzak Frédéric
Cluzeau Thomas
Salvy Bruno
No associations
LandOfFree
Low Complexity Algorithms for Linear Recurrences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Low Complexity Algorithms for Linear Recurrences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low Complexity Algorithms for Linear Recurrences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-275758