An algebraic approach to approximate evaluation of a polynomial on a set of real points
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.
scientific article; zbMATH DE number 803462
scientific article