Re: Evaluation of polynomials: precision loss

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Ilya Zakharevich [2019-05-09 13:31]:
> To calculate some Fourier transforms, I need to evaluate polynomials
> of very high degree.  Is PARI going to use Horner’s method?

For a non-complex evaluation point, yes. Else a variant of 3M sticking
to real numbers.

> If so, then the rounding errors would accumulate, right?

Indeed.

> One can fight this with using Horner’s method for short runs only, and
> combine short runs using Horner’s method for a power of argument.
> (Somewhat similar to “a step” of FFT — but without speedups.)

This is not implemented but should improve things, yes. Another
possibility is simply to suitably increase realprecision (and the inputs
precision) for that computation.

> Additionally, for me the point of evaluation is a root of
> unity — which also has numerical errors.  There does not seem to exist
> a way to avoid *these* accumulating for a general polynomial — unless
> one does substpol(P,x^N,x0^N) first (calculating x0^N using
> transcendental functions), right?
> 
> However, the way I implemented substpol() initially, it would not
> optimize for a power of variable — so it may be painfully
> slow — unless something has changed…

It now optimizes for powers of variables.

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`