Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Fast algorithms for differential equations in positive characteristic

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download

https://hal.inria.fr/inria-00355818
Contributor : Alin Bostan <>
Submitted on : Saturday, January 24, 2009 - 5:05:39 PM
Last modification on : Tuesday, December 8, 2020 - 9:52:29 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 9:18:07 PM

Files

BoSc09.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

251

Files downloads

237