When is hyper-reduction needed in reduced order models?

Question

Consider a high-dimensional ODE, which comes from semi-discretization

$$ \frac{d\mathbf{u}}{dt} = f(\mathbf{u}), \qquad \mathbf{u}\in\mathbb{R}^N \tag{1} $$

If we want to build Reduced Order Models (ROM), we typically say

$$ \mathbf{u} = \mathbf{u}_{ref}(\mathbf{x}) + \mathbf{\Phi}{\mathbf{\hat{u}}}, \qquad {\mathbf{\hat{u}}}\in\mathbb{R}^n, \mathbf{u}_{ref}\in\mathbb{R}^N,\mathbf{\Phi} \in \mathbb{R}^{N \times n}, n \ll N \tag{2} $$

Using (2) in (1) we get

$$ \mathbf{\Phi}\frac{d\mathbf{\hat u}}{dt} = f( \mathbf{u}_{ref}+\mathbf{\Phi}\mathbf{\hat u}) \tag{3} $$

Premultiplying by $\mathbf{\Phi}^T$ (Galerkin projection) and using $\mathbf{\Phi}^T\mathbf{\Phi}=1$ we get,

$$ \frac{d\mathbf{\hat u}}{dt} = \mathbf{\Phi}^Tf( \mathbf{u}_{ref}+\mathbf{\Phi}\mathbf{\hat u}) \tag{4} $$

Since the RHS contains $\mathbf{\Phi}\mathbf{\hat u}$ and $\mathbf{\Phi}^T f$ the computation scales with $N$ and so is undesirable in a ROM (we want computations to scale with $n$). To reduce this cost, by making an approximate computation of the RHS which scales with $n$ instead of $N$, algorithms such as DEIM have been developed.

I understand the development so far.

However, consider the following concrete example, from Brunton and Kutz (Data-Driven Science and Engineering: Machine Learning, Dynamical Systems and Control) pg 425 , where $u=u(x,t)$ is a scalar variable

$$ \frac{du}{dt} = u^3 \tag{5} $$

If we expand $u$ in terms of, say, two orthogonal POD modes, we get

$$ u(x,t)=a_1(t)\psi_1(x) + a_2(t)\psi_2(x) \tag{6} $$

If we use (6) in (5) we get

$$ \psi_1\frac{da_1}{dt} + \psi_2\frac{da_2}{dt} = a_1\psi_1^3 + 3a_1^2a_2\psi_1^2\psi_2 + 3a_1a_2^2\psi_1\psi_2^2 + a_2^3\psi_2^3 $$

Multiplying by $\psi_1$ and integrating in space, and using orthogonality of $\psi_1$ and $\psi_2$ we get

$$ \frac{da_1}{dt} = a_1^3(\psi_1,\psi_1^3) + 3a_1^2a_2(\psi_1,\psi_1^2\psi_2) + 3a_1a_2^2(\psi_1,\psi_1\psi_2^2) + a_2^3(\psi_1,\psi_2^3) \tag{7} $$

where the bracket $(\cdot,\cdot)$ denotes an inner-product in space. In the equation above, all the inner-products on the RHS can be pre-computed in the offline phase. Hence the cost of running the ROM (online phase) will not scale with $N$.

So, my question is why is hyper-reduction needed? Is it meant for non-linearities which cannot be explicitly written in polynomial form as above? Or is it simply meant to leverage the fact that we have a FOM (full order model) code which is capable of computing the RHS $f$ ? Is it because that the number of terms increases quickly in the RHS (multinomial expansion), rendering it impossible to compute even in the offline phase?

Answer 1

Yes, you are correct. In the example from above you don't strictly need hyperreduction, especially since you only have two POD modes.

From an implememtational point of view, I would always first implement the (inefficient) naive POD reduction and then decide whether hyperreduction is needed to further speed up the reduced order model, since the naive POD reduction can be already sufficient for mild nonlinearities, like the quadratic nonlinearity in the Navier-Stokes equations.

However, in the original DEIM paper hyperreduction methods have been motivated as follows:

When a general nonlinearity is present, the cost to evaluate the projected nonlinear function still depends on the dimension of the original system, resulting in simulation times that hardly improve over the original system.

This is then what you also observed that for the simple ODE $$ \frac{du}{dt} = u^n $$ when the polynomial degree $n$ gets larger, e.g. $n \geq 3$, you have to precompute a lot if terms. The offline phase then becomes more expensive, but more importantly the online phase becomes more computationally expensive since there are a lot of terms in the reduced order model. In the worst case the online cost of the reduced order model could be higher than the cost of the full order model, thus making the reduced order model useless.

Finally, there are non-polynomial nonlinearities like $$ \frac{du}{dt} = \exp(u) $$ where you would need to evaluate the nonlinearity with the full order model in the online phase. For this case it is absolutely crucial to use hyperreduction methods, since in reduced order modeling we want to avoid the usage of the full order model in the online phase as much as possible.