A fast algorithm for computing the characteristic polynomial of the p-curvature - Université de Rennes Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

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

Alin Bostan
  • Fonction : Auteur
  • PersonId : 831654
Éric Schost
  • Fonction : Auteur
  • PersonId : 839026

Résumé

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})$.
Fichier principal
Vignette du fichier
BoCaSc14.pdf (239.54 Ko) Télécharger le fichier
Origine : Accord explicite pour ce dépôt
Loading...

Dates et versions

hal-00994033 , version 1 (20-05-2014)

Identifiants

Citer

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⟩
288 Consultations
192 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More