Fast algorithms for differential equations in positive characteristic
Proceedings of the 2009 international symposium on Symbolic and algebraic …, 2009•dl.acm.org
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 Õ (p 1/2), and for determining a whole basis of the
solution space in quasi-linear time Õ (p); the Õ notation indicates that we hide logarithmic …
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 Õ (p 1/2), and for determining a whole basis of the
solution space in quasi-linear time Õ (p); the Õ notation indicates that we hide logarithmic …
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 Õ(p1/2), and for determining a whole basis of the solution space in quasi-linear time Õ(p); the Õ notation indicates that we hide logarithmic factors. We show that for equations of arbitrary order, the p-curvature can be computed in subquadratic time Õ(p1.79), and that this can be improved to O(log(p)) for first order equations and to Õ(p) for classes of second order equations.