Fast computation of the N-th term of a q-holonomic sequence and applications. (March 2023) - Bostan, Alin; Yurkevich, Sergey
Abstract: In 1977, Strassen invented a famous baby-step/giant-step algorithm that computes the factorial N ! in arithmetic complexity quasi-linear in 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 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.