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 <>
Submitted on : Saturday, June 27, 2020 - 10:46:47 PM
Last modification on : Monday, January 11, 2021 - 2:34:57 PM

File

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

Identifiers

Collections

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

84

Files downloads

617