66
Algorithm 2 : DEIM (Discrete Empirical Interpolation Method)
Input: {Wi}*Zι ɑ rjv linearly independent
Output: z = [z1,..., zkf]τ ∈ Rfcy
1: Define zɪ = argmax∣Wι(j)∣
J
2: W = [W1], P = [ezι], z = [z1]
3: for i = 2 to kf do
4: Solve (PτW)s = PτWi for s
5: r ≡ Wj — Ws
6: Define zi = argmax∣r(j)∣
j
7: W ÷- [W W1], P <— [P ezJ, z ÷-
8: end for
term can be approximated, thus reducing the complexity of N to kf ≪ N (Barrault
et al., 2004). This method, originally described for use with finite elements, has
been extended to our case of finite differences via the discrete empirical interpolation
method (DEIM) as given by (Chaturantabut and Sorensen, 2009).
We begin with the basis W for the snapshot set F of nonlinear terms and seek a
“maximally independent basis set” for W (Nguyen et al., 2008). The first interpolation
point Zi is the index of the entry of Wi with the largest magnitude, where wɪ is the
first column of W. For i = 2,..., kf each point zi is chosen as the index of the entry
of the largest magnitude of the residual vector r ≡ Wi — Ws, where P is the matrix of
the г-l coordinate vectors corresponding to the previous interpolation points, W is
the matrix of the previous i — 1 DEIM basis vectors for N (that is, W = W(:, 1 : i — 1)),
and s is the coefficient vector of components of W in Wi relative to the previous i — 1