PaperlayerView exact revision on arXiv

Source-linked AI summary

Galerkin v. least-squares Petrov--Galerkin projection in nonlinear model reduction

Kevin Carlberg, Matthew Barone, Harbir Antil

arXiv:1504.03749v3math.NA

TL;DR

Galerkin and LSPG differ in whether residual minimization is posed at the time-continuous or time-discrete level, and their comparative analysis had been limited. This paper compares them theoretically and computationally for linear multistep and Runge–Kutta schemes, finding that LSPG accuracy can be best at an intermediate time step matched to the reduced basis.

  • Problem

    Comparative analysis of Galerkin and LSPG ROMs has been limited, especially across broad time-integrator classes and in selecting LSPG parameters such as time step and basis dimension.

  • Method

    The paper performs a theoretical and computational comparison of Galerkin and LSPG ROMs for linear multistep and Runge–Kutta schemes, including representations, equivalence conditions, and time-discrete error bounds.

  • Results

    LSPG ROMs are most accurate for an intermediate time step, and experiments show that this choice can reduce both error and simulation time by an order of magnitude.

  • Takeaways & Limitations

    LSPG time-step selection should be matched to the spectral content of the reduced basis rather than assumed to improve monotonically as ∆t decreases.

  • Takeaways & Limitations

    The a priori error bounds retain dependence on the time instance through the linear-multistep coefficients.

Abstract

from arXiv · show

Least-squares Petrov--Galerkin (LSPG) model-reduction techniques such as the Gauss--Newton with Approximated Tensors (GNAT) method have shown promise, as they have generated stable, accurate solutions for large-scale turbulent, compressible flow problems where standard Galerkin techniques have failed. However, there has been limited comparative analysis of the two approaches. This is due in part to difficulties arising from the fact that Galerkin techniques perform optimal projection associated with residual minimization at the time-continuous level, while LSPG techniques do so at the time-discrete level. This work provides a detailed theoretical and computational comparison of the two techniques for two common classes of time integrators: linear multistep schemes and Runge--Kutta schemes. We present a number of new findings, including conditions under which the LSPG ROM has a time-continuous representation, conditions under which the two techniques are equivalent, and time-discrete error bounds for the two approaches. Perhaps most surprisingly, we demonstrate both theoretically and computationally that decreasing the time step does not necessarily decrease the error for the LSPG ROM; instead, the time step should be `matched' to the spectral content of the reduced basis. In numerical experiments carried out on a turbulent compressible-flow problem with over one million unknowns, we show that increasing the time step to an intermediate value decreases both the error and the simulation time of the LSPG reduced-order model by an order of magnitude.

1. Introduction

The paper compares Galerkin’s time-continuous residual minimization with LSPG’s time-discrete optimization, addressing limited comparative theory across common time integrators. It develops representations and conditions connecting the two approaches.

  • Motivation: High-fidelity simulations are often too expensive for real-time and many-query applications, motivating reduced-order models.ROMs use costly offline training to construct a low-dimensional trial basis and inexpensive online projection for new parameter instances.
  • Galerkin and LSPG: Galerkin projection uses equal trial and test bases and minimizes the ODE residual in the ℓ2-norm at the continuous level.The approach can nevertheless exhibit significant problems in theoretical analyses and numerical experiments.
  • Galerkin and LSPG: LSPG projects after time discretization and minimizes the ℓ2-norm of the time-discrete residual at each time step.With gappy POD, LSPG supports least-squares residual approximation for computationally reduced ROMs.
  • Paper scope: The analysis asks how both ROMs are represented for linear multistep and Runge–Kutta schemes, when they are equivalent, and what error bounds apply.It also examines how time-step and basis-dimension choices affect LSPG performance.
  • Representations: The paper shows that Galerkin projection and time discretization are commutative, while LSPG has a time-continuous representation under certain conditions that depends on ∆t.LSPG derivations are provided for Runge–Kutta schemes.

2. Equivalence conditions •

The paper identifies several conditions linking Galerkin and LSPG ROMs. Equivalence depends on the time integrator or limiting regime, while Galerkin can itself be discrete-optimal under a Jacobian condition.

  • Equivalence: Galerkin and LSPG ROMs are equivalent for explicit time integrators.This result is stated for the paper’s explicit-integrator setting.
  • Equivalence: Galerkin and LSPG ROMs are equivalent in the limit ∆t →0 for implicit time integrators.The equivalence is asymptotic in the time-step limit rather than asserted for arbitrary finite ∆t.
  • Discrete optimality: Galerkin ROMs are discrete optimal when the residual Jacobians are symmetric positive definite.The condition is established through Theorems 5.4–5.6.

3. Error analysis •

The paper derives error bounds for Galerkin and LSPG ROMs across linear multistep and Runge–Kutta schemes, revealing time-step and basis-size effects on LSPG accuracy and cost.

  • Linear multistep schemes: The paper provides local and global a posteriori and a priori error bounds for both ROMs with linear multistep schemes.The analysis allows coefficients to depend on the time instance for multistep methods.
  • Linear multistep schemes: For backward differentiation formulas, LSPG can have a lower local a posteriori error bound because it optimizes over a time window.Galerkin instead performs a time-local optimization.
  • Backward Euler: For backward Euler, an intermediate time step yields the lowest error bound, and larger bases imply a smaller optimal LSPG time step.These results connect time-step selection to reduced-basis dimension.
  • Runge–Kutta schemes: The paper provides global a posteriori and a priori error bounds for both ROMs with Runge–Kutta schemes.The broader comparison covers both specified classes of time integrators.
  • Numerical results: In experiments with over one million degrees of freedom, an intermediate LSPG time step decreased error and simulation time by an order of magnitude.The experiment uses a large-scale compressible fluid-dynamics problem with turbulence modeling.

2. Full-order model

The paper formulates a nonlinear ODE full-order model and its time-discrete representations for linear multistep and Runge–Kutta integrators. These formulations define the residual equations and state updates used by the reduced models.

  • Time-continuous model: The full-order model is an initial-value problem governed by a system of nonlinear ODEs.The state is time dependent, and the velocity function may arise from spatially discretizing a time-dependent partial differential equation.
  • Time discretization: Numerical solution requires time discretization, and the paper considers linear multistep and Runge–Kutta schemes.The resulting full-order model is represented as a time-discrete system.
  • Linear multistep schemes: A linear k-step method defines algebraic residual equations at each time instance using scheme coefficients α_j and β_j.The unknown is equal to the state for the explicit state-update formulation, and β_0 ≠ 0 indicates an implicit method.
  • Runge–Kutta schemes: An s-stage Runge–Kutta scheme defines a system of algebraic stage equations and then explicitly updates the state.Its coefficients determine the scheme, with explicit and diagonally implicit cases defined by zero patterns in a_ij.

3. Galerkin ROM

Galerkin ROMs restrict solutions to a low-dimensional affine trial subspace and enforce continuous ODE-residual orthogonality. They are continuously minimum-residual optimal, and Galerkin projection commutes with time discretization, although discrete optimality is generally lost.

  • Continuous representation: Galerkin ROMs restrict the approximate solution to x0 + Ran(Φ) and enforce the ODE residual to be orthogonal to Ran(Φ).The reduced basis Φ has dimension p ≪ N and orthonormal columns.
  • Continuous optimality: Galerkin projection minimizes the ℓ2-norm of the full-order ODE residual over Ran(Φ) when ΦT Φ = I.This is the continuous optimality property of the Galerkin ROM.
  • Continuous optimality: Enriching the Galerkin trial basis monotonically decreases the minimum-residual objective and the difference between ROM and full-order velocities.The objective is the ℓ2-norm of the full-order ODE residual.
  • Time-discrete representation: Time discretization preserves the Galerkin equations but generally removes their optimization interpretation at the discrete level.The time-discrete Galerkin solution does not generally solve an optimization problem.
  • Commutativity: Galerkin projection and time discretization commute for both linear multistep and Runge–Kutta schemes.Either ordering produces the same reduced discrete equations at each time step.

4. Least-squares Petrov–Galerkin ROM

LSPG performs minimum-residual projection after time discretization, yielding discrete-optimal ROMs for linear multistep and Runge–Kutta schemes. Under specified conditions, these ROMs also admit time-continuous Petrov–Galerkin representations whose test bases depend on the time step.

  • Discrete representation: LSPG computes reduced solutions by minimizing weighted ℓ2-norms of full-order time-discrete residuals.This discrete optimality contrasts with Galerkin’s continuous residual minimization.
  • Discrete representation: The paper derives LSPG time-discrete representations for both linear multistep and Runge–Kutta schemes.The Runge–Kutta derivation is identified as a novel contribution relative to earlier linear-multistep results.
  • Discrete optimality: LSPG basis enrichment monotonically decreases the minimum weighted residual objective for linear multistep and Runge–Kutta schemes.The objective is the weighted ℓ2-norm of the full-order time-discrete residual.
  • Continuous representation: Under certain conditions, LSPG has an ODE representation equivalent to Petrov–Galerkin projection with a time-step-dependent test basis.This representation is established for linear multistep and Runge–Kutta schemes.
  • Continuous representation: LSPG has a time-continuous representation for all explicit and single-stage Runge–Kutta schemes, including forward Euler, backward Euler, and implicit midpoint.The representation is expressed through an appropriate Petrov–Galerkin test basis.

5. Equivalence conditions

Galerkin and LSPG are equivalent for several integrator classes and limiting or structural conditions. These include explicit schemes, vanishing time steps, and cases where residual-Jacobian structure makes the LSPG test basis coincide with the Galerkin trial basis.

  • Explicit integrators: For explicit linear multistep schemes, Galerkin equals LSPG with A = 1/√α0 I.This follows from β0 = 0 and a test basis equal to Φ.
  • Explicit integrators: For explicit Runge–Kutta schemes, Galerkin equals LSPG with A = I.In this case, the LSPG test basis is Φ.
  • Vanishing time step: As ∆t → 0, Galerkin equals LSPG with A = 1/√α0 I for linear multistep schemes and Ai = I for Runge–Kutta schemes.The equivalence follows because both reduced solutions satisfy the same limiting equations.
  • Symmetric-positive-definite structure: For linear multistep schemes, Galerkin equals LSPG with A(z) = U(z), where U is the Cholesky factor of the relevant residual-Jacobian inverse.Under these conditions, the Galerkin solution has the corresponding discrete minimum-residual characterization.
  • Symmetric-positive-definite structure: For diagonally implicit Runge–Kutta schemes, Galerkin equals LSPG with Ai(z) = Ui(z), where Ui is the Cholesky factor of the residual-Jacobian inverse.The equivalence is established under the stated residual-Jacobian conditions.
  • Symmetric-positive-definite structure: Galerkin exhibits discrete optimality for implicit Runge–Kutta schemes when the residual Jacobian is symmetric positive definite and the stated factorization conditions hold.The resulting objective provides a discrete optimality characterization aligned with the LSPG formulation.

6. Error analysis

The paper develops local and global a posteriori and a priori error bounds for Galerkin and LSPG ROMs across linear multistep and Runge–Kutta schemes. The analysis shows that LSPG can obtain smaller a posteriori bounds, while its error depends critically on the time step and reduced-basis spectral content.

  • Linear multistep schemes: The analysis provides local and global a posteriori and a priori error bounds for Galerkin and LSPG ROMs using linear multistep schemes.The bounds include both solution-dependent a posteriori results and a priori results.
  • A posteriori bounds: LSPG can produce a smaller local a posteriori error bound than Galerkin under the conditions of Corollary 6.3 and Theorem 6.1.Discrete-residual minimization can reduce a term appearing in the a posteriori bound because LSPG minimizes the entire normed quantity.
  • A posteriori bounds: The global a posteriori bounds distinguish Galerkin’s orthogonal projection error from LSPG’s solution-dependent oblique projection.The oblique projection can yield smaller error bounds because it is associated with discrete residual minimization.
  • Linear multistep schemes: Time-step-independent global bounds are obtained under additional coefficient conditions for linear multistep schemes, including cases such as backward Euler.Residual-form bounds are also derived under conditions including β_j = 0 for j ≥ 1, which covers backward differentiation formulas.
  • A priori bounds: For a priori bounds, LSPG’s oblique projection cannot generally be linked to minimizing bound terms because the operator is evaluated at the full-order-model solution.The resulting bound may depend on the LSPG ROM solution, so it is not quite an a priori bound in its stated form.
  • Backward Euler: Decreasing the LSPG time step can both decrease and increase the error bound, so the time step should be matched to the reduced basis’s spectral content.Numerical experiments show that an intermediate time step can minimize the error bound.

7. Numerical experiments

The numerical experiments use POD-based Galerkin and LSPG ROMs for a challenging turbulent compressible-flow cavity problem. Galerkin responses become unstable, whereas LSPG produces many stable responses whose accuracy depends strongly on the time step.

  • 7.1. Problem description: The CFD test problem is an unsteady two-dimensional open-cavity Navier–Stokes simulation using a DES turbulence model and 192,816 nodes.The flow is simulated with second-order BDF2 time integration over T = 12.5 time units.
  • 7.3. Reduced-order models: The nominal snapshot time step ∆t⋆ = 0.0015 produces convergence rates near BDF2’s asymptotic value of 2.0 and sub-2% errors in the tested quantities.This verification motivates using ∆t⋆ as the reference time step.
  • 7.3. Reduced-order models: The POD bases use energy criteria yielding dimensions p = 204, 368, and 564, with higher modes expected to capture finer spatial and temporal behavior.The basis is constructed from initial-condition-centered full-order snapshots collected with ∆t⋆ = 0.0015.
  • 7.4. Limiting case: comparison: LSPG responses exhibit a clear dependence on the time step, unlike the expected time-step convergence behavior observed for the Galerkin ROM.The reduced-order verification study is conducted for p = 368 over 0 ≤ t ≤ 0.55.
  • 7.3. Reduced-order models: Galerkin ROMs become unstable for all tested time steps and basis dimensions, while LSPG yields many stable, accurate responses.The instability is identified by encountering negative pressure and is consistent with prior compressible-flow ROM observations.

7.4. Limiting case: comparison

The comparison shows that LSPG approaches Galerkin as ∆t → 0 under the stated weighting, but its error is not necessarily reduced by taking smaller time steps. Instead, basis spectral content and time-step choice jointly determine accuracy.

  • 7.4. Limiting case: comparison: As ∆t → 0, the LSPG pressure response converges to the Galerkin response for the employed weighting A = 1/√α0 I.The comparison uses a Galerkin reference with fixed ∆t = 1.875 × 10^-4 over 0 ≤ t ≤ 1.1.
  • 7.4. Limiting case: comparison: For p = 564, convergence of the LSPG–Galerkin difference to zero is unclear because the tested time steps may be insufficiently small.Larger basis dimensions capture finer temporal behavior and require smaller ∆t to detect convergence.
  • 7.5.1. Spectral content of POD basis: Higher POD modes shift energy toward higher frequencies, so the characteristic time scale generally decreases as the mode number increases.The characteristic scale τ95 is defined from the frequency containing 95 percent of each mode’s energy.
  • 7.5.1. Spectral content of POD basis: The analysis predicts that the optimal LSPG time step should decrease as modes are added to the POD basis.The authors note that systematic calibration could automate time-step selection, but nonlinear interactions complicate this process.
  • 7.5.2. Error-bound assessment: An intermediate ∆t yields the lowest evaluated LSPG error bound regardless of basis dimension, matching the experimentally observed time-step dip.Adding basis vectors reduces projection error more strongly for small time steps than for large ones.

7.6. LSPG ROM performance

LSPG accuracy and computational cost are both optimized at an intermediate time step in the CFD experiments. The same time-step effect persists when GNAT complexity reduction is applied.

  • 7.6. LSPG ROM performance: An intermediate time step produces better LSPG accuracy and faster simulation times than the tested smaller and larger steps.The experiments vary basis dimension, time step, and time interval to assess both error and walltime.
  • 7.6. LSPG ROM performance: As basis dimension increases, the optimal time step decreases, while adding POD vectors does not improve accuracy at large time steps.For large ∆t, the first POD modes already capture coarse phenomena at the relevant temporal scale.
  • 7.7. GNAT: ROM with complexity reduction: GNAT equips LSPG with complexity reduction by approximating residual least squares using a residual basis and selected sample rows.The GNAT formulation uses A = (PΦr)+P.
  • 7.7. GNAT: ROM with complexity reduction: For the GNAT ROM, increasing ∆t from 1.5 × 10^-3 to 6.0 × 10^-3 reduces error from 3.32% to 2.25%.The same change increases computational savings relative to the full-order model from 14.9 to 55.7 core–hours.
  • 7.7. GNAT: ROM with complexity reduction: The GNAT ROM’s lowest error occurs at ∆t = 6.0 × 10^-3, confirming the intermediate-time-step dip under complexity reduction.The sampled mesh contains 4.1% of the original nodes and 3.0% of the original volumes.

7.8. Summary of experimental results

The experiments show that LSPG performance depends strongly on time-step selection, basis dimension, and simulation interval. Intermediate time steps generally improve accuracy and speed, while Galerkin and LSPG exhibit different stability and accuracy patterns.

  • Galerkin ROMs are unstable for long time intervals, whereas LSPG ROMs are unstable only for small time steps.
  • LSPG ROMs are more accurate than Galerkin ROMs over small time windows where Galerkin remains stable.
  • LSPG ROMs achieve their highest accuracy at an intermediate time step, consistent with the theoretical error-bound dip.
  • Adding POD modes incorporates higher-frequency response components, but has little effect on LSPG accuracy at large time steps.
  • The optimal LSPG time step decreases as modes are added and increases as the simulated time interval grows.
  • The GNAT ROM, which includes complexity reduction, also achieves minimal error at an intermediate time step.

8. Conclusions

The paper compares Galerkin and LSPG reduced-order models theoretically and experimentally for linear multistep and Runge–Kutta schemes. Its central conclusion is that LSPG accuracy and stability depend critically on matching the time step to the reduced basis’s spectral content.

  • The study derives time-continuous representations, equivalence conditions, and time-discrete error bounds for Galerkin and LSPG ROMs.
  • Decreasing the time step does not necessarily decrease LSPG error; the time step should instead be matched to the reduced basis’s spectral content.
  • In some experiments, an intermediate time step reduced both LSPG error and simulation time by an order of magnitude.

Appendix

The appendix describes computation of a proper-orthogonal-decomposition basis from normalized snapshots using a thin singular value decomposition.

  • Algorithm 1 computes a POD basis from normalized snapshots.
  • The procedure begins by computing the thin singular value decomposition W = UΣV^T.
  • The snapshot matrix W is represented using the listed snapshot vectors u1 through unw.
  • The selected POD basis consists of the retained vectors u1 through up.
Loading 1504.03749v3…