POD/DEIM Nonlinear model order reduction of an ADI implicit shallow water equations model

Razvan Stefanescu; Ionel Michael Navon

Source-linked AI summary

POD/DEIM Nonlinear model order reduction of an ADI implicit shallow water equations model

Razvan Stefanescu, Ionel Michael Navon

arXiv:1211.2521v1Nov 12, 2012physics.comp-phmath.NA

TL;DR

The reduced shallow-water model still depends computationally on the full model dimension. The paper applies DEIM to address this dependence, reducing CPU time with POD/DEIM ADI and explicit schemes while maintaining comparable errors at 50 DEIM points.

Problem
The reduced shallow-water equations model still has computational complexity dependent on the number of variables in the full model.
Method
The paper applies the discrete empirical interpolation method (DEIM) to reduce the full-dimension dependence of the reduced model.
Results
CPU time was reduced by a factor of 73.91 with POD/DEIM ADI SWE and 68.733 with POD/DEIM EE SWE.
Takeaways & Limitations
POD/DEIM and POD approximation errors are almost identical once the DEIM dimension reaches 50.
Takeaways & Limitations
The POD reduced model can still have computational complexity depending on the original model dimension.

Abstract

from arXiv · show

In the present paper we consider a 2-D shallow-water equations (SWE) model on a $β$-plane solved using an alternating direction fully implicit (ADI) finite-difference scheme on a rectangular domain. The scheme was shown to be unconditionally stable for the linearized equations. The discretization yields a number of nonlinear systems of algebraic equations. We then use a proper orthogonal decomposition (POD) to reduce the dimension of the SWE model. Due to the model nonlinearities, the computational complexity of the reduced model still depends on the number of variables of the full shallow - water equations model. By employing the discrete empirical interpolation method (DEIM) we reduce the computational complexity of the reduced order model due to its depending on the nonlinear full dimension model and regain the full model reduction expected from the POD model. To emphasize the CPU gain in performance due to use of POD/DEIM, we also propose testing an explicit Euler finite difference scheme (EE) as an alternative to the ADI implicit scheme for solving the swallow water equations model. We then proceed to assess the efficiency of POD/DEIM as a function of number of spatial discretization points, time steps, and POD basis functions. As was expected, our numerical experiments showed that the CPU time performances of POD/DEIM schemes are proportional to the number of mesh points. Once the number of spatial discretization points exceeded 10000 and for 90 DEIM interpolation points, the CPU time was decreased by a factor of 10 in case of POD/DEIM implicit SWE scheme and by a factor of 15 for the POD/DEIM explicit SWE scheme in comparison with the corresponding POD SWE schemes. Our numerical tests revealed that if the number of points selected by DEIM algorithm reached 50, the approximation errors due to POD/DEIM and POD reduced systems have the same orders of magnitude.

1 Introduction

The paper combines POD and DEIM to reduce the dimension and nonlinear computational cost of shallow-water equation models. It evaluates the approach for implicit and explicit schemes across discretization and reduction settings.

Numerical schemes: The paper addresses explicit-scheme CFL restrictions by considering an alternating direction implicit method for shallow-water equations.The introduction motivates implicit discretization as a way to avoid time-step restrictions imposed by CFL stability conditions.
Related methods: The paper builds on POD applications to nonlinear flow and shallow-water models and on prior ADI methods for multidimensional problems.The cited background includes POD uses in fluid dynamics and ADI reductions to one-dimensional systems.
Motivation and contribution: POD reduces the dimension of the shallow-water model, but nonlinearities leave reduced-model complexity dependent on the full model size.DEIM is introduced to remove this dependence by approximating nonlinear components using selected entries.
Study design: The study evaluates POD/DEIM for both explicit and implicit shallow-water schemes while varying spatial points, time steps, and basis functions.It also examines invariant conservation, RMSEs, and correlations against full, POD, and POD/DEIM systems.
Motivation and contribution: DEIM replaces orthogonal projection of nonlinear terms with interpolation requiring evaluation of only a few selected components.The paper describes this as the mechanism for restoring the computational reduction expected from POD.

2 Brief description of the Gustafsson ADI method.

The Gustafsson ADI method discretizes the β-plane shallow-water equations on a rectangular mesh through two implicit directional steps. Its nonlinear algebraic systems are solved with a quasi-Newton procedure that reuses Jacobian factorizations between updates.

Stability and formulation: The ADI finite-difference scheme is unconditionally stable for the linearized shallow-water equations and was tested for large CFL condition numbers.The supplied results state stability for the linearized model and report testing at a CFL condition number of 7.188.
Model and discretization: The model uses the β-plane approximation on a rectangular domain with periodic x-direction conditions and zero normal velocity at the y boundaries.The state vector contains velocity components and fluid depth-related variables on the rectangular grid.
ADI scheme: The fully implicit scheme advances the solution through two alternating directional steps and is first order in both time and space.The discretization defines grid and time-step vectors for the approximate shallow-water variables before applying the two-step ADI update.
Nonlinear solve: The nonlinear systems from each ADI step are solved using quasi-Newton iterations whose Jacobians are block cyclic tridiagonal or block tridiagonal.The resulting linear solves use LU decomposition followed by two-stage back substitution.
Nonlinear solve: The quasi-Newton method updates the expensive LU decomposition every M-th time step, making the method efficient when nonlinear iteration counts are small.The experiments use M = 6, and the supplied text reports that even one quasi-Newton iteration can be sufficient at each time step.

3 The POD version of SWE model

The POD formulation constructs reduced shallow-water models by projecting ADI finite-difference equations onto bases derived from solution snapshots. Although this reduces the state dimension, evaluating and projecting nonlinear terms can retain dependence on the full spatial dimension.

POD basis construction: POD bases are constructed from solution snapshots, with separate bases for the velocity components and geopotential.The basis retains leading singular vectors after snapshot decomposition.
Reduced system construction: The reduced SWE system is obtained by replacing the full variables with POD expansions and applying Galerkin projection to the ADI finite-difference model.The projected equations use reduced coordinates and projected linear and nonlinear operators.
Implementation: Coefficient matrices for linear and nonlinear terms can be precomputed and reused throughout the integration interval.This reuse applies to matrices involving the POD bases and spatial-difference operators.
Computational limitation: The POD model still depends on the full dimension nxy because nonlinear evaluation and projection require full-scale operations.The dependence arises from both evaluating nonlinear functions and multiplying them by transposed POD bases.
DEIM motivation: DEIM is introduced to remove the full-dimension dependence by approximating projected nonlinear functions using selected interpolation entries.The approach evaluates only a few nonlinear-term entries and enables precomputation, targeting reduced-model cost independent of the original system size.

ADI/SWE model

DEIM approximates nonlinear functions in the reduced SWE model using POD bases of nonlinear snapshots and selected interpolation indices. Applied to the nonlinear terms, it changes the reduced computational cost from dependence on the full dimension to dependence on the reduced and interpolation dimensions.

DEIM approximation: DEIM approximates each nonlinear function in the reduced SWE system using a basis built from nonlinear snapshots and selected interpolation indices.The procedure determines interpolation rows through an inductive selection algorithm based on residual magnitudes.
Interpolation-index selection: The first DEIM index is chosen at the largest-magnitude entry of the first basis vector, while later indices maximize residual magnitudes.The residual measures the difference between the current basis vector and its interpolation-based approximation.
Implementation: Precomputed coefficient matrices and interpolation operators are reused at every time step in the POD/DEIM reduced system.This reduces the storage and repeated computation associated with projected nonlinear terms.
Computational complexity: The DEIM nonlinear-term cost is O(α(m) + 4mk), independent of the full-order dimension nxy.The reduced system consequently has computational complexity proportional to reduced dimensions rather than the original spatial dimension.

5 Numerical experiments

The experiments evaluate POD/DEIM reduced SWE models for implicit ADI and explicit Euler schemes across discretizations, time steps, and basis dimensions. POD/DEIM substantially reduces computational time while retaining comparable accuracy and integral-invariant behavior.

DEIM reduces computational time by factors of 73.91 for POD ADI SWE and 68.733 for the explicit scheme.The explicit POD/DEIM model was solved with RKF45.
For more than 10000 spatial points and 90 DEIM points, POD/DEIM is faster than POD by a factor of 10.This comparison is reported for CPU time as a function of spatial discretization points.
POD/DEIM is much faster and almost as accurate as POD for the ADI SWE scheme.The experiments report very accurate local, average-relative, and RMSE results for POD/DEIM ADI SWE.
Increasing the number of time steps and snapshots improves solution accuracy, while implicit schemes are slightly more accurate than explicit ones.The implicit schemes were also faster in the reported tests because of the chosen time steps and Newton-iteration settings.
When the DEIM dimension reaches 50, POD and POD/DEIM have almost identical RMSE results.The experiments also report at least a tenfold CPU-time decrease once the POD dimension exceeds 15 for ADI or 5 for explicit SWE.
The reduced systems behave similarly to the full ADI FD SWE scheme regarding conservation of integral invariants.The reported conserved quantities include free-surface height and potential enstrophy, with their evolution depicted in Figure 13.

6 Conclusions

The conclusions report that DEIM reduces POD nonlinear-term costs to depend on reduced dimensions and improves computational efficiency in implicit and explicit SWE schemes. Experiments identify spatial discretization as the dominant CPU-time factor, while POD/DEIM and POD errors become nearly identical at sufficient DEIM dimension.

6 Conclusions: DEIM changes nonlinear-term storage from O(nxyk) in POD to O(mk), with m much smaller than nxy.Projected linear terms require O(k^2) storage in both formulations.
6 Conclusions: The study evaluated DEIM with both fully implicit ADI finite differences and explicit Euler finite differences for SWE.The conclusions characterize the efficiency of DEIM across both schemes.
6 Conclusions: POD/DEIM CPU time was most sensitive to the number of spatial discretization points.The reported experiments varied spatial discretization, time steps, and snapshots.
6 Conclusions: 73.91-fold and 68.733-fold CPU-time reductions were obtained for POD/DEIM ADI and explicit SWE models, respectively.These were the largest reductions reported in the first experiment.
6 Conclusions: At DEIM dimension 50, POD/DEIM and POD reduced systems had almost identical approximation errors.This result was reported across the tested methods and variables.
6 Conclusions: Increasing time steps and snapshots in the second experiment produced higher solution accuracy than in the first experiment.The comparison concerns the experimental settings rather than a separate model formulation.

Appendix

The appendix formalizes the nonlinear ADI SWE discretization, including componentwise matrix multiplication and finite-difference operators. It also records boundary conditions and index restrictions used in the scheme.

Appendix: The appendix rewrites Gustafsson’s nonlinear ADI finite-difference SWE scheme in a more symbolic form.The rewritten scheme uses operators and matrices defined in the discretization.
Appendix: Componentwise multiplication takes two same-sized matrices and multiplies corresponding entries, producing a matrix of the same dimensions.The operation is also called the Hadamard product.
Appendix: The discretization indexes grid points with i, j, and n over Nx, Ny, and NT ranges, approximating w(i∆x, j∆y, n∆t).The appendix also defines related finite-difference operators such as D0y, D+y, and D−y.
Appendix: Periodic x-direction boundary conditions permit central differences and eliminate the need to calculate SWE solutions at i = Nx.The appendix states this consequence explicitly for the x discretization.
Appendix: The nonlinear algebraic equations exclude the v component at j = 1 and j = Ny, where a boundary condition is used instead.The supplied appendix passage identifies the excluded boundary indices and the imposed condition.