An algebraic approach to approximate evaluation of a polynomial on a set of real points (Q1899278)

Making use of algebraic techniques, the author develops an algorithm to approximate (on a fixed bounded set \(X(m)\) of \(m + 1\) real points) a degree \(n\) polynomial \(p(x) = \sum^n_{i = 0} p_i x^i\), within the error bound \(2^{-u} p\), \(p \leq \sum^n_{i = 0} |p_i|\) for a given positive \(u\). This algorithm decreases the record estimate of the algorithm of \textit{V. Rokhlin} [J. Complexity 4, No. 1, 12-32 (1988; Zbl 0646.65094)] which uses \(O(mu + nu^3)\) (infinite precision) arithmetic operations, to \(O(m \log^2u + n \min \{u, \log n\})\), and also improves other known algorithms for multipoint polynomial evaluation. The algorithm can be performed over abstract rings or fields and is furthermore applicable to algebraic and numerical computing.