arXiv Open Access 2015

A Fast Algorithm for Computing the p-Curvature

Alin Bostan Xavier Caruso Éric Schost

Lihat Sumber

Abstrak

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 $ω$ denotes the exponent of matrix multiplication), whereas the size of the output is about $p d r^2$. Our algorithm is then quasi-optimal assuming that matrix multiplication is (\emph{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.

Topik & Kata Kunci

cs.SC

Penulis (3)

Alin Bostan

Xavier Caruso

Éric Schost

Format Sitasi

APA MLA BibTeX

Bostan, A., Caruso, X., Schost, É. (2015). A Fast Algorithm for Computing the p-Curvature. https://arxiv.org/abs/1506.05645

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2015
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓