Publication Details
Title: A New Approach to Fast Polynomial Interpolation and Multipoint Evaluation
Author: V. Pan, A. Sadikou, E. Landowne, and O. Tiga
Group: ICSI Technical Reports
Date: August 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-055.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-92-055
Bibliographic Reference:
V. Pan, A. Sadikou, E. Landowne, and O. Tiga. A New Approach to Fast Polynomial Interpolation and Multipoint Evaluation. ICSI Technical Report TR-92-055, August 1992
Author: V. Pan, A. Sadikou, E. Landowne, and O. Tiga
Group: ICSI Technical Reports
Date: August 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-055.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-92-055
Bibliographic Reference:
V. Pan, A. Sadikou, E. Landowne, and O. Tiga. A New Approach to Fast Polynomial Interpolation and Multipoint Evaluation. ICSI Technical Report TR-92-055, August 1992