🔢 mathematics

Tensor-based empirical interpolation method and its application in model reduction

This paper proposes a tensor-based empirical interpolation method that approximates matrix-valued functions directly without vectorization, offering reduced computational costs compared to traditional DEIM approaches while maintaining comparable accuracy, albeit with a theoretical limitation of generating rectangular grid interpolation points.

Original authors: Brij Nandan Tripathi, Hanumant Singh Shekhawat, Seip Weiland

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Brij Nandan Tripathi, Hanumant Singh Shekhawat, Seip Weiland

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Compressing a Giant Spreadsheet

Imagine you are trying to simulate a complex physical system, like weather patterns or fluid flow. In a computer, this system is often represented as a massive spreadsheet (a matrix) that changes over time. To run a simulation, the computer has to crunch numbers for every single cell in that spreadsheet. If the spreadsheet is huge (say, 1,000 by 1,000), this takes an enormous amount of time and power.

Model Order Reduction (MOR) is like trying to shrink that giant spreadsheet down to a tiny, manageable size without losing the important story it tells. The goal is to keep the "essence" of the data while throwing away the redundant details.

The Problem: The "Flattening" Trap

Usually, when computers try to shrink these giant spreadsheets, they use a method called DEIM (Discrete Empirical Interpolation Method). However, DEIM was originally designed for lists (vectors), not spreadsheets (matrices).

To use DEIM on a spreadsheet, traditional methods force the computer to flatten the 2D grid into a long, 1D list.

The Analogy: Imagine you have a photo of a city. To analyze it with a tool that only understands lists, you have to cut the photo into tiny strips and tape them end-to-end into a single, miles-long ribbon.
The Downside: This "ribbon" is messy. It breaks the natural structure of the photo (the grid), and the computer has to do a lot of extra work to handle this long ribbon, making the process slow and inefficient.

The Solution: TEIM (The "Grid-Smart" Method)

The authors of this paper propose a new method called TEIM (Tensor-based Empirical Interpolation Method). Instead of cutting the photo into a ribbon, TEIM looks at the spreadsheet as it naturally is: a grid with rows and columns.

How it works:

The "Sampling" Strategy: To understand the whole spreadsheet, you don't need to look at every cell. You just need to look at a few key spots.
The Discovery: The authors mathematically proved that their method doesn't pick random spots. Instead, it always picks a rectangular grid of points.
- The Metaphor: Imagine you are trying to guess the contents of a giant chessboard. Instead of picking random squares, TEIM says, "Let's look at 4 specific rows, and within those rows, let's look at 6 specific columns." The result is a neat, rectangular block of selected squares.
The Benefit: Because the selected points form a perfect rectangle, the math becomes much simpler and faster. The computer doesn't have to untangle a messy ribbon; it can process the grid directly.

The Trade-off: Speed vs. Perfection

The paper compares their new "Grid-Smart" method (TEIM) against the old "Ribbon" method (DEIM).

Speed: TEIM is faster. It requires less computing power (both when setting up the model and when running it). It's like taking a shortcut through a park instead of walking around the block.
Accuracy: The results show that TEIM is slightly less accurate than DEIM in the specific examples tested.
- Why? The paper explains that the "Ribbon" method (DEIM) sometimes finds a better "subspace" (a better way to compress the data) for certain types of problems.
- However, the authors note that if the data naturally fits a "tensor" structure (like 3D video or multi-dimensional grids), TEIM might actually be more accurate because it respects the natural shape of the data.

The "Aha!" Moment: It's Two DEIMs in One

One of the paper's most important theoretical findings is a realization about the shape of the selected points.

The authors proved that because TEIM always selects points in a rectangular grid, it is mathematically equivalent to running the DEIM algorithm twice: once for the rows and once for the columns.
This means you don't need a complex new algorithm; you can just run the standard DEIM tool on the rows, then run it again on the columns, and you get the same result as their fancy new method.

Real-World Test: The "Allen-Cahn" Equation

To prove their method works, the authors tested it on a specific mathematical model called the Allen-Cahn equation (used to model things like phase separation in materials).

They took a complex, non-linear equation that usually requires massive computing power.
They used TEIM to shrink the problem.
The Result: The new method solved the problem significantly faster than the traditional method. While the traditional method was slightly more precise, the new method was "good enough" and much more efficient.

Summary

The Problem: Existing tools force 2D data (grids) into 1D lists, which is slow and clumsy.
The Fix: A new method (TEIM) that keeps the data in its 2D grid shape.
The Magic: It automatically selects a neat, rectangular block of data points to represent the whole grid.
The Result: It is much faster and computationally cheaper. It is slightly less accurate in some cases, but the authors argue that for data with complex, multi-dimensional structures, this speed gain is worth the tiny loss in precision.

In short, the paper teaches us that sometimes, keeping data in its natural "grid" shape is smarter than flattening it out, and doing so can save a massive amount of computer time.

Technical Summary: Tensor-Based Empirical Interpolation Method and Its Application in Model Reduction

Problem Statement
Model Order Reduction (MOR) is essential for simulating large-scale dynamical systems, particularly those governed by non-linear partial differential equations (PDEs). While techniques like Proper Orthogonal Decomposition (POD) combined with Galerkin projection effectively reduce linear and bilinear systems, non-linear terms often retain a dependency on the full-order model (FOM) dimension. To address this, the Discrete Empirical Interpolation Method (DEIM) and its predecessor, the Empirical Interpolation Method (EIM), were developed to approximate non-linear terms using a small set of interpolation points.

However, a significant limitation exists when the non-linearity is a matrix-valued function (e.g., arising from discretized 3D PDEs). Conventional approaches require vectorizing the matrix into a high-dimensional vector before applying DEIM. This vectorization is computationally inefficient for large matrices, increasing both offline and online computational costs. While some researchers have attempted matrix-based extensions, a rigorous theoretical framework explaining the functioning, limitations, and optimal structure of such methods has been lacking.

Methodology
The authors propose the Tensor-Based Empirical Interpolation Method (TEIM), an extension of EIM designed specifically to approximate matrix-valued functions without transforming them into vector form. The methodology proceeds through the following steps:

Tensor POD Basis Construction: Instead of standard vector POD, the method employs Higher-Order Singular Value Decomposition (HOSVD) to generate a tensor basis (a set of rank-one matrices $u_i \otimes v_j$ ) that spans the solution space. This avoids the computational overhead of vectorizing large matrices.
Interpolation Point Selection (TEIM Algorithm): The paper introduces a modified algorithm to select interpolation points. Unlike standard DEIM which selects points arbitrarily on a grid, the TEIM algorithm selects indices in a nested, structured manner.
Rectangular Grid Structure: A critical theoretical finding is that for tensor bases (or rank-one matrix bases), the TEIM algorithm inherently selects interpolation points that form a rectangular grid. Specifically, if $m_1 m_2$ points are required, the algorithm selects $m_1$ rows and $m_2$ columns, selecting all intersections.
Equivalence to 2D-DEIM: The authors mathematically prove that the TEIM method is equivalent to applying the standard DEIM algorithm independently to the row and column basis matrices (a "two-sided" DEIM approach). This allows the masking operator to be decomposed into two smaller operators ( $P_3$ and $P_4$ ) rather than one large operator acting on the vectorized matrix.
Efficient Approximation Formula: The final approximation of the matrix function $\tilde{A}(t)$ is derived in a matrix-product form:
$\tilde{A}(t) = U_1(P_5 U_1)^{-1} (P_5 A(t) P_6^T) (U_2(P_6 U_2)^{-1})^T$
where $P_5$ and $P_6$ are the masking operators derived from the row and column bases, respectively. This formulation avoids vectorization entirely during the online stage.

Key Contributions

Theoretical Framework: The paper establishes a necessary theoretical foundation for tensor-based interpolation, proving the equivalence between the proposed TEIM and the application of DEIM in each direction.
Rectangular Grid Characterization: The authors demonstrate that tensor-based interpolation methods relying on rank-one bases inevitably select interpolation points on a rectangular grid. This identifies a fundamental structural limitation of such approaches.
Computational Efficiency: By exploiting the rectangular grid structure, the method reduces the online computational complexity. For a matrix of size $n_1 \times n_2$ with $m_1$ rows and $m_2$ columns selected, the complexity is $O(n_1 n_2 m_2 + n_1 m_1 m_2)$ (or similar depending on evaluation order), which is significantly lower than the $O(n_1 n_2 m_1 m_2)$ complexity of vectorized DEIM approaches.
Algorithmic Implementation: The paper provides a specific algorithm (Algorithm 1) for selecting the nested set of interpolation points that ensures the invertibility of the masking operator.

Results and Numerical Experiments
The authors validate the method through two primary applications:

Matrix-Valued Function Approximation:
- Example 1: A non-linear parameterized 2D function. Results show that when the tensor POD basis provides a better approximation subspace than the standard vector POD basis, TEIM achieves lower approximation errors than DEIM.
- Example 2: A time-dependent function where the standard POD basis outperforms the tensor basis. In this case, DEIM yields better accuracy. This highlights that the choice between TEIM and DEIM depends on which basis (tensor vs. vector) better captures the system's dynamics.
- Timing: TEIM consistently demonstrates lower average CPU time compared to DEIM, even when accuracy is comparable.
Model Reduction of Semi-Linear Matrix Differential Equations:
- The method was applied to the 2D Allen-Cahn equation. The reduced-order model (ROM) was constructed using tensor POD for the state and TEIM for the non-linear term.
- Accuracy vs. Efficiency: In the specific case of the Allen-Cahn equation tested, the standard POD-DEIM approach (vector-based) provided slightly higher accuracy than the TEIM approach. However, the TEIM approach required fewer computational resources.
- Vector Differential Equations: When the matrix equation was converted to a vector form and reduced using TEIM for the non-linearity, the results were comparable to POD-DEIM, with the choice of method again depending on which basis offered a superior approximation subspace.

Significance and Claims
The paper claims that the TEIM method offers a computationally efficient alternative to vectorizing matrix-valued functions for model reduction. Its primary significance lies in:

Reducing Computational Burden: It significantly lowers both offline and online computation times by avoiding the vectorization of large matrices.
Structural Insight: It clarifies that tensor-based interpolation is structurally constrained to rectangular grids, which simplifies the implementation to a two-sided DEIM approach.
Contextual Applicability: The authors modestly note that while TEIM is more efficient, its accuracy relative to DEIM is contingent on the problem. If the system's dynamics are better captured by a tensor basis (as in Example 1), TEIM is superior in both accuracy and speed. If the system is better captured by a standard vector basis (as in the Allen-Cahn example), DEIM may yield higher accuracy, though TEIM remains a viable, faster alternative with a minor compromise in precision.

The work concludes that while the study focuses on matrix-valued functions, the theoretical framework is extensible to higher-order tensor-valued functions.