Fast algorithms for differential equations in positive characteristic

Details Fast algorithms for differential equations in positive characteristic Fast algorithms for differential equations in positive characteristic

2009-01-24

arxiv.org/abs/0901.3843v1

Computer Science

Symbolic Computation

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Fast algorithms for differential equations in positive characteristic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast algorithms for differential equations in positive characteristic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast algorithms for differential equations in positive characteristic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-454498