Source-linked AI summary
Updating and Downdating the Recurrences of Discrete Multiple Orthogonal Polynomials on the Real Line
Amin Faghih, Marc Van Barel, Raf Vandebril
TL;DR
Reconstructing recurrence matrices for discrete multiple orthogonal polynomials from nodes and weights is an inverse eigenvalue problem. The paper develops updating and downdating algorithms, with scaling, that efficiently modify existing matrices and numerically support stable construction of larger recurrences.
Problem
The paper addresses reconstruction of Hessenberg recurrence matrices for discrete multiple orthogonal polynomials from given measure nodes and weights.
Method
It uses structured Hessenberg inverse eigenvalue methods, similarity transformations, eigenvalue deflation, and scaling to update or downdate existing recurrence matrices.
Results
Numerical experiments confirmed accurate and stable matrix construction, with scaling retaining approximately five digits of recurrence accuracy at N = 100.
Takeaways & Limitations
Existing recurrence relations can be reused when nodes are added or removed, avoiding recomputation from scratch under modest inner-product changes.
Takeaways & Limitations
The updating procedure may become numerically unstable when elimination denominators become very small.
Abstract
from arXiv · showhide
We study multiple orthogonal polynomials with orthogonality defined by multiple positive discrete measures on the real line. Focusing on type~I and type~II multiple orthogonal polynomials and their step-line recurrence relations, we consider the reconstruction of the associated banded upper Hessenberg recurrence matrix from given nodes and weights of the measures. We propose efficient updating and downdating procedures that modify an existing recurrence matrix when nodes are added to or removed from the discrete measures. The updating strategy is based on solving an inverse eigenvalue problem, while the downdating procedure relies on an eigenvalue deflation technique inspired by a QR-type of algorithm. Numerical experiments confirm the stability and efficiency of the proposed approaches.
1 Introduction
This paper extends updating and downdating procedures to multiple orthogonal polynomials for positive discrete measures on the real line. It reconstructs and modifies banded upper Hessenberg recurrence matrices from measure nodes and weights using inverse eigenvalue and eigenvalue-deflation techniques.
- Problem setting: Multiple orthogonal polynomials impose orthogonality with respect to r positive discrete measures on the real line and include type I and type II families.Type I MOPs are polynomial vectors, whereas type II MOPs are single polynomials.
- Problem setting: The step-line recurrence is an (r + 2)-term relation represented by an (r + 2)-banded upper Hessenberg matrix.The recurrence coefficients are the entries to be reconstructed.
- Problem setting: Given nodes and weights of discrete measures, the paper reconstructs the associated recurrence matrix as an inverse eigenvalue problem.The nodes and weights correspond to eigenvalues and eigenvectors of the recurrence matrix.
- Contributions: The proposed updating and downdating procedures reuse existing recurrence relations after nodes are added or deleted from the inner product.They are more memory efficient than Lanczos and core transformation methods because they do not store the entire basis.
- Contributions: Updating uses similarity transformations of the Hessenberg recurrence matrix, whereas downdating uses eigenvalue deflation.A novel scaling strategy is introduced to improve numerical stability in the updating procedure.
2 Problem formulation
The section formulates step-line recurrences for type I and type II multiple orthogonal polynomials as structured matrix and inverse eigenvalue problems. It also frames node updates and downdates as corresponding transformations of recurrence matrices.
- 2.1 Step-line recurrences: The paper focuses on step-line indexing, where type I and type II multiple orthogonal polynomials satisfy related recurrence relations.The general framework is introduced for r measures before specializing to r = 2.
- 2.1 Step-line recurrences: For r = 2, the recurrences reduce to four-term relations whose coefficients define a 4-banded upper Hessenberg matrix.The matrix encodes the recurrence coefficients for the step-line polynomial sequence.
- 2.1 Step-line recurrences: The formulation does not impose monicness on type II polynomials, allowing P0(x) to be any nonzero constant and Hessenberg subdiagonal entries to differ from one.This relaxation is presented as providing additional flexibility for numerical stability.
- 2.1 Step-line recurrences: Under uniqueness conditions, the zeros of PN(x) are the measure nodes, and each node zi is an eigenvalue of the recurrence matrix HN.Evaluating the vector-matrix recurrence at the nodes yields the spectral characterization.
- 2.2 Biorthogonality and inverse eigenvalue problem: Biorthogonality converts construction of the type I functions and type II polynomials into a matrix problem involving recurrence coefficients and discrete inner products.The matrix formulation expresses the biorthogonality through products of weight and polynomial evaluation matrices.
- 2.2 Biorthogonality and inverse eigenvalue problem: The proposed updating and downdating procedures modify recurrence matrices when nodes in the discrete inner products are added or removed.They are described as more memory efficient than Lanczos and core-transformation methods because they avoid storing the entire basis, while reusing existing recurrences.
- 2.2 Biorthogonality and inverse eigenvalue problem: The associated inverse eigenvalue problem constructs a banded upper Hessenberg matrix from prescribed eigenvalues and selected entries of right and left eigenvectors.For the discrete inner product, eigenvalues are the nodes, while starting vectors contain specified eigenvector components.
3 Updating the IEP
The updating procedure enlarges an existing IEP solution after adding a node and weights, restores the prescribed 4-banded upper Hessenberg structure with eliminators, and uses diagonal scaling to improve finite-precision stability. Under no-breakdown assumptions, the procedure solves the updated IEP.
- Updating procedure: The update constructs an (N+1)×(N+1) recurrence matrix after introducing an additional node and associated weights, using three stages: extension, biorthogonality enforcement, and structural restoration.The first stage extends all solution matrices; the second imposes biorthogonality with the new weight vectors and perturbs the structure; the third restores the prescribed form.
- Limitations: Very small eliminator denominators can cause breakdown and numerical instability, so the derivation assumes that breakdown does not occur.Under this assumption, the eliminations are repeated until the proper 4-banded upper Hessenberg matrix is achieved and the updated IEP is solved.
- Numerical stabilization: Diagonal scaling balances the norms of corresponding left and right basis columns, reducing condition numbers and improving finite-precision preservation of biorthogonality.The scaling enforces ∥Scaled ˜ wi∥2 ≈∥Scaled ˜vi∥2 for i = 1, 2, . . . , N + 1 while preserving biorthogonality.
4 Downdating the IEP
Downdating removes a prescribed eigenvalue from an existing Hessenberg recurrence matrix through a structured similarity transformation. The isolated eigenvalue is deflated while preserving the required banded upper-Hessenberg form and biorthonormal factors, yielding a solution to the downdate problem.
- Downdating formulation: Downdating is formulated as removing one eigenvalue from the spectrum of an available Hessenberg-matrix solution.The starting solution includes H_N and biorthonormal matrices V_N and W_N.
- Structural constraints: The downdated matrix must remain banded upper-Hessenberg with one subdiagonal and two superdiagonals.The transformation also enforces the required block form and prescribed leading columns of the updated biorthonormal factors.
- Eigenvalue isolation: A structured similarity transformation isolates the prescribed eigenvalue in a leading 1×1 block, making it ready for deflation.The construction uses perfect-shift RL iterations that preserve the biorthogonal structure.
- Downdated solution: The deflated factors eH_N−1, eV_N−1, fW_N−1, and eZ satisfy the downdated problem’s conditions (C2) and (C3).They are obtained after deflating the isolated eigenvalue ˜z.
- Correctness: Condition (C1) is satisfied by uniqueness of the solution established in Proposition 4.2 of the cited reference.This completes the verification of the downdated construction.
5 Numerical experiments
The numerical experiments assess recurrence accuracy and biorthonormality for updating and downdating multiple orthogonal polynomial recurrences. Scaling substantially improves stability for Kravchuk and Hahn sequences, while downdating remains stable under successive node removals.
- Evaluation metrics: The experiments measure recurrence-relation accuracy and loss of biorthonormality for the computed Hessenberg matrix and basis, using the appropriately updated node matrix.The node matrix omits downdated nodes or includes updated nodes.
- Updating experiments: For Kravchuk and Hahn MOPs, the monic setting shows rapidly increasing recurrence and biorthogonality errors as N grows, with essentially exponential deterioration.The experiments compare monic and scaled settings, with the monic case constraining subdiagonal recurrence entries to one.
- Updating experiments: The scaling strategy keeps errors several orders of magnitude smaller with mild growth; at N = 100, about five accuracy digits remain and biorthonormality error stays below 10^-1.This improvement is reported for both Kravchuk and Hahn MOPs.
- Node distributions: At N = 100, the recurrence relation retains approximately five accuracy digits for Chebyshev nodes versus about three for equidistant nodes, while both errors remain controlled.The biorthogonality error grows faster than the recurrence error but remains relatively small.
- Downdating experiments: The downdating procedure remains numerically stable under successive node removals, with recurrence and biorthogonality errors staying between approximately 10^-9 and 10^-11.No noticeable error growth occurs across the considered matrix sizes, starting from a computed 40 × 40 updated solution.
6 Conclusion and future work
The paper presents structured updating and downdating procedures for step-line recurrence matrices of discrete multiple orthogonal polynomials, efficiently handling added or removed measure nodes. Future work will extend the framework beyond step-line recurrences and to more general inner products.
- Conclusion: The proposed procedures construct and modify step-line recurrence relations for discrete multiple orthogonal polynomials on the real line.The problem is reformulated as a structured Hessenberg inverse eigenvalue problem.
- Conclusion: The algorithms efficiently update or downdate an existing (r +2)-banded upper Hessenberg recurrence matrix when nodes are added to or removed from the discrete measures.They use structured similarity transformations and eigenvalue deflation.
- Future work: Future research will extend the framework to MOPs associated with paths beyond the step-line case, including nearest-neighbor MOPs and MOPs on the complex plane.These extensions concern other recurrence structures and domains.
- Future work: Another proposed direction is developing updating and downdating procedures for more general inner products involving derivatives of MOPs.The passage identifies derivative-based inner products as an example.
Funding
The research received partial support from the Research Council KU Leuven and the Fund for Scientific Research – Flanders through specified projects.
- Funding: The Fund for Scientific Research – Flanders supported the research through projects G0A9923N and G0B0123N.The projects addressed low-rank tensor approximation for up- and downdating massive online time series clustering and short recurrence relations for rational Krylov and orthogonal rational functions inspired by modified moments.