Fast Coefficient Computation for Algebraic Power Series in Positive Characteristic
Fast Coefficient Computation for Algebraic Power Series in Positive Characteristic
复制标题
正特性代数幂级数的快速系数计算
DOI：
10.2140/obs.2019.2.119
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
P. Dumas
中科院分区：
文献类型：
--
作者：
A. Bostan;X. Caruso;G. Christol;P. Dumas
我们重新审视克里斯托的正特征代数幂级数定理，并为其提出另一个证明。这个新证明结合了现有证明的多种成分和优点，这使得它非常适合算法目的。我们将新证明中使用的结构应用于设计一种新的高效算法，用于计算完美特征域~$p$上给定代数幂级数的第$N$个系数。它有几个很好的特点：比以前的算法更通用、更自然、更高效。新算法的算术复杂度不仅在$\log N$中是线性的，在~$p$中是准线性的，而且它对输入次数的依赖性比以前最好的算法要小得多。 {此外，当地面场有限时，新方法会产生更快的算法，其位复杂度在 $\log N$ 中呈线性，在 ~$\sqrt{p}$} 中呈准线性。
We revisit Christol's theorem on algebraic power series in positive characteristic and propose yet another proof for it. This new proof combines several ingredients and advantages of existing proofs, which make it very well-suited for algorithmic purposes. We apply the construction used in the new proof to the design of a new efficient algorithm for computing the $N$th coefficient of a given algebraic power series over a perfect field of characteristic~$p$. It has several nice features: it is more general, more natural and more efficient than previous algorithms. Not only the arithmetic complexity of the new algorithm is linear in $\log N$ and quasi-linear in~$p$, but its dependency with respect to the degree of the input is much smaller than in the previously best algorithm. {Moreover, when the ground field is finite, the new approach yields an even faster algorithm, whose bit complexity is linear in $\log N$ and quasi-linear in~$\sqrt{p}$}.
DOI：
--
发表时间：
2006
期刊：
Integrable systems, geometry, and topology, AMS/IP Studies of Advanced Mathematics, American Mathematical Society 36
影响因子：
--
作者：
FURUYA;Jun;Martin Guest
通讯作者：
Martin Guest