Fully-factorized barycentric transformation operator
The barycentric transformation operator matrices from Lagrange to Newton and from Newton to Lagrange are both highly structured and sparse. The matrices are block lower triangular whose each block is also triangular. The size of each block is determined by the splitting in the multi-index set. Below is how the N2L transformation matrix looks like for a polynomial of dimension 4, poly-degree 2, and lp-degree 2.0.
Furthermore, each of the blocks is actually a cropped of the parent block (top corner block) and multiplied by some factors.
We are aware and exploit this structure in Minterpy; instead of storing the whole matrix, we simply store the parent block and the factors (plus positions and sizes for bookkeeping). And, during transformation, instead of reconstructing the whole matrix first, we carry out the operation block-wise.
Yet, it turns out that the matrix of factors also follows similar structure and can be further factorized for more efficient storage and transformation. Below is how the factors matrix looks like for the same polynomial.
In the current version of Minterpy, the factorized transformation operator only exploits one level of factorization, meaning the whole factors are stored as part of the transformation data. As shown by Jannik's initial implementation, further factorization of factors for N2L is possible.
Notes on the current implementation
The current implementation of the (one-level) factorized barycentric transformation operator consists of three parts:
-
transformation data (the required data to carry out the transformation):
- For L2N: 1-dimensional DDS, the factors, the positions (which factors to apply to which location in the full matrix), and the sizes (for cropping).
- For N2L: 1-dimensional Newton monomials, the factors, the positions, and the sizes.
- merging function (the procedure to construct the full array representation of the transformation operator based on the transformation data)
-
transformation function (the procedure to carry out the transformation based on the transformation data)
- In the current implementation, the transformation is carried out block-by-block without doing the merging first. However, the algorithm does not exploit the fact that each block is also a triangular matrix.
In Minterpy, the implementation of factorized barycentric transformation operator includes both L2N and N2L as, although the parent matrix and factors differ in origin, the data structure for transformation and merging is exactly the same.
Fully-factorized implementation
Further factorization seems possible as shown by Jannik's initial implementation for N2L transformation. There are, however, a few things missing before this implementation is included in Minterpy:
- transformation function (we manage to obtain the fully-factorized transformation data for N2L but not sure how to use it for transformation without merging first)
- merging function (we have a draft implementation, this needs to be cleaned up)
- transformation data for Lagrange to Newton transformation
Ideally, the same merging and transformation functions should work regardless whether the transformation data is N2L or L2N as both have the same data structure.