Technical Summary: A Parallel Batch Greedy Algorithm in Reduced Basis Methods

Problem Statement

The Reduced Basis Method (RBM) is a prominent technique for the model order reduction of parameterized partial differential equations (PPDEs). A critical component of RBM is the offline training phase, where a reduced basis is constructed by selecting specific parameter samples and computing high-fidelity numerical solutions (snapshots) for them.

In the standard "classical" (weak) greedy algorithm, snapshots are selected sequentially. In each iteration, an a posteriori error estimator is maximized over a training set to identify the next most informative parameter. The corresponding snapshot is then computed and added to the basis. While parallel computing can accelerate the solution of individual snapshots, the selection process itself remains serial. This sequential dependency creates a bottleneck, making the offline phase computationally expensive, particularly for complex problems requiring high-fidelity discretizations.

The paper addresses the challenge of accelerating this offline phase by introducing a parallel batch greedy algorithm. The goal is to select and compute multiple snapshots ($b \ge 2$) simultaneously, thereby leveraging parallel hardware resources more effectively, while ensuring that the resulting reduced basis maintains optimal convergence properties.

Methodology

The authors propose two variants of a parallel batch greedy algorithm, both operating within a Hilbert space framework (with a generalization to Banach spaces provided in the appendix). The core idea is to select a batch of $b$ parameter samples, compute their snapshots in parallel, and then integrate them into the reduced basis using specific filtering mechanisms to avoid adding linearly dependent or redundant information.

1. The Weak Batch Greedy Algorithm

Unlike the strong greedy algorithm, which requires computing the exact distance to the current subspace for all parameters (computationally infeasible), the weak variant uses an error surrogate $r_n(f)$ that bounds the true error $\sigma_n(f)$.

The algorithm proceeds in iterations $\ell$:

1. Batch Selection: Select $b$ parameters. The first is chosen to maximize the error surrogate. The remaining $b-1$ can be chosen by maximizing the surrogate, randomly, or a mix.

2. Parallel Computation: Compute the $b$ corresponding high-fidelity snapshots in parallel.

3. Integration: Add the snapshots to the reduced basis. To prevent the addition of linearly dependent functions (which would yield diminishing returns), the authors introduce two integration strategies:

   • Variant A: Bulk Criterion
     The snapshots are added one by one to the basis. A snapshot is added only if its error surrogate exceeds a fraction $\lambda$ (the bulk parameter) of the current maximum error in the training set. If a snapshot fails this criterion, the rest of the batch is discarded for that iteration. This ensures a guaranteed error decay but reintroduces a degree of serial processing within the batch integration step.

   • Variant B: Proper Orthogonal Decomposition (POD)
     Instead of adding snapshots individually, the algorithm computes the projection errors of all $b$ snapshots relative to the current reduced space. A POD is performed on these projection errors. Only the POD modes (singular vectors) whose singular values exceed a relative threshold $\lambda$ are added to the basis. This allows for the simultaneous addition of multiple linearly independent modes derived from the batch.

2. Theoretical Analysis

The paper provides a rigorous convergence analysis for both variants, extending the known results for the classical weak greedy algorithm (CWG) to the batch setting.

• Convergence Rates: The authors prove that both batch variants preserve the asymptotic convergence rates of the classical greedy algorithm. Specifically, if the Kolmogorov $n$-width $d_n(\mathcal{F})$ decays algebraically ($n^{-\alpha}$) or exponentially ($e^{-c n^\alpha}$), the reduced basis error $\sigma_n(\mathcal{F})$ exhibits the same decay rates.
• Constants: The analysis reveals that the constants in the error bounds depend on the batch size $b$ and the bulk/POD parameter $\lambda$. While the asymptotic rate is preserved, the pre-factors suggest that the reduced basis size may increase moderately compared to the classical method (a trade-off for offline speedup).
• Banach Spaces: The analysis is generalized to Banach spaces using Hahn-Banach functionals, confirming that the bulk criterion variant retains similar convergence properties in this broader setting.

Key Results

The authors validate their theoretical findings through numerical experiments on the linear elliptic thermal block problem, a standard benchmark for model reduction. The experiments utilize the pyMOR library and an MPI-based parallel implementation.

1. Convergence Behavior

• Error Decay: Both the bulk and POD variants exhibit error decay rates nearly identical to the classical weak greedy (CWG) method. The asymptotic convergence is preserved regardless of the batch size $b$ or the parameter $\lambda$.
• Plateaus: For very small values of $\lambda$, "plateaus" in error decay were observed, where the error stagnates with increasing basis size $n$. This suggests that too aggressive a threshold can lead to the inclusion of insufficiently informative snapshots.

2. Computational Efficiency

• Offline Speedup: The primary benefit is a significant reduction in offline wall-clock time. By computing snapshots in parallel, the "Solve" phase of the offline process is accelerated.
  • For the tested problems, the offline time was reduced to less than half of the classical approach with an optimal choice of $\lambda$.
  • The POD variant generally outperformed the bulk criterion variant in terms of total offline time. The bulk criterion requires frequent updates to the reduced model (orthogonalization, projectors) as snapshots are added one by one, which becomes a bottleneck. The POD variant updates the model only once per iteration.
• Online Cost: The introduction of a batch leads to a moderate increase in the size of the reduced basis (typically a 10–30% increase in dimension depending on $\lambda$). Consequently, the online computation time (solving the reduced system) increases slightly but remains negligible compared to the full-order model.
• Break-Even Point: The "break-even point" (the number of queries required for the reduced model to become more efficient than repeated full-order solves) is substantially lower for the batch methods. This indicates that the trade-off between increased online cost and decreased offline cost is highly favorable.

3. Batch Selection and Training Sets

• Selection Strategy: The numerical results suggest that the specific method of choosing the remaining $b-1$ samples in a batch (e.g., random vs. maximizing error) has a minor influence on the convergence rate, provided the first sample is the maximizer.
• Training Set Size: Increasing the size of the training set did not significantly degrade the performance. While larger sets contain more similar snapshots, the effective batch size (the number of snapshots actually added) remained stable.

Significance and Claims

The paper claims that the proposed parallel batch greedy algorithm offers a practical and theoretically sound method to accelerate the offline training phase of Reduced Basis Methods.

• Parallel Efficiency: It successfully transforms the serial bottleneck of snapshot selection into a parallelizable task, fully utilizing available CPU cores without sacrificing the theoretical convergence guarantees of the greedy algorithm.
• Trade-off Management: The authors demonstrate that the slight increase in the reduced basis size (and thus online cost) is a worthwhile trade-off for the substantial reduction in offline computational time. This is particularly beneficial for complex problems where the offline phase is the dominant cost.
• POD Superiority: The numerical evidence suggests that the POD variant is generally more efficient than the bulk criterion variant for parallel implementation, as it minimizes the overhead of repeated model updates during the batch integration.
• Parameter Sensitivity: The efficiency of the method is sensitive to the choice of the bulk/POD parameter $\lambda$. The authors suggest that $\lambda \in [10^{-2}, 10^{-1}]$ works well for the bulk variant, while smaller values ($\lambda \in [10^{-4}, 10^{-2}]$) are suitable for the POD variant.

In summary, the work provides a robust framework for parallelizing the greedy algorithm in RBM, proving that parallelism can be achieved without compromising the asymptotic convergence rates, thereby making RBM more scalable for computationally intensive parameterized PDEs.