ML p(r)ior | On p-adic differential equations with separation of variables

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.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2017-01-08

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

Highlights - Most important sentences from the article

2019-05-12

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

Highlights - Most important sentences from the article

2019-05-10
1905.04187 | cs.SC

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

Highlights - Most important sentences from the article

2019-02-13

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-04-26

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-01-20

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

Highlights - Most important sentences from the article

2017-12-02

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

Highlights - Most important sentences from the article

2018-06-15

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-01-31

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

Highlights - Most important sentences from the article

2018-11-21
1811.08616 | cs.SC

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

Highlights - Most important sentences from the article

2018-07-25
1807.09675 | cs.SC

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

Highlights - Most important sentences from the article

2014-04-17

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

Highlights - Most important sentences from the article

2014-07-10

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