Approximate Evaluation of a Polynomial on a Set of Real Points
Title | Approximate Evaluation of a Polynomial on a Set of Real Points |
Publication Type | Technical Report |
Year of Publication | 1992 |
Authors | Pan, V. |
Other Numbers | 781 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-92-076.pdf |
Bibliographic Notes | ICSI Technical Report TR-92-076 |
Abbreviated Authors | V. Pan |
ICSI Publication Type | Technical Report |