## 2 Model Problem of the Allen-Cahn Equation and Finite Difference Approximation
### Pod-Deim Reduced System  
Since the nonlinear term of the POD reduced system in (9) may still have a _large_ computational cost due to the dependence on \(n\), we will use DEIM to approximate this nonlinear term. DEIM approximation consists of two main steps. The first step is to project the nonlinear term on a basis set of dimension \(m\), which is generally much less than \(n\). This basis is obtained from POD basis of the nonlinear snapshot matrix \(\mathbf{F}=\{F(\mathbf{u}(t_{1})),...,F(\mathbf{u}(t_{n}))\}\) by using Algorithm 1. Suppose the resulting POD basis matrix of the nonlinear snapshots is denoted by \(\mathbf{Z}=[\mathbf{z}_{1},\ldots,\mathbf{z}_{m}]\in\mathbb{R}^{n\times m}\). The second step of DEIM is to perform interpolation of the projected nonlinear term on its certain components, which are chosen by a greedy selection procedure as shown in Algorithm 2. This procedure is called DEIM algorithm in this work. ```
\(\bullet\) INPUT : \(\{\mathbf{z}_{i}\}_{i=1}^{m}\subset\mathbb{R}^{n}\) linearly independent \(\bullet\) OUTPUT : \(\vec{\varrho}=[\varrho_{1},...,\varrho_{m}]\in\mathbb{R}^{m}\) \(1\). \(\varrho_{1}=\)argmax\({}_{j=1,...,n}\{|z_{j_{1}}|\}\) \(\mathbf{Z}=|\mathbf{z}_{1}|,\mathbf{P}=[\varrho_{1}]\), \(\vec{\varrho}=[\varrho_{1}]\) \(3\). for \(i=2\) to \(m\) do \(4\). Solve \((\mathbf{P}^{T}\mathbf{Z})\mathbf{c}=\mathbf{P}^{T}\mathbf{z}_{i}\) for \(\mathbf{c}\) \(\mathbf{r}=\mathbf{z}_{i}-\mathbf{Z}\mathbf{c}\) \(\varrho_{i}=\)argmax\({}_{j=1,...,n}\{|r_{j_{i}}|\}\) \(\mathbf{Z}\leftarrow\left[\mathbf{Z}\quad\mathbf{z}_{i}\right],\mathbf{P} \leftarrow\left[\mathbf{P}\quad\mathbf{e}_{\varrho_{i}}\right],\vec{\varrho} \leftarrow\left[\vec{\varrho}\right]\) \(8\). end for
```  
**Algorithm 2**Discrete Empirical Interpolation Method (DEIM)  
Note that the input to Algorithm 2 can be any set of linearly independent vectors \(\{\mathbf{z}_{i}\}_{i=1}^{m}\). In the standard POD-DEIM approach, this set of input vectors is obtained from POD basis of nonlinear snapshots. The output is the vector \(\vec{\varrho}\) that contains the indices for unity components in matrix \(\mathbf{P}\) with \(\mathbf{P}=[\mathbf{e}_{\varrho_{1}},...,\mathbf{e}_{\varrho_{m}}]\in\mathbb{R }^{n\times m}\), where \(e_{\varrho_{i}}=[0\;...\;0\;1\;0\;...\;0]^{T}\in\mathbb{R}^{n}\) is the \(\varrho_{i}\)th column of the identity matrix\(\mathbf{I}\in\mathbb{R}^{n\times n}\) for \(i=1,...,m\). From Algorithm 2, in line 1, the index \(\varrho_{1}\) is determined by the largest absolute value of elements in \(\mathbf{z}_{1}\). In line 2, we define \(\mathbf{Z}=\mathbf{z}_{1}\in\mathbb{R}^{n\times 1}\) and \(\mathbf{P}=\mathbf{e}_{\varrho_{1}}\in\mathbb{R}^{n\times 1}\). The selected index is stored in \(\varrho_{1}\in\mathbb{R}\). In line 3, we start the iterative process for \(i=2,...,m\) and solve \(\left(\mathbf{P}^{T}\mathbf{Z}\right)\mathbf{c}=\mathbf{P}^{T}\mathbf{z}_{i}\) to find the constant \(\mathbf{c}\) in line 4. In line 5, we consider the residual \(\mathbf{r}=\mathbf{z}_{i}-\mathbf{Z}\mathbf{c}\) and determine the next index by finding the largest component in \(|\mathbf{r}|\). In line 6, the index \(\varrho_{i}\) is determined by the largest absolute value of element in \(\mathbf{r}\). In line 7, this index is used to update the matrix \(\mathbf{P}\) by appending a new vector \(\mathbf{e}_{\varrho_{i}}\) to the existing one. From the iterative process, we obtain \(\mathbf{Z}\), \(\mathbf{P}\) and \(\vec{\varrho}\). Note that the matrix \(\mathbf{P}^{T}\mathbf{Z}\) in each iteration of Algorithm 2 is a nonsingular matrix as proved in [51].