2020/12/15 by Alin Bostan, Sergey Yurkevich, Bostan, Alin +1
Computer Science · Engineering · #05A30 #33F10 #68Q25 #68W30 #Coding theory and cryptography #FOS: Computer and information sciences #I.1.2 #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2012.08656
openalex publication_date 2020/12/15 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
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.