A fast algorithm for computing the characteristic polynomial of the p-curvature

Abstract : We discuss theoretical and algorithmic questions related to the $p$-curvature of differential operators in characteristic $p$. Given such an operator~$L$, and denoting by $\Chi(L)$ the characteristic polynomial of its $p$-curvature, we first prove a new, alternative, description of $\Chi(L)$. This description turns out to be particularly well suited to the fast computation of $\Chi(L)$ when $p$ is large: based on it, we design a new algorithm for computing $\Chi(L)$, whose cost with respect to~$p$ is $\softO(p^{0.5})$ 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 $p$-curvature, had merely slightly subquadratic complexity $\softO(p^{1.79})$.
Document type :
Conference papers
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-00994033
Contributor : Alin Bostan <>
Submitted on : Tuesday, May 20, 2014 - 8:26:02 PM
Last modification on : Thursday, November 15, 2018 - 11:56:35 AM
Long-term archiving on : Wednesday, August 20, 2014 - 12:20:40 PM

Files

BoCaSc14.pdf
Explicit agreement for this submission

Identifiers

Citation

Alin Bostan, Xavier Caruso, Éric Schost. A fast algorithm for computing the characteristic polynomial of the p-curvature. ISSAC - 39th International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. ⟨10.1145/2608628.2608650⟩. ⟨hal-00994033⟩

Share

Metrics

Record views

524

Files downloads

227