Recursive algorithms for computing Birkhoff interpolation polynomials

Technical Summary: Recursive Algorithms for Computing Birkhoff Interpolation Polynomials

Problem Statement
The paper addresses the Birkhoff interpolation problem, a generalization of the classical Hermite interpolation problem. Unlike Hermite interpolation, where derivative conditions at each node are contiguous, Birkhoff interpolation imposes no such continuity requirements on the derivatives. This lack of structure renders the problem more complex; specifically, the set of polynomials satisfying homogeneous conditions does not form an ideal, and there is no unified criterion for the regularity of the problem or a direct method to specify the form of the interpolation polynomial. While existing methods like Gaussian elimination can solve these problems, they often incur high computational costs and storage requirements. Furthermore, recent recursive approaches (e.g., RHBPIA) have addressed specific cases but may yield higher-degree interpolation bases than necessary.

Methodology
The authors propose two recursive algorithms, Algorithm 1 and Algorithm 2, based on the theory of the Schur complement and the Sylvester identity. These algorithms generalize the Generalized Recursive Polynomial Interpolation Algorithm (GRPIA), originally designed for Hermite interpolation.

1. Theoretical Framework:

   • The paper defines a "strongly proper interpolation basis," a sequence of polynomials where the first $i$ polynomials form a proper basis for the first $i$ interpolation conditions.
   • Using the Schur complement, the authors derive recursive formulas to compute a Newton-type basis and the corresponding interpolation polynomial. The interpolation polynomial $p_{k-1}(x)$ for the first $k$ conditions is expressed as a Schur complement of a matrix involving the basis polynomials and the interpolation values.
   • The approach utilizes the Sylvester identity to update auxiliary polynomials ($g_{j,k-1}(x)$) recursively, avoiding the need to recompute the entire system at each step.

2. Algorithm 1:

   • Scope: Designed for Birkhoff problems where conditions are composed of evaluation functionals and monomial differential operators (e.g., $\delta_{x_\beta} \circ D_x^\alpha$).
   • Mechanism: It iteratively constructs a Newton-type basis. At each step $k$, it checks a judgment condition: $g^{(\alpha_k)}_{k-2, k-1}(x_{\beta_k}) \neq 0$. This ensures the non-singularity of the associated Vandermonde matrix.
   • Adjustment: If the judgment condition fails, the algorithm increases the degree of the underlying monomial basis (multiplying by $x$) and recomputes until the condition is met.
   • Optimization: The algorithm implicitly embodies Gaussian elimination but restricts calculations to the first $k$ conditions when computing the $k$-th basis, avoiding access to the full lower triangular part of the matrix.

3. Algorithm 2:

   • Scope: Extends Algorithm 1 to handle more general conditions where the differential operator is a differential polynomial (a linear combination of derivatives) rather than a single monomial.
   • Mechanism: It introduces a reordering strategy. If the judgment condition fails for the current condition $L_k$, the algorithm checks subsequent conditions ($L_{k+s}$). If a later condition yields a non-zero value, it swaps the positions of $L_k$ and $L_{k+s}$ to ensure the basis remains strongly proper.
   • Degree Reduction: This reordering capability allows Algorithm 2 to potentially produce lower-degree interpolation polynomials compared to Algorithm 1, which strictly follows the initial ordering.

Key Contributions

• Generalization of GRPIA: The work extends recursive interpolation techniques from Hermite to the broader class of Birkhoff interpolation problems.
• Strongly Proper Basis Construction: The paper provides a constructive method to generate a "strongly proper interpolation basis" and a Newton-type basis, ensuring the problem is well-posed at every recursive step.
• Judgment Condition: A core contribution is the incorporation of a judgment condition to verify the non-singularity of the Vandermonde matrix dynamically during the recursive process.
• Two-Algorithm Approach:
  • Algorithm 1 offers a recursive solution for monomial differential operators with reduced computational overhead.
  • Algorithm 2 handles general differential polynomial conditions and includes a mechanism to reorder conditions to achieve lower-degree solutions.

Results and Performance
The paper validates the algorithms through numerical examples (Examples 1–4) and compares them against traditional Gaussian elimination and the RHBPIA algorithm.

• Computational Efficiency: The recursive approach significantly reduces computational cost and storage space. By processing conditions incrementally and not retaining all auxiliary polynomials, the method avoids the full matrix operations required by Gaussian elimination.
• Degree Reduction: In Example 1, the proposed method yields a minimal-degree interpolation polynomial (degree 3), whereas the RHBPIA method from reference [16] produced a polynomial of degree 6 for the same problem.
• Flexibility: Example 2 demonstrates that Algorithm 2 can reorder conditions to find a lower-degree solution (degree 3) compared to Algorithm 1, which might otherwise require increasing the degree of the basis to satisfy the judgment condition.

Significance and Claims
The authors claim that their recursive approach offers a more efficient alternative to traditional Gaussian elimination for Birkhoff interpolation. By leveraging the Schur complement and Sylvester identity, the method reduces both computational complexity and memory requirements. Furthermore, the introduction of a judgment condition ensures the well-posedness of the problem at each step. The paper positions Algorithm 2 as a significant advancement over existing methods (specifically RHBPIA) by handling general differential polynomial conditions and providing a mechanism to minimize the degree of the resulting interpolation polynomial through condition reordering. The work contributes a unified theoretical framework for constructing interpolation bases in non-ideal interpolation settings.