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})$.
Type de document :
Communication dans un congrès
ISSAC - 39th International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. ACM Press, 2014, 〈10.1145/2608628.2608650〉
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00994033
Contributeur : Alin Bostan <>
Soumis le : mardi 20 mai 2014 - 20:26:02
Dernière modification le : jeudi 15 novembre 2018 - 11:56:35
Document(s) archivé(s) le : mercredi 20 août 2014 - 12:20:40

Fichiers

BoCaSc14.pdf
Accord explicite pour ce dépôt

Identifiants

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. ACM Press, 2014, 〈10.1145/2608628.2608650〉. 〈hal-00994033〉

Partager

Métriques

Consultations de la notice

453

Téléchargements de fichiers

146