### On p-adic differential equations with separation of variables

**2016-01-31**

1602.00244 | cs.SC

Several algorithms in computer algebra involve the computation of a power
series solution of a given ordinary differential equation. Over finite fields,
the problem is often lifted in an approximate $p$-adic setting to be
well-posed. This raises precision concerns: how much precision do we need on
the input to compute the output accurately? In the case of ordinary
differential equations with separation of variables, we make use of the recent
technique of differential precision to obtain optimal bounds on the stability
of the Newton iteration. The results apply, for example, to algorithms for
manipulating algebraic numbers over finite fields, for computing isogenies
between elliptic curves or for deterministically finding roots of polynomials
in finite fields. The new bounds lead to significant speedups in practice.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2017-01-08**

1701.01994 | cs.SC

Differential (Ore) type polynomials with "approximate" polynomial
coefficients are introduced. These… show more

**2019-05-12**

1905.04614 | cs.SC

Following recent work by van der Hoeven and Lecerf (ISSAC 2017), we discuss
the complexity of linear… show more

**2019-05-10**

1905.04187 | cs.SC

The coefficient sequences of multivariate rational functions appear in many
areas of combinatorics. … show more

**2019-02-13**

1902.04740 | cs.CC

We study the complexity of Boolean constraint satisfaction problems (CSPs)
when the assignment must … show more

**2018-10-22**

1810.09056 | cs.SC

A notion of gcd chain has been introduced by the author at ISSAC 2017 for two
univariate monic polyn… show more

**2019-04-26**

1904.11705 | cs.SC

Let $S\subset R^n$ be a compact basic semi-algebraic set defined as the real
solution set of multiva… show more

**2017-10-23**

1710.08225 | cs.SC

In this article we show how to generalize to the Darbouxian, Liouvillian and
Riccati case the extact… show more

**2018-10-25**

1810.11068 | math.NT

We present a probabilistic Las Vegas algorithm for computing the local zeta
function of a genus-$g$ … show more

**2019-01-20**

1901.06628 | cs.CC

Polynomial factoring has famous practical algorithms over fields-- finite,
rational \& $p$-adic. How… show more

**2017-12-02**

1712.00669 | cs.CG

We present a novel randomized algorithm to factor polynomials over a finite
field $\F_q$ of odd char… show more

**2018-06-15**

1806.05834 | math.NT

We propose a Las Vegas probabilistic algorithm to compute the zeta function
of a genus-3 hyperellipt… show more

**2018-12-17**

1812.06828 | cs.CC

The existence of string functions, which are not polynomial time computable,
but whose graph is chec… show more

**2019-01-31**

1901.11343 | math.CO

It is known that the following five counting problems lead to the same
integer sequence~$f_t(n)$: th… show more

**2018-11-21**

1811.08616 | cs.SC

A lot of information concerning solutions of linear differential equations
can be computed directly … show more

**2018-07-25**

1807.09675 | cs.SC

We present a randomized quantum algorithm for polynomial factorization over
finite fields. For polyn… show more

**2014-04-17**

1404.5525 | cs.NA

In this paper, we study iterative methods on the coefficients of the rational
univariate representat… show more

**2014-07-10**

1407.2802 | cs.SC

A wide range of numerical methods exists for computing polynomial
approximations of solutions of ord… show more