Discrete Empirical Interpolation for Nonlinear Model Reduction

A dimension reduction method called Discrete Empirical Interpolation is proposed and shown to dramatically reduce the computational complexity of the popular Proper Orthogonal Decomposition (POD) method for constructing reduced-order models for unsteady and/or parametrized nonlinear partial differential equations (PDEs). In the presence of a general nonlinearity, the standard POD-Galerkin technique reduces dimension in the sense that far fewer variables are present, but the complexity of evaluating the nonlinear term remains that of the original problem. Empirical Interpolation posed in finite dimensional function space is a modification of POD that reduces complexity of the nonlinear term of the reduced model to a cost proportional to the number of reduced variables obtained by POD. We propose a Discrete Empirical Interpolation Method (DEIM), a variant that is suitable for reducing the dimension of systems of ordinary differential equations (ODEs) of a certain type. As presented here, it is applicable to ODEs arising from finite difference discretization of unsteady time dependent PDE and/or parametrically dependent steady state problems. However, the approach extends to arbitrary systems of nonlinear ODEs with minor modification. Our contribution is a greatly simplified description of EIM in a finite dimensional setting that possesses an error bound on the quality of approximation. An application of DEIM to a finite difference discretization of the 1-D FitzHugh-Nagumo equations is shown to reduce the dimension from 1024 to order 5 variables with negligible error over a long-time integration that fully captured non-linear limit cycle behavior. We also demonstrate applicability in higher spatial dimensions with similar state space dimension reduction and accuracy results.