A Fast Algorithm for Computing the p-Curvature

Abstract

We design an algorithm for computing the $p$-curvature of a differential system in positive characteristic $p$. For a system of dimension $r$ with coefficients of degree at most $d$, its complexity is $\softO (p d r^ω)$ operations in the ground field (where $\omega$ denotes the exponent of matrix multiplication), whereas the size of the output is about $pd{r}^2$. Our algorithm is then quasi-optimal assuming that matrix multiplication is (\emph{i.e.} $\omega =2$). The main theoretical input we are using is the existence of a well-suited ring of series with divided powers for which an analogue of the Cauchy--Lipschitz Theorem holds.

ISSAC 2015, Jul 2015, Bath, United Kingdom

References in corpus (5)

• Singularities of $n$-fold integrals of the Ising class and the theory of elliptic curves
• A fast algorithm for computing the characteristic polynomial of the p-curvature
• Globally nilpotent differential operators and the square Ising model
• Automatic Classification of Restricted Lattice Walks
• Fast algorithms for differential equations in positive characteristic