# Fast algorithms for differential equations in positive characteristic

1 ALGORITHMS - Algorithms
Inria Paris-Rocquencourt
Abstract : We address complexity issues for linear differential equations in characteristic~$p>0$: resolution and computation of the $p$-curvature. For these tasks, our main focus is on algorithms whose complexity behaves well with respect to~$p$. We prove bounds linear in $p$ on the degree of polynomial solutions and propose algorithms for testing the existence of polynomial solutions in sublinear time $\tilde{O}(p^{1/2})$, and for determining a whole basis of the solution space in quasi-linear time $\tilde{O}(p)$; the $\tilde{O}$ notation indicates that we hide logarithmic factors. We show that for equations of arbitrary order, the $p$-curvature can be computed in subquadratic time $\tilde{O}(p^{1.79})$, and that this can be improved to $O(\log(p))$ for first order equations and to $\tilde{O}(p)$ for classes of second order equations.
Keywords :
Type de document :
Pré-publication, Document de travail
2009
Domaine :

Littérature citée [27 références]

https://hal.inria.fr/inria-00355818
Contributeur : Alin Bostan <>
Soumis le : samedi 24 janvier 2009 - 17:05:39
Dernière modification le : mercredi 29 novembre 2017 - 15:08:39
Document(s) archivé(s) le : mardi 8 juin 2010 - 21:18:07

### Fichiers

BoSc09.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00355818, version 1
• ARXIV : 0901.3843

### Citation

Alin Bostan, Éric Schost. Fast algorithms for differential equations in positive characteristic. 2009. 〈inria-00355818〉

### Métriques

Consultations de la notice

## 194

Téléchargements de fichiers