Skip to Main content Skip to Navigation
Conference papers

Computing the $N$-th Term of a $q$-Holonomic Sequence

Abstract : In 1977, Strassen invented a famous baby-step / giant-step algorithm that computes the factorial $N!$ in arithmetic complexity quasi-linear in $\sqrt{N}$. In 1988, the Chudnovsky brothers generalized Strassen’s algorithm to the computation of the $N$-th term of any holonomic sequence in the same arithmetic complexity. We design $q$-analogues of these algorithms. We first extend Strassen’s algorithm to the computation of the $q$-factorial of $N$, then Chudnovskys' algorithm to the computation of the $N$-th term of any $q$-holonomic sequence. Both algorithms work in arithmetic complexity quasi-linear in~$\sqrt{N}$. We describe various algorithmic consequences, including the acceleration of polynomial and rational solving of linear $q$-differential equations, and the fast evaluation of large classes of polynomials, including a family recently considered by Nogneng and Schost.
Document type :
Conference papers
Complete list of metadata

Cited literature [77 references]  Display  Hide  Download

https://hal.inria.fr/hal-02882885
Contributor : Alin Bostan Connect in order to contact the contributor
Submitted on : Saturday, June 27, 2020 - 10:46:47 PM
Last modification on : Saturday, August 6, 2022 - 3:46:32 AM

File

Bostan20-arxiv.pdf
Files produced by the author(s)

Identifiers

Citation

Alin Bostan. Computing the $N$-th Term of a $q$-Holonomic Sequence. ISSAC 2020 - 45th International Symposium on Symbolic and Algebraic Computation, Jul 2020, Kalamata, Greece. pp.8, ⟨10.1145/3373207.3404060⟩. ⟨hal-02882885⟩

Share

Metrics

Record views

72

Files downloads

434