Fast polynomial evaluation for fmpz_poly/ZZX with arb input

[videlec]

Similarly to #19822 we implement polynomial evaluation for real ball. Contrarily to the case of mpfr/mfpi it needs some non-trivial modification to sage/rings/real_arb.pyx because of loops in import statements.

Depends on #19822

CC: @slel

Component: numerical

Keywords: arb, polynomial

Author: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/19841

[mezzarobba]

comment:1

It may be better (I'm not sure) to do that at the level of generic polynomials (using _evaluate_polynomial()) rather than special-casing polynomials with rational coefficients like you did for intervals. More precisely, real and complex ball could provide an implementation of _evaluate_polynomial() that converts the polynomial to arb's corresponding polynomial types and lets arb do the evaluation. (Actually something like that might have been a better solution in the case of mpfr/mpfi too.)

[videlec]

comment:2

I do not completely understand the end your comment. The code I have written was precisely to avoid any conversion. You can have a look at #19822: there is no type conversion at all (except some NTL -> FLINT integer conversions).

I agree that we have two places for the implementation of IntegerPolynomial.__call__(ArbType):

1. in integer polynomials __call__ (as in #19822)

2. in arb _evaluate_polynomial

I have no strong opinion about what is best. Though I provided a shurtcut p._eval_mpfr_(x) which is useful and avoid type checking. This is does not discard using 1. or 2. for the generic call to __call__.

[fredrik-johansson]

comment:3

We could add some methods to arb to evaluate an fmpz_poly or fmpq_poly for arb or acb input, without conversion overhead.

Using arb's evaluation would definitely be faster at high precision for polynomials with small coefficients, even with conversion overhead, since a faster algorithm than Horner's rule will be used.

[videlec]

comment:4

Replying to @fredrik-johansson:

We could add some methods to arb to evaluate an fmpz_poly or fmpq_poly for arb or acb input, without conversion overhead.

That would be much better than doing the implementation in Sage. However, I think that a template approach would be useful here to do all kind of input/output (NTL, gmp, fmpz, fmpq, mpfr, mpir, arb, ...). There is an (almost dead) ticket #13358 in that direction.

Using arb's evaluation would definitely be faster at high precision for polynomials with small coefficients, even with conversion overhead, since a faster algorithm than Horner's rule will be used.

Right now, my usage is for polynomial of small degree (< 10). Though the template approach would allow different algorithms as well.

[mezzarobba]

comment:5

Replying to @videlec:

I do not completely understand the end your comment. The code I have written was precisely to avoid any conversion. You can have a look at #19822: there is no type conversion at all (except some NTL -> FLINT integer conversions).

Yes, I agree that your implementation must be faster. I was thinking in terms of code complexity rather than running time. But if you think the speed difference is worth it, I have no problem with that!

(As for the case of balls, as Fredrik said, arb has code for polynomial evaluation that will likely work better in some cases at least. I'm not against having special code for the evaluation of polynomials with rational coefficients at arb balls, but I think we should first see if the version using _evaluate_polynomial is fast enough. The “template approach” you mention looks interesting too.)

[slel]

Changed keywords from none to arb, polynomial