A Fast Algorithm for Computing the P-curvature
Alin Bostan, Xavier Caruso, Éric Schost · 2015
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 O~ (p d rω) operations in the ground field (where ω denotes the exponent of matrix multiplication), whereas the size of the output is about p d r2. Our algorithm is then quasi-optimal assuming that matrix multiplication is (i.e. ω = 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.