A fast algorithm for computing the characteristic polynomial of the p-curvature
A fast algorithm for computing the characteristic polynomial of the p-curvature
复制标题
计算p曲率特征多项式的快速算法
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
É. Schost
中科院分区：
文献类型：
--
作者：
A. Bostan;X. Caruso;É. Schost
讨论了特征<i>p</i>中微分算子的<i>p</i>-曲率的理论和算法问题.给定这样一个算子<i>L</i>，用λ（<i>L</i>）表示它的<i>p</i>-曲率的特征多项式，我们首先证明λ（<i>L</i>）的一个新的可供选择的描述。这种描述特别适合于当<i>p</i>较大时快速计算k（<i>L</i>）：在此基础上，我们设计了一种新的计算k（<i>L</i>）的算法，其代价相对于<i>p</i>为<i>k</i>（<i>p</i><sup>0.5</sup>）次基域运算。这是值得注意的，因为在这项工作之前，这个任务的最快算法，甚至对于决定<i>p</i>-曲率的幂零性的子任务，只有轻微的次二次复杂<i>度</i>（<i>p</i><sup>1.79</sup>）。
We discuss theoretical and algorithmic questions related to the <i>p</i>-curvature of differential operators in characteristic <i>p</i>. Given such an operator <i>L</i>, and denoting by Ξ(<i>L</i>) the characteristic polynomial of its <i>p</i>-curvature, we first prove a new, alternative, description of Ξ(<i>L</i>). This description turns out to be particularly well suited to the fast computation of Ξ(<i>L</i>) when <i>p</i> is large: based on it, we design a new algorithm for computing Ξ(<i>L</i>), whose cost with respect to <i>p</i> is <i>Õ</i>(<i>p</i><sup>0.5</sup>) operations in the ground field. This is remarkable since, prior to this work, the fastest algorithms for this task, and even for the subtask of deciding nilpotency of the <i>p</i>-curvature, had merely slightly subquadratic complexity <i>Õ</i>(<i>p</i><sup>1.79</sup>).