Approximate Evaluation of a Polynomial on a Set of Real Points

TitleApproximate Evaluation of a Polynomial on a Set of Real Points
Publication TypeTechnical Report
Year of Publication1992
AuthorsPan, V.
Other Numbers781

The previous best algorithm for approximate evaluation of a polynomial on a real set was due to Rokhlin and required the order of mu + (nu^3) infinite precision arithmetic operations to approximate [on a fixed bounded set X(m) of m + 1 real points] a degree n polynomial p(x) = (sum (superscript n) (subscript i=0)) (p subscript i) (x superscript i) within the error bound (2 superscript -u) (sum (superscript n) (subscript i=0)) |p subscript i|. We develop an approximation algorithm, which decreases Rokhlin's record estimate to O(m (log superscript 2) u + n min (u, log n)). For log u = o(log n), this result may also be favorably compared with the record bound O((m+n) (log superscript 2) n) on the complexity of the exact multipoint polynomial evaluation. The new algorithm can be performed in the fields (or rings) generated by the input values, which enables us to decrease the precision of the computations [by using modular (residue) arithmetic] and to simplify our computations further in the case where u = O(log n). Our algorithm allows NC and simultaneously processor efficient parallel implementation. Because of the fundamental nature of the multipoint polynomial evaluation, our results have further applications to numerical and algebraic computational problems. By passing, we also show a substantial improvement in the Chinese remainder algorithm for integers based on incorporating Kaminski's fast residue computation.

Bibliographic Notes

ICSI Technical Report TR-92-076

Abbreviated Authors

V. Pan

ICSI Publication Type

Technical Report