论文标题
快速计算$ q $ - 单位序列和应用
Fast Computation of the $N$-th Term of a $q$-Holonomic Sequence and Applications
论文作者
论文摘要
1977年，Strassen发明了一种著名的婴儿步骤/巨型步骤算法，该算法计算了$ \ sqrt {n} $中的算术$ n！$ n！ 1988年，Chudnovsky兄弟将Strassen的算法概括为在基本上具有相同算术复杂性的任何自动序列的$ n $ THA $ THE期限计算中。我们设计了这些算法的$ Q $ - 动物。我们首先将Strassen的算法扩展到$ n $的$ Q $ Factorial，然后将Chudnovskys的算法扩展到计算任何$ q $ - $ - 循环序列的$ n $ TH $ th $。两种算法都在算术复杂性中起作用quasi-linear中的$ \ sqrt {n} $;令人惊讶的是，它们比人类案例中的类似物简单。我们在算术和位复杂性模型中提供了详细的成本分析。此外，我们描述了各种算法后果，包括线性$ q $差异方程的多项式和合理解决方案的加速，以及对大型多项式的快速评估，包括Nogneng和Schost最近考虑的家庭。
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.
