Barycentric Transformation#
In one dimension, barycentric Lagrange interpolation is the most efficient scheme for fixed interpolation nodes[1]. Both determining the interpolating polynomial \(\left( Q_{f,A} \right)\) for \(\left( A = \{0, \ldots, n\} \right)\) and evaluating \(\left( Q_{f,A} \right)\) at any point \(\left( \boldsymbol{x} \in \Omega \right)\) require linear runtime \(\left( \mathcal{O}(n) \right)\). This efficiency is achieved by precomputing the constant barycentric weights, which depend only on the interpolation node locations, not on the function \(\left( f: \Omega \to \mathbb{R} \right)\) and its values.
Minterpy has partially extended the classic barycentric Lagrange interpolation to the multidimensional case. This extension leverages the fact that the transformation from the Lagrange to Newton basis involves structured sparse triangular matrices. Exploiting this structure, as indicated by our preliminary results for the case of \(\left( l_1 \right)\)-degree[2], allows for faster inversion and multiplication of the corresponding matrices compared to the general case, as seen in similar approaches[3][4].
In summary, we aim to reduce the runtime complexity from \(\left( \mathcal{O}(|A|^2) \right)\) for deriving and executing the transformations to \(\left( \mathcal{O}(mn|A| ) \right)\), and further to \(\left( \mathcal{O}(\log(|A|)|A|) \right)\) for \(\left( A = A_{m,n,p}, p = 1, \infty \right)\). Research and implementation enhancements are ongoing to achieve these goals.
References