Transformation Between Bases#
If an \(m\)-dimensional polynomial \(Q \in \Pi_A\), where \(A \subseteq \mathbb{N}^m\), is given in one of the supported bases, you might want to transform it into another representation to leverage specific properties. For instance, canonical polynomials are familiar while Newton polynomials are more stable and accurate to evaluate.
On this page, we outline how the underlying theorem how such a transformation is carried out.
Theorem: Basis transformations#
Let \(A= A_{m,n,p}\,, m,n \in \mathbb{N}\,, p > 0\) be a complete multi-index set, \(P_A \subseteq \Omega\) be unisolvent nodes, and \(Q \in \Pi_A\) be a polynomial. Then:
Lower triangular matrices \(\mathrm{NL}_A, \mathrm{LN}_A \in \mathbb{R}^{|A|\times |A|}\) can be computed in \(\mathcal{O}(|A|^3)\) operations, such that
\[\mathrm{LN}_A \cdot\mathrm{NL}_A = \mathrm{I} \,, \quad \mathrm{NL}_A \cdot \boldsymbol{c}_{\mathrm{nwt}} = \boldsymbol{c}_{\mathrm{lag}}\,, \quad \mathrm{LN}_A\cdot \boldsymbol{c}_{\mathrm{lag}} = \boldsymbol{c}_{\mathrm{nwt}} \,,\]where \(\boldsymbol{c}_{\mathrm{lag}} = (c_{\mathrm{lag}, \boldsymbol{\alpha}})_{\alpha \in A} \in \mathbb{R}^{\lvert A \rvert}\) and \(\boldsymbol{c}_{\mathrm{nwt}} = (c_{\mathrm{lag}, \boldsymbol{\alpha}})_{\alpha \in A} \in \mathbb{R}^{\lvert A \rvert}\) are the Lagrange coefficients and the Newton coefficients of \(Q\), respectively.
Upper triangular matrices \(\mathrm{CL}_A, \mathrm{CN}_A \in \mathbb{R}^{\lvert A \rvert \times \lvert A \rvert}\) can be computed in \(\mathcal{O}(\lvert A \rvert^3)\) operations, such that
\[\mathrm{CL}_A \cdot \boldsymbol{c}_{\mathrm{can}} = \boldsymbol{c}_{\mathrm{lag}}\,, \quad \mathrm{CN}_A \cdot \boldsymbol{c}_{\mathrm{can}} = \boldsymbol{c}_{\mathrm{nwt}}\,,\]where \(\boldsymbol{c}_{\mathrm{can}} = (c_{\mathrm{can}, \boldsymbol{\alpha}})_{\alpha \in A} \in \mathbb{R}^{\lvert A \rvert}\) denotes the canonical coefficients of \(Q\).
Due to their triangular structure, the inverse matrices \(\mathrm{NC}_A =\mathrm{CN}_A^{-1}\), \(\mathrm{LC}_A =\mathrm{CL}_A^{-1}\) can be computed efficiently and accurately in \(\mathcal{O}(\lvert A \rvert^2)\) time, providing realizations of the inverse transformations.
Further relationships#
If the unisolvent nodes \(P_A\) are fixed, all matrices can be precomputed. The columns of \(\mathrm{NL}_A\) are given by evaluating the Newton polynomials on the unisolvent nodes, that is,
Thus, the above theorem enables both efficient and numerically accurate computations. Conversely, the Multidimensional Divided Difference Scheme (DDS) can be used to interpolate the polynomial in the Lagrange basis \(L_{\boldsymbol{\alpha}} = \sum_{\boldsymbol{\beta} \in A} d_{\boldsymbol{\alpha}, \boldsymbol{\beta}} N_{\boldsymbol{\beta}}\), \(\alpha \in A\) expressed in the Newton basis. This process yields the columns of \(\mathrm{LN}_A\), that is,
With respect to the canonical basis,
coincides with the classic Vandermonde matrix[1].
Moreover, the columns of \(\mathrm{CN}_A\) are given by applying DDS to the canonical basis polynomial \(\Psi_{\mathrm{can}, \boldsymbol{\alpha}}\) evaluated at the unisolvent nodes.
Triangular matrices
All matrices presented above are of recursive triangular sparse structure, which enables numerically accurate precomputation of the sub-matrices and helps avoid storage issues.
Consequently, the explicit structure of the matrices can be condensed into barycentric transformations, which perform much faster than classic matrix multiplication. This results in more efficient polynomial interpolation and evaluation. A preliminary implementation of these fast transformations is already utilized in Minterpy.
References