A new approach to fast polynomial interpolation and multipoint evaluation

AbstractThe 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