Pyramid algorithms for barycentric rational interpolation

We present a new perspective on the Floater–Hormann interpolant. This interpolant is rational of degree (n,d)(n,d), reproduces polynomials of degree d  , and has no real poles. By casting the evaluation of this interpolant as a pyramid algorithm, we first demonstrate a close relation to Neville's algorithm. We then derive an O(nd)O(nd) algorithm for computing the barycentric weights of the Floater–Hormann interpolant, which improves upon the original O(nd2)O(nd2) construction.