Fast algorithms for differential equations in positive characteristic
| dc.creator | Bostan, Alin | |
| dc.creator | Schost, Éric | |
| dc.date | 2009-01-24 | |
| dc.date.accessioned | 2026-07-07T12:34:24Z | |
| dc.date.available | 2026-07-07T12:34:24Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/0901.3843 | |
| dc.identifier | http://arxiv.org/abs/0901.3843 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/217418 | |
| dc.subject | Symbolic Computation | |
| dc.title | Fast algorithms for differential equations in positive characteristic | |
| dc.type | text |