Low Complexity Algorithms for Linear Recurrences
| dc.creator | Bostan, Alin | |
| dc.creator | Chyzak, Frédéric | |
| dc.creator | Salvy, Bruno | |
| dc.creator | Cluzeau, Thomas | |
| dc.date | 2006-05-16 | |
| dc.date.accessioned | 2026-07-07T09:29:55Z | |
| dc.date.available | 2026-07-07T09:29:55Z | |
| dc.description | 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. | |
| dc.description | This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution | |
| dc.identifier | https://arxiv.org/abs/cs/0605068 | |
| dc.identifier | http://arxiv.org/abs/cs/0605068 | |
| dc.identifier | ISSAC'06, pages 31--38, ACM Press, 2006 | |
| dc.identifier | doi:10.1145/1145768.1145781 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/157965 | |
| dc.subject | Symbolic Computation | |
| dc.title | Low Complexity Algorithms for Linear Recurrences | |
| dc.type | text |