PaperlayerView exact revision on arXiv

Source-linked AI summary

Model reduction for transport-dominated problems via online adaptive bases and adaptive sampling

Benjamin Peherstorfer

arXiv:1812.02094v2math.NA

TL;DR

Transport-dominated problems are difficult to reduce because propagating structures require high-dimensional approximation spaces. The paper introduces AADEIM, which adapts local reduced bases online using adaptively selected full-model samples. Its analysis links greater spatial locality to fewer required samples, while numerical results report applicability across problems and speedups of up to one order of magnitude.

  • Problem

    Transport-dominated problems exhibit high-dimensional features that make traditional low-dimensional model reduction ineffective.

  • Method

    AADEIM uses online adaptive bases for local-in-time reduction and adaptive sampling to derive basis updates from selected full-model components.

  • Results

    Numerical results show applicability to a wide range of problems, faithful approximation under changing parameters, and significant speedups over full and static reduced models.

  • Takeaways & Limitations

    The faster local coherence decays, the fewer samples are required to adapt the reduced spaces.

  • Takeaways & Limitations

    AADEIM has online costs that scale with the full-model dimension and is therefore not online efficient in the traditional model-reduction sense.

Abstract

from arXiv · show

This work presents a model reduction approach for problems with coherent structures that propagate over time such as convection-dominated flows and wave-type phenomena. Traditional model reduction methods have difficulties with these transport-dominated problems because propagating coherent structures typically introduce high-dimensional features that require high-dimensional approximation spaces. The approach proposed in this work exploits the locality in space and time of propagating coherent structures to derive efficient reduced models. Full-model solutions are approximated locally in time via local reduced spaces that are adapted with basis updates during time stepping. The basis updates are derived from querying the full model at a few selected spatial coordinates. A core contribution of this work is an adaptive sampling scheme for selecting at which components to query the full model to compute basis updates. The presented analysis shows that, in probability, the more local the coherent structure is in space, the fewer full-model samples are required to adapt the reduced basis with the proposed adaptive sampling scheme. Numerical results on benchmark examples with interacting wave-type structures and time-varying transport speeds and on a model combustor of a single-element rocket engine demonstrate the wide applicability of the proposed approach and runtime speedups of up to one order of magnitude compared to full models and traditional reduced models.

1. Introduction

Transport-dominated problems develop high-dimensional features that defeat traditional low-dimensional model reduction, so this work exploits their local structure with adaptive bases and sampling.

  • Propagating structures in convection-dominated flows and wave phenomena produce high-dimensional features, yielding high Kolmogorov n-widths.
  • Nonlinear reduced models often remain expensive because nonlinear terms scale with the full solution dimension, motivating empirical interpolation and DEIM.
  • The analysis relates residual locality in space to the number of samples required for adaptive basis construction.
  • The approach derives basis updates by selecting which full-model components to sample.
  • Numerical examples report speedups of up to one order of magnitude over full-model solutions and traditional static reduced models.

2. Preliminaries

Classical empirical-interpolation reduction relies on globally low-rank trajectories, but advection can require large bases because transport moves localized features through space.

  • Projection-based reduction constructs a low-dimensional basis and projects the full-model equations onto it.
  • The discretized full model advances an N-dimensional state through potentially nonlinear implicit time-step equations.
  • DEIM evaluates nonlinear operators at selected interpolation points and reconstructs the remaining components from a reduced basis.
  • Local trajectories can have rapidly decaying singular values and residuals, motivating online basis updates from only a few samples.
  • In the advection example, at least n ≥ 200 basis vectors are needed for projection error below 10^-15 in the Euclidean norm.

3. Exploiting local structure via online adaptive basis updates

AADEIM exploits temporal locality through online adaptive bases and spatial locality through adaptive sampling to build reduced models for transport-dominated systems.

  • AADEIM targets transport-dominated full models by combining online adaptive bases with adaptive sampling.
  • The method uses local low-rankness to update DEIM bases and local coherence to derive those updates from few full-model samples.

3.1. Local structure in transport-dominated problems

For moving localized structures, local trajectories are more compressible than global trajectories, and their DEIM residuals concentrate in a few spatial components.

  • A local trajectory’s singular values decay orders of magnitude faster than those of the global trajectory in the advection example.For window size w = 500, the local trajectory is compared with the global trajectory.
  • Local low-rank structure means local trajectory singular values decay rapidly even when global trajectory singular values decay slowly.
  • The squared DEIM residual decays rapidly, indicating that residual energy is localized in only a few components.
  • This residual localization implies that local DEIM basis corrections need to target only a small number of components.

3.2. Exploiting local low-rank structure: Basis updates

The method adapts local DEIM spaces online by using low-rank ADEIM basis updates derived from sampled residual information and surrogate full-model states. The analysis bounds the distance between the target and adapted spaces under stated rank and regularity assumptions.

  • Online adaptation: At each time step, the DEIM basis is adapted through an additive low-rank update, and interpolation points are recomputed from the updated basis.The online procedure is initialized with U1 and P1, then applies ADEIM updates and QDEIM point selection during time stepping.
  • ADEIM update: ADEIM chooses the rank-r update to minimize the residual of approximating Fk at the sampled components in the Frobenius norm.The coefficient matrix Ck remains fixed during the update, avoiding nonlinear interactions between the updated coefficients and basis.
  • Surrogate information: Because recent full-model states are unavailable online, the method constructs Fk from sampled evaluations and DEIM approximations that serve as state surrogates.The surrogate vectors approximate recent full-model states, while Fk collects the resulting information for basis adaptation.
  • Error analysis: The analysis measures adaptation quality by the distance between the target subspace ¯Uk+1 and the adapted space Uk+1.This distance is symmetric and invariant under orthogonal basis transformations, allowing comparison of the represented subspaces rather than particular bases.
  • Error analysis: Under full-rank and rank assumptions, Proposition 1 bounds the adapted-space error using the sampled residual and the smallest non-zero singular value of Fk.The result applies when Fk has rank n and its columns lie in the n-dimensional target space.

3.3. Exploiting local coherence: Adaptive sampling

Adaptive sampling selects spatial components with the largest residual contributions to update the basis efficiently. The analysis links sampling efficiency to residual and local-coherence decay, with probabilistic guarantees under specified assumptions.

  • Residual-based sampling: The sampling points are selected by ordering component-wise residuals from largest to smallest and choosing the first m components.This strategy minimizes the bound’s decay factor for full-rank ADEIM updates.
  • Residual-based sampling: For full-rank updates, selecting the largest-residual components is optimal because it minimizes the bound ρk.The optimality statement concerns the bound governing the adapted-space error.
  • Residual decay: If the residual decays rapidly, the adapted-space error bound decays at least as rapidly with the number of sampling points m.Proposition 2 formulates this result for exponential residual decay and connects the required sample count to that decay.
  • Residual decay: The sampling count can be chosen so that the adapted-space distance satisfies d(¯Uk+1, Uk+1) ≤ ǫ.The guarantee follows from the proposition’s bound and the stated choice of m.
  • Local coherence: The analysis relates local coherence decay to the decay of the adapted-space error bound and derives a probabilistic sample requirement.The result uses random-space assumptions and bounds the condition number of the associated Gaussian coefficient matrix with probability at least 1 − δ.
  • Scope: The method is most directly suited to spatially local moving structures; globally distributed new features may require m = N or multiple local updates.Multiple local updates can have a similar effect to one global update because sampling prioritizes the largest residual components.

3.4. Practical considerations and algorithm

AADEIM initializes from a short full-model trajectory, then advances with locally adapted reduced bases and adaptive sampling. Its online costs still scale with the full-model dimension, but economical full-model evaluations and lower-dimensional spaces can provide speedups.

  • Initialization: AADEIM initializes its DEIM interpolant from winit full-model time steps, avoiding an offline phase and explicit parameterization.The initial basis and interpolation points are constructed from the corresponding full-model states.
  • Adaptive sampling: At adaptation iterations, AADEIM evaluates the residual across components, ranks their squared row norms, and updates the basis and sampling points from selected components.Between sampling-point updates, residual evaluations are restricted to the current sampling points.
  • Parameter choices: The window size must satisfy w ≥ n, while smaller windows can accelerate singular-value decay and potentially reduce adaptive-space error.The analysis requires the relevant trajectory matrices to span n-dimensional spaces.
  • Algorithm: The algorithm computes a local n-dimensional POD basis, selects QDEIM interpolation points, and advances subsequent steps with the reduced model.The first winit trajectory columns use the full model; later columns are produced by the adaptive reduced model.
  • Online efficiency: Online costs scale with N, but sampling-point adaptation occurs in K/z iterations and local adaptation can enable lower-dimensional spaces than static reduced models.The approach therefore has potential speedups compared with static reduced models and full models, as demonstrated numerically.
  • Advection illustration: For the advection example, residual norms and local-coherence bounds decay rapidly, while the corresponding curves track the residual and local-coherence behavior.These plots connect residual decay with the local coherence of the spaces used for adaptation.

4. Numerical results

The numerical section evaluates AADEIM on an advection problem, a time-varying Burgers’ problem, and a rocket-combustor model. The advection results show that adapted-space error follows residual decay, while low-rank updates can cause its bounds to level off.

  • Examples: AADEIM is demonstrated on an advection equation, interacting-wave Burgers’ equation, and a rocket-combustor model.The Burgers’ setup includes time-varying viscosity and transport-direction coefficients.
  • Advection equation: In the advection experiment, residual decay is inherited from the decay of local coherence, as predicted by Lemma 2.The plotted residual and its bound provide evidence for this relationship.
  • Advection equation: For ADEIM updates with rank r = 1, 2, 3, adapted-space error is plotted against the number of sampling points m.When r < 3, the error bound levels off because later singular values dominate the decay factor.
  • Advection equation: The fast decay of adapted-space error with m is inherited from fast residual decay, demonstrating Proposition 2.The residual is shown as the dashed curve in Figure 4.
  • Burgers’ example: The Burgers’ example varies viscosity and transport direction periodically over time, with nominal viscosity µ = 3 × 10^-3.Figure 5 displays these coefficients only through t = 0.2 because of their periodicity.

4.2. Burgers’ equation with time-varying viscosity

For Burgers’ equation with time-varying viscosity and transport direction, AADEIM exploits local low-rank structure to obtain accurate reduced models with sparse adaptive sampling. It achieves substantial speedups across model sizes and remains effective under different update and initialization choices.

  • Problem setup: The time-varying Burgers’ problem contains two right-propagating waves that begin interacting around t = 0.7.The transport direction and viscosity also change over time.
  • Local structure: Local trajectory singular values decay orders of magnitude faster than global-trajectory singular values, indicating a local low-rank structure.For local spaces of dimension n = 8, the residual rows also decay rapidly.
  • Performance of AADEIM: With n = 8 and m = 96, AADEIM reaches error below 10^-1 and about one-order-of-magnitude speedup over the full model.Increasing m from 96 to 608 reduces the error from 10^-1 to 10^-2 without significant runtime increase.
  • Initialization: AADEIM error remains near 10^-2 across a wide range of initial window sizes, although overly large windows can lose local low-rank structure and accumulate error.The initial window size is therefore a tuning parameter for initializing basis adaptation.
  • Performance with respect to full-model dimension: Across N ∈ {256, 512, 1024, 2048}, AADEIM achieves about one-order-of-magnitude speedups while maintaining error below 10^-2.The sampling count grows linearly with N to preserve similar error behavior with respect to m/N.
  • Performance with respect to updates with SVD: AADEIM achieves up to 30% runtime reduction compared with Full+SVD at comparable error by evaluating the full-model right-hand side at only a few components.When Full+SVD evaluates the right-hand side less frequently, it becomes 2–8% faster but up to one order of magnitude worse in error than AADEIM.

4.3. Combustion model

The combustor experiment evaluates AADEIM on a parameterized single-element rocket combustor with pressure oscillations that vary across the heat-release parameter domain. AADEIM provides substantial speedups and remains effective across parameter changes and compared with uniform sampling.

  • Problem setup: The combustor model studies pressure-oscillation growth at a monitoring point, relevant to avoiding combustion instabilities and unbounded amplitudes.The heat-release parameter µ controls amplification, with µ ∈ [2, 4.2].
  • Parameter dependence: Solutions vary significantly across µ ∈ [2, 4.2], with µ = 3.8 appearing to enter a limit-cycle oscillation.The parameter sweep therefore covers qualitatively different solution behavior.
  • Parameter sweep: Across the parameter sweep, AADEIM shows significant speedups and the adaptive sampling scheme achieves orders-of-magnitude lower errors than uniform sampling.These results support robustness with respect to changes in the heat-release parameter.
  • Performance: At µ = 3.8, AADEIM achieves about 6× speedup over the full model, while the static reduced model is slower than the full model.The comparison uses AADEIM with n = 8 and m ∈ {20, 30, 40, 50}, versus static models with n ∈ {60, 70, 80, 90, 100}.

5. Conclusions

AADEIM exploits locality in time and space through adaptive basis updates and sampling, yielding reduced models without an offline construction phase. Its analysis connects spatial locality to sampling requirements, while numerical results show broad applicability and runtime speedups.

  • AADEIM exploits locality in time through adaptive basis updates and locality in space through adaptive sampling.
  • Faster decay of local coherence requires fewer samples to adapt the reduced spaces.
  • AADEIM reduced models are implicitly parametrized, adapting online to parameter changes without an offline model-construction phase.
  • Numerical results show AADEIM applies to a wide range of problems and achieves significant runtime speedups over full and traditional static reduced models.
  • Future work includes adapting reduced-space dimensions and time windows, comparing adaptive basis schemes, and determining samples required per adaptation step.

A. Analytic example with local low-rank structure

The analytic example shows that a globally translating discontinuity resists rapid low-dimensional approximation, whereas restricting the time interval recovers exponentially accurate local approximation.

  • No n-dimensional space approximates the full time-domain solutions with error decay faster than 1/√n.
  • On the shortened interval [0, T/ζ], the reduced space is spanned by snapshots sampled at equally spaced times t_i = ih.Here h = (T/ζ)/n.
  • Choosing ζ = e^n yields local approximation error in O(e^-n), demonstrating recoverable local low-rank structure.

B. Helper functions for Algorithm 1

The helper functions provide interpolation-point selection with QDEIM and online basis adaptation with ADEIM, including residual-based update-rank determination.

  • QDEIM: QDEIM selects interpolation points from a reduced basis matrix U using a QR factorization of U^T.
  • QDEIM: The QDEIM procedure returns the selected interpolation-point index matrix P.
  • ADEIM: ADEIM computes coefficients at interpolation points and forms the residual used for basis adaptation.
  • ADEIM: ADEIM determines the update rank from the residual singular values and applies the resulting updates before returning U and P.
Loading 1812.02094v2…