Nicolae Mihalache-Ciurdea (Université Paris-Est Créteil)

will speak on

Fast Evaluation of Real and Complex Polynomials

Time: 3:00PM
Date: Tue 18th April 2023
Location: Seminar Room SCN 1.25 [map]

Further information

Abstract: We propose an algorithm for quick evaluation of polynomials. It pre-conditions a complex polynomial P of degree d in time O(d log d), with a low multiplicative constant, independent of the precision. Subsequent evaluations of P computed with a fixed precision of p bits are performed in average arithmetic complexity O(\sqrt{d(p+\log d)}) and memory O(dp). The average complexity is computed with respect to points on the Riemann sphere.
The worst case does not exceed the complexity of Horner's scheme.

The proof is based on an inequality concerning concave maps on the interval.


https://ucd-ie.zoom.us/j/65569970448

(This talk is part of the Analysis series.)

PDF notice

Return to all seminars