rom.deim.deim_o
rom.deim.deim_o
Discrete Empirical Interpolation Method (DEIM) for nonlinear ROM acceleration.
This module implements DEIM for reducing the dimension of nonlinear force terms in reduced-order models within finite element frameworks. DEIM enables efficient evaluation of nonlinear terms by:
- Computing empirical modes from nonlinear force snapshots via SVD
- Selecting optimal interpolation points using greedy algorithms
- Constructing projection matrices for fast nonlinear term approximation
- Mapping selected DOFs to element indicators for efficient assembly
TL;DR: Dramatically reduces computational cost of nonlinear ROM evaluation by approximating nonlinear terms using interpolation at carefully selected points, achieving significant speedups while maintaining accuracy.
Author: Suparno Bhattacharyya
Classes
| Name | Description |
|---|---|
| deim | Discrete Empirical Interpolation Method for nonlinear ROM acceleration. |
deim
rom.deim.deim_o.deim(mesh, F_nl, V_sel, tol_f=0.01, extra_modes=0)Discrete Empirical Interpolation Method for nonlinear ROM acceleration.
TL;DR: Reduces computational cost of nonlinear terms in ROMs by ~1000x through strategic sampling and interpolation, enabling real-time nonlinear PDE solutions.
The Discrete Empirical Interpolation Method (DEIM) addresses the computational bottleneck in nonlinear reduced-order models where nonlinear terms must still be evaluated at all degrees of freedom. DEIM constructs an efficient approximation by:
Empirical Mode Analysis: Computes dominant modes of nonlinear force snapshots using SVD to capture the essential nonlinear behavior patterns.
Optimal Point Selection: Uses a greedy algorithm to select interpolation points that maximize information content while minimizing approximation error.
Projection Matrix Construction: Builds a projection matrix that enables fast reconstruction of full nonlinear terms from interpolated values.
Element Mapping: Maps selected degrees of freedom to finite element indicators for efficient sparse assembly operations.
The method transforms the nonlinear term evaluation from O(n) to O(m) where m << n, achieving dramatic computational savings essential for real-time applications.
Parameters
| Name | Type | Description | Default |
|---|---|---|---|
| mesh | object | Finite element mesh containing connectivity information and node data. | required |
| F_nl | ndarray of shape (n_dofs, n_snapshots) | Snapshot matrix of nonlinear force evaluations at various parameter values. Each column represents the nonlinear force vector for one parameter instance. | required |
| V_sel | ndarray of shape (n_dofs, n_modes) | Reduced basis matrix from POD, used for solution space projection. | required |
| tol_f | float | Tolerance for SVD mode selection based on singular value decay. Smaller values retain more modes for higher accuracy. | 1e-2 |
| extra_modes | int | Additional empirical modes to retain beyond those selected by tolerance criterion, useful for capturing marginal nonlinear effects. | 0 |
Attributes
| Name | Type | Description |
|---|---|---|
| U_fs | ndarray | Truncated empirical basis matrix containing selected nonlinear modes. |
| deim_mat | ndarray | DEIM projection matrix enabling fast nonlinear term reconstruction: F_nl_approx = V.T @ U_fs @ deim_mat @ F_nl_sampled |
| xi | ndarray of int | Binary element indicator vector marking which elements contain selected DOFs. |
| n_f_sel | int | Number of empirical modes selected for DEIM approximation. |
Notes
DEIM is particularly effective for:
- Nonlinear PDEs with localized nonlinear effects
- Real-time control applications requiring fast ROM evaluation
- Problems where nonlinear term evaluation dominates computational cost
- Systems with smooth nonlinear behavior amenable to low-rank approximation
The method assumes the nonlinear terms can be well-approximated by a low-rank representation, which is typically valid for many physical systems.
References
.. [1] Chaturantabut, S. and Sorensen, D.C., 2010. Nonlinear model reduction via discrete empirical interpolation method. SIAM journal on scientific computing, 32(5), pp.2737-2764.
Examples
>>> # Generate nonlinear force snapshots
>>> F_snapshots = compute_nonlinear_snapshots(problem, param_list)
>>> # Create DEIM approximation
>>> deim_obj = deim(mesh, F_snapshots, reduced_basis, tol_f=1e-3)
>>> deim_matrix, sample_points = deim_obj.select_elems()
>>> # Use in ROM: F_approx = V.T @ U @ deim_matrix @ F_sampledMethods
| Name | Description |
|---|---|
| deim_red | Execute greedy DEIM algorithm for optimal interpolation point selection. |
| select_elems | Select interpolation points and construct DEIM projection matrix. |
| sopt_red | Perform an S-optimal sampling reduction on the given basis. This method uses a QR |
deim_red
rom.deim.deim_o.deim.deim_red(f_basis, num_f_basis_vectors_used)Execute greedy DEIM algorithm for optimal interpolation point selection.
TL;DR: Implements the core greedy algorithm that iteratively selects interpolation points to minimize approximation error in the empirical subspace.
The DEIM greedy algorithm works by:
Initial Selection: Chooses the DOF with maximum absolute value in the first empirical mode as the starting interpolation point.
Iterative Refinement: For each subsequent mode, solves for optimal interpolation coefficients using previously selected points, then selects the DOF with maximum residual as the next point.
Residual Minimization: Each new point is chosen to minimize the approximation error when reconstructing the current empirical mode from previously selected points.
This greedy strategy ensures that interpolation points capture maximum information content while maintaining numerical stability through well-conditioned interpolation matrices.
Parameters
| Name | Type | Description | Default |
|---|---|---|---|
| f_basis | ndarray of shape (n_dofs, n_modes) | Empirical basis matrix from SVD of nonlinear force snapshots. Each column represents one empirical mode. | required |
| num_f_basis_vectors_used | int | Number of empirical modes to use for interpolation point selection. Cannot exceed the total number of available modes. | required |
Returns
| Name | Type | Description |
|---|---|---|
| f_basis_sampled | ndarray of shape (num_modes, num_modes) | Square matrix containing rows of the empirical basis corresponding to selected interpolation points. Used to construct the projection matrix. |
| sampled_rows | list of int | Ordered list of DOF indices selected as interpolation points. The order reflects the greedy selection sequence. |
Notes
The algorithm ensures that the interpolation matrix f_basis_sampled remains well-conditioned by construction, as each new point is chosen to maximize the residual norm.
For problems with strong locality in nonlinear effects, DEIM typically selects points near regions of highest nonlinear activity, leading to physically intuitive sampling patterns.
The computational complexity is O(m³) where m is the number of modes, making it efficient even for moderately large empirical subspaces.
Examples
>>> # Empirical basis from SVD
>>> U, s, Vt = np.linalg.svd(F_snapshots, full_matrices=False)
>>> sampled_basis, indices = deim_obj.deim_red(U, n_modes=10)
>>> print(f"Condition number: {np.linalg.cond(sampled_basis):.2e}")select_elems
rom.deim.deim_o.deim.select_elems(sopt=False)Select interpolation points and construct DEIM projection matrix.
TL;DR: Core DEIM algorithm that identifies optimal sampling points and builds the projection matrix for fast nonlinear term approximation.
This method performs the complete DEIM setup:
SVD Analysis: Decomposes nonlinear snapshots to identify dominant empirical modes that capture essential nonlinear behavior patterns.
Mode Selection: Applies tolerance-based truncation with optional extra modes to balance accuracy and computational efficiency.
Point Selection: Uses greedy DEIM algorithm to select interpolation points that minimize approximation error in the empirical subspace.
Element Mapping: Maps selected DOFs to finite element indicators for efficient sparse matrix assembly during online evaluation.
Projection Construction: Builds the DEIM projection matrix that enables reconstruction: F_full ≈ U_fs @ pinv(U_fs[selected_rows, :]) @ F_sampled
Returns
| Name | Type | Description |
|---|---|---|
| deim_mat | ndarray of shape (n_modes, n_selected_points) | DEIM projection matrix for reconstructing full nonlinear terms from sampled values. Used as: F_approx = V.T @ U_fs @ deim_mat @ F_sampled |
| sampled_rows | list of int | Indices of degrees of freedom selected as DEIM interpolation points. These are the only DOFs where nonlinear terms need evaluation. |
Notes
The projection matrix construction uses the Moore-Penrose pseudoinverse to ensure numerical stability even when the empirical basis is not perfectly conditioned.
The element mapping (self.xi) enables efficient assembly by identifying which finite elements contribute to the selected DOFs, allowing sparse matrix operations during online evaluation.
Examples
>>> deim_obj = deim(mesh, F_snapshots, basis_matrix)
>>> proj_matrix, points = deim_obj.select_elems()
>>> print(f"Selected {len(points)} points from {F_snapshots.shape[0]} DOFs")
>>> print(f"Reduction ratio: {F_snapshots.shape[0]/len(points):.1f}x")sopt_red
rom.deim.deim_o.deim.sopt_red(f_basis, num_f_basis_vectors_used)Perform an S-optimal sampling reduction on the given basis. This method uses a QR factorization to extract an orthogonal basis and then iteratively selects the most representative rows (sampling points) based on a defined objective.
Parameters:
f_basis : ndarray The original basis matrix (from the nonlinear force snapshots). num_f_basis_vectors_used : int The number of basis vectors (modes) to consider.
Returns:
f_sampled_row : ndarray The rows of the basis matrix corresponding to the selected sampling points. Z_indices : list List of indices (row numbers) that were selected. Z_boolean : ndarray Boolean vector indicating which rows have been selected.