Publication Details
Title: Approximate Evaluation of a Polynomial on a Set of Real Points
Author: V. Pan
Group: ICSI Technical Reports
Date: November 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-076.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-076
Bibliographic Reference:
V. Pan. Approximate Evaluation of a Polynomial on a Set of Real Points. ICSI Technical Report TR-92-076, November 1992
Author: V. Pan
Group: ICSI Technical Reports
Date: November 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-076.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-076
Bibliographic Reference:
V. Pan. Approximate Evaluation of a Polynomial on a Set of Real Points. ICSI Technical Report TR-92-076, November 1992