Fast Computation of the $N$-th Term of a $q$-Holonomic Sequence and Applications - Archive ouverte HAL Access content directly
Journal Articles Journal of Symbolic Computation Year : 2022

Fast Computation of the $N$-th Term of a $q$-Holonomic Sequence and Applications

(1, 2) , (3, 1, 2)
1
2
3

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 essentially 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}$; surprisingly, they are simpler than their analogues in the holonomic case. We provide a detailed cost analysis, in both arithmetic and bit complexity models. Moreover, 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.
Fichier principal
Vignette du fichier
2012.08656.pdf (487.68 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03084680 , version 1 (21-12-2020)

Identifiers

Cite

Alin Bostan, Sergey Yurkevich. Fast Computation of the $N$-th Term of a $q$-Holonomic Sequence and Applications. Journal of Symbolic Computation, 2022, 115, pp.96-123. ⟨10.1016/j.jsc.2022.07.008⟩. ⟨hal-03084680⟩
58 View
77 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More