A New Approach to Fast Polynomial Interpolation and Multipoint Evaluation

TitleA New Approach to Fast Polynomial Interpolation and Multipoint Evaluation
Publication TypeTechnical Report
Year of Publication1992
AuthorsPan, V., Sadikou A., Landowne E., & Tiga O.
Other Numbers760
Abstract

The fastest known algorithms for the problems of polynomial evaluation and multipoint interpolation are devastatingly unstable numerically because of their recursive use of polynomial divisions. We apply a completely distinct approach to compute approximate solutions to both problems equally fast but with improved numerical stability. Our approach relies on new techniques, so far not used in this area: we reduce the problems to Vandermonde matrix computations and then exploit some recent methods for improving computations with structured matrices.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-92-055.pdf
Bibliographic Notes

ICSI Technical Report TR-92-055

Abbreviated Authors

V. Pan, A. Sadikou, E. Landowne, and O. Tiga

ICSI Publication Type

Technical Report