Randomized model order reduction

Alessandro Alla, J. Nathan KutzAdvances 2019 · DOI

TL;DR

This paper introduces a novel approach to accelerate the computationally expensive offline stage of model order reduction (MOR) by leveraging randomized linear algebra techniques. By employing randomized Singular Value Decomposition (rSVD) and compressed sensing, the authors significantly reduce the computational cost of constructing basis functions for Proper Orthogonal Decomposition (POD) and Dynamic Mode Decomposition (DMD), leading to faster and more efficient surrogate models for complex dynamical systems.

What Problem Does This Paper Address?

Model order reduction (MOR) is a crucial technique for tackling high-dimensional dynamical systems and partial differential equations (PDEs) that arise in many scientific and engineering applications. MOR aims to create low-dimensional "surrogate" models that capture the essential dynamics of the original system, enabling faster simulations. The standard MOR workflow involves an "offline stage" where basis functions are computed to project the high-dimensional system into a low-dimensional subspace, followed by an "online stage" where the reduced model is evaluated. The offline stage, particularly the computation of basis functions using methods like Singular Value Decomposition (SVD), can be prohibitively expensive, especially for systems with millions or billions of degrees of freedom. This computational bottleneck limits the widespread adoption and application of MOR. This paper addresses this challenge by proposing efficient, randomized algorithms to accelerate the offline stage without sacrificing accuracy.

Methods

The core contribution of this paper lies in the application of randomized linear algebra techniques to accelerate the offline stage of MOR. Specifically, the authors propose:

  • Randomized Singular Value Decomposition (rSVD): Instead of using the standard, computationally intensive SVD to find the basis functions for POD, the paper advocates for rSVD. rSVD uses random projections to construct a compressed matrix that approximates the original data matrix, from which a low-rank decomposition can be efficiently computed. This significantly reduces the computational cost and memory requirements.
  • Compressed Sensing for Dynamic Mode Decomposition (DMD): The paper also integrates compressed sensing ideas to speed up the computation of DMD basis functions. This involves using sparse measurements of the data to reconstruct the necessary information for DMD, thereby avoiding the need to process the full high-dimensional dataset.
  • Compressed POD and Compressed POD-DEIM: Building upon rSVD, the authors introduce compressed versions of POD and POD-DEIM. These methods leverage rSVD to compute the POD basis functions and the basis for the nonlinear terms (in the case of POD-DEIM) more efficiently.
  • Compressed DMD (cDMD): This method applies compressed sensing principles to the DMD framework, enabling the computation of DMD basis functions from sparse measurements.

The paper outlines algorithms for these methods, demonstrating how they can be integrated into existing MOR frameworks. The key idea is to exploit the fact that the target rank of interest for MOR is often much smaller than the dimension of the original system.

Datasets

The paper does not introduce new benchmark datasets. Instead, it uses numerical examples derived from:

  • Test 1: Semi-Linear Parabolic Equation: A partial differential equation (PDE) is discretized using finite differences, resulting in a system of ordinary differential equations (ODEs) of the form (2.1). The dimension of the full problem is varied, with an initial setup of n=10000.
  • Test 2: Parametric Elliptic Equation: Another PDE is discretized using finite differences, leading to a system of nonlinear equations. The dimension of this discretized problem is n=2500.

These examples serve to evaluate the performance and accuracy of the proposed randomized MOR techniques against standard methods.

Key Insights and Ideas

  • Randomization as a Game-Changer for Offline MOR: The paper strongly advocates for randomized linear algebra as a powerful tool to overcome the computational bottleneck of the offline stage in MOR. This is a significant shift from relying solely on deterministic methods like SVD.
  • Significant Speedups Achieved: The core insight is that by using randomized techniques, substantial computational savings (orders of magnitude) can be achieved in the offline stage, making MOR more practical for larger and more complex systems.
  • Accuracy is Largely Preserved: Despite the computational gains, the proposed randomized methods maintain high accuracy, often comparable to or negligibly different from their deterministic counterparts. This is crucial for the validity of the surrogate models.
  • Compressed Sensing Enhances DMD: The integration of compressed sensing with DMD offers a new avenue for efficient model reduction, particularly for systems where dynamic mode decomposition is a suitable tool.
  • The "Offline" Stage is the Key Target: The paper correctly identifies the offline stage as the primary area where computational improvements are most impactful for the overall MOR workflow, as it is typically the most expensive part.

Key Results

The paper presents numerical results demonstrating the effectiveness of the proposed methods:

  • CPU Time Reduction: Figures 5.3 and 5.4 (for Test 1) and Figure 5.7 (for Test 2) clearly show that the compressed/randomized methods (cPOD, cPOD-DEIM, cDMD) achieve significant speedups in CPU time compared to their standard counterparts (POD, POD-DEIM, DMD). For instance, Figure 5.4 indicates a gain of "more than 2 order of magnitude in speed up as the dimension increases."
  • High Accuracy Maintained: The relative errors presented in the figures (e.g., Figure 5.3 right panel, Figure 5.7 right panel) show that the compressed methods achieve accuracy comparable to the standard methods, with POD and cPOD (and their DEIM variants) performing very similarly.
  • rSVD Effectiveness: Figure 3.1 illustrates how randomized SVD can approximate the singular value decay of a matrix with different levels of sampling, showing that increasing sampling leads to more accurate approximations.
  • cDMD is Fastest: The results suggest that compressed DMD (cDMD) can be the fastest method as it "does not require the computation of the randomized SVD."

Limitations and Future Work

  • Oversampling Parameter: The paper mentions that the oversampling parameter ($p$) in rSVD allows for controlling the approximation error. While small values are suggested, the optimal choice of $p$ for different problems might require further investigation.
  • Online Stage Not Optimized: The authors explicitly state that their focus is on accelerating the offline stage, and they do not aim to improve the online stage's performance. Future work could explore optimizations for the online evaluation of these reduced models.
  • Error Analysis for Randomized SVD: While the paper references existing work on error bounds for randomized SVD, a deeper dive into how these error bounds specifically impact the MOR context could be beneficial.
  • General Applicability: While the paper demonstrates success on two specific examples, further validation across a broader range of complex dynamical systems and PDEs would strengthen the claims of general applicability.
  • Heuristic Choice of Rank ($l$): The paper acknowledges that there are no a-priori estimates for choosing the truncation parameter $l$ (the rank of the basis functions) that guarantee optimal reduced models. While heuristic considerations exist, more principled methods for rank selection in the context of randomized MOR could be explored.

Summary updated

BibTeX
@inproceedings{alla2019randomized,
  author = {Alessandro Alla and J. Nathan Kutz},
  title = {{Randomized model order reduction}},
  booktitle = {Advances},
  year = {2019},
  doi = {10.1007/s10444-018-09655-9},
}
Figure