Low Complexity Algorithms for Linear RecurrencesReport as inadecuate




Low Complexity Algorithms for Linear Recurrences - Download this document for free, or read online. Document in PDF available to download.

1 ALGO - Algorithms Inria Paris-Rocquencourt 2 CAFE - Computer algebra and functional equations CRISAM - Inria Sophia Antipolis - Méditerranée

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~$ON\log^{3}N$ bit operations. Similar speed-ups are obtained in indefinite and definite hypergeometric summation. We describe the results of an implementation.





Author: Alin Bostan - Frédéric Chyzak - Thomas Cluzeau - Bruno Salvy -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents