English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In 1977, Strassen invented a famous baby-step/giant-step algorithm thatcomputes the factorial $N!$ in arithmetic complexity quasi-linear in$\sqrt{N}$. In 1988, the Chudnovsky brothers generalized Strassen's algorithmto the computation of the $N$-th term of any holonomic sequence in essentiallythe same arithmetic complexity. We design $q$-analogues of these algorithms. Wefirst 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 complexityquasi-linear in $\sqrt{N}$; surprisingly, they are simpler than their analoguesin the holonomic case. We provide a detailed cost analysis, in both arithmeticand bit complexity models. Moreover, we describe various algorithmicconsequences, including the acceleration of polynomial and rational solving oflinear $q$-differential equations, and the fast evaluation of large classes ofpolynomials, including a family recently considered by Nogneng and Schost.

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