Why the adaptive-greedy algorithm for parametric eigenvalue problems
What is on this page. A short statement of the problem the adaptive-greedy algorithm solves, framed in the language of the source work (Alghamdi 2025) and the reduced-basis literature it builds on. Six drivers, in problem-first order: the cost of dense sampling, the structural obstruction posed by eigenvalue crossings, the absence of a standard technique that links eigensolutions across parameters, the prior-art gap for multiple eigenpairs, the role of sparse-grid adaptivity in classifying the global eigensurface, and the algorithm’s place in the reduced-basis greedy lineage. Each section ends with a Sources block naming the references supporting its claims.
Scope. Motivation only. For the technical comparison against alternative solvers, see
method-comparison-1d.md; the open methodological questions that remain are collected in a companion research note (not yet published).
1. Parametric eigenproblems and the cost of dense sampling
A parametric eigenvalue problem (pEVP) asks for the eigenpairs (λ(µ), u(µ)) of a generalised eigenproblem K(µ) u = λ M(µ) u as the parameter µ ranges over a box Ω ⊂ ℝ^d. The matrices K(µ), M(µ) arise from a finite-element discretisation of a PDE whose coefficients depend on µ — material properties, geometric parameters, boundary data. The quantities of interest in design, control, optimisation and uncertainty quantification are functionals of (λ(µ), u(µ)) over the whole box, not at one point.
The naïve approach — assemble and solve at every µ of interest — is prohibitive once Ω is more than coarsely sampled. The cost scales linearly in the number of sample points and each sample carries a full sparse eigensolve. Reduced-basis methods exist precisely because this multi-query regime is otherwise intractable: a small set of high-fidelity snapshots is used to build a surrogate that can be queried cheaply at any µ.
2. Eigenvalue crossings break standard sensitivity theory
When two eigenvalue branches λ_i(µ) and λ_j(µ) collide as µ varies, the assumptions underwriting classical perturbation theory — a simple eigenvalue with a well-separated spectrum — fail at the crossing point. The associated eigenvectors are no longer individually differentiable in µ; only the eigenspace spanned by the colliding branches is smooth, and any specific representative of that eigenspace is a gauge choice. Sensitivity bounds that assume a fixed band ordering are not applicable to a generic neighbourhood of a crossing.
This is not a numerical artefact — it is a feature of the underlying operator. Crossings are generic in parametric problems of dimension two and higher; they occur on codimension-one strata of Ω. Any surrogate that pretends the branches stay individually well-defined across µ will mislabel its bands at every crossing it traverses, silently corrupting any subsequent error estimate.
3. No standard technique links eigensolutions across parameters
Even when crossings are absent, the eigensolver returns eigenvectors at each parameter point under a solver-dependent gauge. The mapping from u_i(µ_a) to “the same band’s” u_i(µ_b) is not given by the eigensolver — ARPACK at µ_a and ARPACK at µ_b make independent choices inside any near-degenerate subspace, and even far from degeneracy a sign or rotation can flip between calls. A surrogate that needs to interpolate eigenvectors across µ therefore needs an additional matching step that the standard FE / eigensolver toolchain does not provide.
Alghamdi (2025) states this gap directly: “available numerical techniques cannot precisely link the eigensolutions at one parameter to those at other parameters.” The adaptive-greedy algorithm closes that gap by pairing a Hungarian-style eigenvector cost matrix with an a-posteriori projection check on the matched pairs — the matching produces a candidate band correspondence and the projection certifies or rejects it before any downstream computation trusts it.
4. Prior reduced-basis greedy methods cover only one eigenpair
Greedy reduced-basis methods for parametric eigenvalue problems exist in the prior literature, but the established constructions target a single eigenpair — typically the smallest, or one band selected ahead of time. The greedy training picks new snapshots to drive down the error of that one band’s reduced approximation across Ω. This suffices when the application only needs a single resonance or the fundamental mode.
The applications motivating the method — global classification of the spectrum over Ω, design problems that need several bands simultaneously, problems where crossings exchange the role of which band is “the one of interest” — require several eigenpairs tracked jointly. The adaptive-greedy method extends greedy reduced-basis sampling to that multi-eigensolution regime by making the verification step per-edge and per-band: an edge is refined if any of its matched bands fails the projection check. This is the gap the algorithm fills.
5. Sparse-grid adaptivity and global eigensurface classification
The output of the greedy loop is not just a surrogate — it is a graph of axis-aligned edges over Ω, refined adaptively until each edge is locally certified. Smooth regions of the eigensurface end up with coarse sampling; regions where bands draw close, cross, or change character get the bisections the verifier requested. Reading off the refinement pattern recovers a global picture of where the eigenvalue structure is non-trivial — a classification of the eigensurface that is produced as a by-product of the algorithm rather than asked for separately.
This is structurally different from a uniform dense sweep, which spends its budget evenly and learns nothing about where the eigensurface is hard. It is also different from a single-band continuation, which can miss crossings entirely because it follows one branch by construction. The sparse-grid adaptive structure is what makes the algorithm informative in higher parameter dimension, where dense sweeps become infeasible long before the eigensurface gets interesting.
6. Place in the reduced-basis greedy lineage
The adaptive-greedy algorithm is the eigenvalue-problem descendant of a well-established line of work on reduced-basis methods for parametric PDEs. The greedy training principle — at each step, add the snapshot that maximises a cheap a-posteriori error estimator — is the Maday–Patera–Rozza–Hesthaven recipe applied to a new operator setting. The Kolmogorov n-width arguments that underwrite reduced-basis approximability transfer; what does not transfer automatically is which error estimator to use, because the source-problem residual at the heart of the classical theory is not the right object for an eigenproblem.
The adaptive-greedy method’s contribution within this lineage is twofold: the verifier is built from the projection of matched eigenvectors rather than a residual, and the greedy refinement runs over a sparse-grid graph of edges so the multi-band structure is preserved through the loop. Both adaptations are forced by the eigenvalue setting — the classical reduced-basis machinery cannot be lifted unchanged.
7. What this page is not
This page is a motivation note, not a literature survey and not a benchmark. For a method-by-method comparison of the adaptive-greedy algorithm against alternative pEVP techniques (uniform dense grids, warm-started LOBPCG, predictor–corrector continuation, Grassmannian subspace continuation, polynomial interpolation of K(µ), classical reduced-basis, FEAST contour integration), see method-comparison-1d.md. The methodological questions that remain open after this project’s validation work against the reference implementation — termination criteria, gauge ambiguity in near-degenerate spectra, the Window-mode verdict interpretation — are examined in a companion research note (not yet published).