rom.deim.deim

Purpose: Implements the Discrete Empirical Interpolation Method (DEIM) for accelerating nonlinear term evaluation in reduced-order models within finite element frameworks. By restricting nonlinear force evaluations to a small set of strategically selected degrees of freedom and reconstructing the full term via interpolation, DEIM reduces the computational cost of nonlinear ROM evaluation by orders of magnitude while preserving accuracy.

Summary: Provides the deim class, which constructs an efficient approximation of nonlinear force terms by computing empirical modes from snapshot data, selecting optimal interpolation points via a greedy algorithm, and building the DEIM projection matrix for fast online reconstruction. Selected DOFs are mapped to finite element indicators to enable sparse assembly during online evaluation. The method transforms nonlinear term evaluation from ((n)) to ((m)) where (m n), making real-time and large-scale nonlinear ROM simulation tractable.

Author: Suparno Bhattacharyya

Classes

Name	Description
deim	Discrete Empirical Interpolation Method for nonlinear ROM acceleration.

deim

rom.deim.deim.deim(mesh, F_nl, V_sel, tol_f=0.01, extra_modes=0)

Summary: Addresses the computational bottleneck in nonlinear reduced-order models where nonlinear terms must otherwise be evaluated at all degrees of freedom regardless of basis size. The DEIM procedure proceeds through four stages:

Empirical Mode Analysis: Computes dominant modes of the nonlinear force snapshot matrix via SVD to capture the essential nonlinear behavior patterns in a compact basis.
Optimal Point Selection: Applies a greedy algorithm to select interpolation points that maximize information content and minimize approximation error in the empirical subspace.
Projection Matrix Construction: Builds the DEIM projection matrix enabling fast reconstruction of the full nonlinear term from values sampled at the selected points only.
Element Mapping: Maps selected DOFs to finite element indicators for efficient sparse matrix assembly during online ROM evaluation.

This approach is most effective for nonlinear PDEs with smooth or localized nonlinear behavior, real-time control applications, and systems where nonlinear term evaluation dominates the online computational cost.

Parameters

Name	Type	Description	Default
mesh	object	Finite element mesh containing connectivity information and node data.	required
F_nl	ndarray, shape (n_dofs, n_snapshots)	Snapshot matrix of nonlinear force evaluations; each column is the nonlinear force vector for one parameter instance.	required
V_sel	ndarray, 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 the tolerance criterion, useful for capturing marginal nonlinear effects.	`0`

Attributes

Name	Type	Description
U_fs	ndarray	Truncated empirical basis matrix containing the selected nonlinear modes.
deim_mat	ndarray	DEIM projection matrix enabling fast nonlinear term reconstruction: ( {} = V^U{fs} D _{} ), where (D) is `deim_mat`.
xi	ndarray of int	Binary element indicator vector marking which elements contain at least one selected DOF.
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 online ROM evaluation
Problems where nonlinear term evaluation dominates computational cost
Systems with smooth nonlinear behavior amenable to low-rank approximation

The method assumes nonlinear terms can be well-approximated by a low-rank representation, which holds for a broad class of physical systems.

References

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_sampled

Methods

Name	Description
deim_red	Execute the greedy DEIM algorithm for optimal interpolation point selection.
select_elems	Select interpolation points and construct the DEIM projection matrix.
sopt_red	S-OPT sampling: select rows maximizing the S-optimality measure.

deim_red

rom.deim.deim.deim.deim_red(f_basis, num_f_basis_vectors_used)

Summary: Implements the core greedy DEIM algorithm that iteratively selects interpolation points to minimize approximation error in the empirical subspace. The procedure operates as follows:

Initial Selection: Chooses the DOF with the largest absolute value in the first empirical mode as the starting interpolation point.
Iterative Refinement: For each subsequent mode, solves for optimal interpolation coefficients using the previously selected points, then selects the DOF with the maximum residual as the next point.
Residual Minimization: Each new point is chosen to minimize the reconstruction error for the current empirical mode given all previously selected points.

This greedy strategy ensures that selected points capture maximum information content while maintaining numerical stability through well-conditioned interpolation matrices. The computational complexity is ((m^3)) where (m) is the number of modes, making it efficient even for moderately large empirical subspaces.

Parameters

Name	Type	Description	Default
f_basis	ndarray, 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, shape (num_modes, num_modes)	Square matrix containing the rows of the empirical basis corresponding to selected interpolation points; used to construct the DEIM projection matrix.
sampled_rows	list of int	Ordered list of DOF indices selected as interpolation points; the ordering reflects the greedy selection sequence.

Notes

The interpolation matrix f_basis_sampled remains well-conditioned by construction, as each successive point is chosen to maximize the residual norm. For problems with strongly localized nonlinear effects, DEIM typically selects points near regions of highest nonlinear activity, producing physically intuitive sampling patterns.

Examples

>>> 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.deim.select_elems(sopt=False)

Summary: Performs the complete DEIM setup pipeline, from snapshot decomposition through to projection matrix construction. Executes the following steps in sequence:

SVD Analysis: Decomposes the nonlinear snapshot matrix to identify the dominant empirical modes capturing essential nonlinear behavior.
Mode Selection: Applies tolerance-based truncation, with optional additional modes (extra_modes) to balance accuracy against computational efficiency.
Point Selection: Invokes the greedy DEIM algorithm (or S-OPT if sopt=True) to select interpolation points that minimize approximation error in the empirical subspace.
Element Mapping: Maps selected DOFs to finite element indicators (self.xi) to enable efficient sparse assembly during online evaluation.
Projection Construction: Builds the DEIM projection matrix using the Moore-Penrose pseudoinverse for numerical stability:

[ {} U{fs} (U_{fs}[, :])^{+} _{} ]

Returns

Name	Type	Description
deim_mat	ndarray, shape (n_modes, n_selected_points)	DEIM projection matrix for reconstructing full nonlinear terms from sampled values; used as ( {} = V^U{fs} D _{} ).
sampled_rows	list of int	DOF indices selected as DEIM interpolation points; these are the only locations where nonlinear terms require evaluation during online ROM solves.

Notes

The pseudoinverse-based construction ensures numerical stability even when the empirical basis is not perfectly conditioned. The element mapping (self.xi) restricts assembly to only the finite elements containing selected DOFs, enabling sparse matrix operations throughout the online phase.

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.deim.sopt_red(f_basis, num_f_basis_vectors_used)

Summary: Implements S-OPT sampling as an alternative to the greedy DEIM algorithm. Rather than minimizing pointwise residuals, S-OPT selects rows of the empirical basis by maximizing the S-optimality measure ( S(Z^Q) ), which jointly maximizes column orthogonality and the determinant of the information matrix ( (Z^Q)^(Z^Q) ). This produces sampling sets with better volumetric coverage of the empirical subspace compared to purely greedy selection.

Efficient Sherman–Morrison rank-1 updates are used to avoid recomputing determinants at every candidate evaluation, keeping the procedure tractable for large subspaces. The algorithm operates in two phases:

Phase 1 (( j < n_f )): Row and column expansion following the Slide 12/14 formula.
Phase 2 (( j n_f )): Row-only append for oversampling, following the Slide 13/15 formula.

Parameters

Name	Type	Description	Default
f_basis	ndarray, shape (N, n_modes_total)	Full empirical basis matrix from SVD of nonlinear snapshots.	required
num_f_basis_vectors_used	int	Number of empirical basis vectors (modes) to use for point selection.	required

Returns

Name	Type	Description
f_sampled_row	ndarray	Rows of `f_basis` at the S-OPT selected indices.
Z_indices	list of int	Selected row indices.
Z_boolean	ndarray of bool	Boolean mask of selected rows, usable for direct array indexing.

References

Shin, Y. and Xiu, D., 2016. On a near optimal sampling strategy for least squares polynomial regression. SIAM Journal on Scientific Computing, 38(3), pp. A385–A411.

Lauzon, J. et al., 2024. S-OPT: A points selection strategy for hyper-reduction in reduced order models. SIAM Journal on Scientific Computing, 46. arXiv:2203.16494.