\documentclass[12pt,ngerman,compress]{beamer}
\usepackage{amsmath,amssymb,amscd,amsthm,latexsym,tabto}
\usepackage{url}
\usepackage[ngerman]{babel}

\usepackage[utf8]{inputenc}

\newcommand{\T}[1]{\mathbf{#1}}
\newcommand{\thetas}{\T{\tilde{\boldsymbol\theta}}}
\newcommand{\thetar}{\thetas}
\newcommand{\tr}{\mathrm{T}}
\newcommand{\ddt}{\frac{\mathrm{d}}{\mathrm{d}t}}
\newcommand{\dtheta}{\mathrm{D}_\theta}
\newcommand{\blambda}{\boldsymbol\lambda}
\newcommand{\ytilde}{\T{\widetilde y}}
\newcommand{\R}{\mathbb{R}}
\usepackage[protrusion=true,expansion=false]{microtype}


\usepackage{pgf,pgffor,pgfplots}
\usepgflibrary{plothandlers}

\usepackage[protrusion=true,expansion=false]{microtype}
\newtheorem*{satz}{Theorem}
\DeclareMathOperator{\Spur}{Spur}
\DeclareMathOperator{\Vecc}{vec}
\DeclareMathOperator{\Orth}{orth}
\DeclareMathOperator*{\argmin}{arg\,min}

\title[POD/DEIM in field-flow fractionation]{\large POD and DEIM in field-flow fractionation}
\author[Carina Willbold]{\small Carina Willbold \\ Universität Augsburg}
\date{Sion\\August 1, 2012}

%\usetheme[secheader]{Madrid}  %Warsaw
\usetheme{Antibes}
%\usecolortheme[RGB={0,101,97}]{structure}
\useoutertheme{split}
\usecolortheme{orchid}
\usefonttheme{serif}
\usepackage{palatino}
\useinnertheme{rectangles}
\setbeamertemplate{frametitle}[default][center]
\linespread{1.1}
%\setbeamercovered{transparent}
%\usepackage{lmodern}
%\usepackage{bookman}

\setbeamertemplate{navigation symbols}{}


\newcommand*\oldmacroB{}%
\let\oldmacroB\insertshorttitle%
\renewcommand*\insertshorttitle{%
        \oldmacroB\hfill%
  \insertframenumber\,/\,\inserttotalframenumber\hfill}

\newcommand{\dashdash}{{\usebeamercolor[fg]{itemize item}--{}}}
\definecolor{darkgreen}{RGB}{0,100,0}
\definecolor{darkred}{RGB}{139,0,0}

\begin{document}

\frame{\titlepage}

\frame[t]{\frametitle{Outline}\tableofcontents}





%\frame[t]{\frametitle{Navier--Stokes equation}
%\begin{picture}(300,0)\linethickness{0.5mm}
%\put(20,-85){\makebox(325,100){\centering\tabular{@{}l@{}}$
%       \rho\frac{\partial\T{v}}{\partial t} - \nu\Delta\T{v} + \rho (\T{v} \cdot \nabla) \T{v} + \nabla p = \T{F} \hspace{5 mm}\quad\text{in}\quad \Omega \times (0,T)$\\
%	  $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{1.9 mm}\nabla\cdot\T{v} = 0 \hspace{5 mm}\quad\text{in}\quad\Omega\times (0,T)$\\
%	  $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{8.4 mm}\T{v} = \T{v}_{\text{in}}\hspace{1.5 mm}\quad \text{on}\quad\color{red}{\Gamma_{\text{in}}\times(0,T),$\\
%	  $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{8.4 mm}\T{v} = 0 \hspace{ 5 mm}\quad\text{on}\quad\Gamma_{\text{lat}}\times(0,T)$\\
%	  $\quad\quad\quad\quad\quad\quad\hspace{7.2 mm}\nu\frac{\partial \T{v}}{\partial \T{n}_\Gamma} - p\T{n}_{\Gamma} = 0\hspace{5 mm}\quad \text{on}\quad\color{blue}{\Gamma_{\text{out}}}\times(0,T)$\\
%	  $\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{4.2 mm}\T{v}(\cdot,0) = \T{v}_{0} \hspace{3 mm}\quad\text{in}\quad\Omega
 %      $\endtabular}}
% \put(30,-180){\color{blue}\line(1,0){240}}\put(30,-180){\line(0,1){80}}\put(270,-180){\line(0,1){80}}\put(30,-150){\color{gray}\line(1,0){240}}
%    \put(45,-100){\color{red}\line(1,0){25}} \put(30,-100){\line(1,0){15}}\put(70,-100){\line(1,0){160}}\put(230,-100){\color{red}\line(1,0){25}}\put(255,-100){\line(1,0){15}}
%    \put(45,-105){\color{red}\line(0,1){10}}\put(70,-105){\color{red}\line(0,1){10}}\put(230,-105){\color{red}\line(0,1){10}}\put(255,-105){\color{red}\line(0,1){10}}\put(140,-176){\makebox(20,20){$\Omega_{2}$}}\put(140,-135){\makebox(20,20){$\Omega_{1}$}}
%\end{picture}
%}





\section[Problem formulation]{Problem formulation}

\subsection{Stokes--Brinkman}
\frame[t]{\frametitle{Stokes--Brinkman equation}
\begin{picture}(300,0)\linethickness{0.5mm}
\put(0,-85){\makebox(325,100){\centering\tabular{@{}l@{}}$
       \rho\frac{\partial\T{v}}{\partial t} - \nu\Delta\T{v} + \nu\chi_{\Omega_{2}} K^{-1}\T{v} + \nabla p = \T{0} \hspace{5 mm}\quad\text{in}\quad \Omega \times (0,T)$\\
	  $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{1.9 mm}\nabla\cdot\T{v} = 0 \hspace{5 mm}\quad\text{in}\quad\Omega\times (0,T)$\\
	  $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{8.4 mm}\T{v} = \T{v}_{\text{in}}^{(i)}\hspace{1.5 mm}\quad \text{on}\quad\color{red}{\Gamma_{\text{in}}^{(i)}}\times(0,T),\color{black}{1\leq i\leq 2}$\\
	  $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{8.4 mm}\T{v} = \T{0} \hspace{ 5 mm}\quad\text{on}\quad\Gamma_{\text{lat}}\times(0,T)$\\
	  $\quad\quad\quad\quad\quad\quad\hspace{7.2 mm}\nu\frac{\partial \T{v}}{\partial \T{n}_\Gamma} - p\T{n}_{\Gamma} = \T{0}\hspace{5 mm}\quad \text{on}\quad\color{blue}{\Gamma_{\text{out}}}\times(0,T)$\\
	  $\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{4.2 mm}\T{v}(\cdot,0) = \T{v}_{0} \hspace{3 mm}\quad\text{in}\quad\Omega
       $\endtabular}}
 \put(30,-180){\color{blue}\line(1,0){240}}\put(270,-180){\line(0,1){45}}\put(270,-115){\line(0,1){15}}\put(30,-180){\line(0,1){45}}\put(10,-135){\line(1,0){20}}\put(10,-115){\line(1,0){20}}\put(30,-115){\line(0,1){15}}\put(10,-135){\color{red}\line(0,1){20}}\put(270,-135){\line(1,0){20}}\put(270,-115){\line(1,0){20}}\put(290,-135){\color{red}\line(0,1){20}}\put(30,-150){\color{gray}\line(1,0){240}}
    \put(45,-100){\color{black}\line(1,0){25}} \put(30,-100){\line(1,0){15}}\put(70,-100){\line(1,0){160}}\put(230,-100){\color{black}\line(1,0){25}}\put(255,-100){\line(1,0){15}}
    \put(140,-176){\makebox(20,20){$\Omega_{2}$}}\put(140,-135){\makebox(20,20){$\Omega_{1}$}}
\end{picture}
}
%\put(30,-180){\line(0,1){80}}
\frame[t]{\frametitle{Stokes--Brinkman equation}\framesubtitle{weak formulation}
Find~$(\T{v},p) \in W(0,T)\times Q(0,T)$ such that
\begin{align*}
 \frac{\partial}{\partial t} (\T{v}, \T{z})_{0, \Omega} + a_{s}(\T{v}, \T{z}) - b_{s}(p, \T{z}) &= 0, \quad t \in (0,T]\\
  b_{s}(z, \T{v}) &= 0, \quad t\in (0,T]\\
(\T{v}(\cdot, 0),\T{z})_{0, \Omega} &= (\T{v}^{0},\T{z})_{0, \Omega}
\end{align*}
holds true for all~$\T{z} \in V_{0}$, $z \in Q(0,T)$, where
\begin{align*}
%V := {\T{v} \in H^{1}(\Omega) | \T{v}|_{\Gamma_{\text{in}}^{i}} = \T{v}_{\text_{in}}^{i}, 1 \leq i \leq 2, \T{v}|_{\Gamma_{\text{lat}}} = 0}\\
 V &:= \{ \T{v} \in H^1(\Omega) \,|\, \T{v}|_{\Gamma_{\text{in}}^{(i)}} = \T{v}_{\text{in}}^{(i)}, \T{v}|_{\Gamma_{\text{lat}}} = \T{0} \} \\
V_0 &:= \{ \T{v} \in H^1(\Omega) \,|\, \T{v}|_{\Omega \setminus \Gamma_{\text{out}}} = \T{0} \}, \\
 W(0,T) &:= H^{1}(0,T;V^{*})\cap L^{2}(0,T;V), \\
Q(0,T) &:= L^{2}(0,T;L^{2}(\Omega)).
\end{align*}
}

\subsection{Advection diffusion}
\frame[t]{\frametitle{Advection diffusion equation}
\begin{picture}(300,0)\linethickness{0.5mm}
\put(-10,-55){\makebox(325,60){\centering\tabular{@{}l@{}}$
      \hspace{13mm}\frac{\partial c}{\partial t} - \nabla\cdot D\nabla c + \T{v}\cdot\nabla c =0 \quad\hspace{5 mm}\text{in}\quad\Omega_{1}\times (0,T)$\\
	    $\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{8.5 mm}\frac{\partial c}{\partial \T{n}_{\Gamma}} = 0\quad\hspace{5 mm}\text{on}\quad {\color{blue}\Gamma_1}\times(0,T)$\\
	     $\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{4.6 mm}c(\cdot,0) = c_{0}\quad\hspace{4 mm} \text{in}\quad\Omega_{1}$\endtabular}}
 \put(30,-160){\line(0,1){45}}\put(10,-115){\color{blue}\line(1,0){20}}\put(10,-95){\color{blue}\line(1,0){20}}\put(10,-115){\color{blue}\line(0,1){20}}\put(270,-115){\color{blue}\line(1,0){20}}\put(270,-95){\color{blue}\line(1,0){20}}\put(290,-115){\color{blue}\line(0,1){20}}\put(30,-160){\color{black}\line(1,0){240}}\put(30,-130){\color{blue}\line(0,1){15}}\put(30,-95){\color{blue}\line(0,1){15}}\put(270,-130){\color{blue}\line(0,1){15}}\put(270,-95){\color{blue}\line(0,1){15}}\put(30,-130){\color{blue}\line(1,0){240}}
    \put(45,-80){\color{blue}\line(1,0){25}} \put(30,-80){\color{blue}\line(1,0){15}}\put(70,-80){\color{blue}\line(1,0){160}}\put(230,-80){\color{blue}\line(1,0){25}}\put(255,-80){\color{blue}\line(1,0){15}}
    \put(140,-156){\makebox(20,20){$\Omega_{2}$}}\put(140,-115){\makebox(20,20){$\Omega_{1}$}}
    \put(30,-160){\color{black}\line(0,1){30}}\put(270,-160){\color{black}\line(0,1){30}}
\end{picture}
}


\frame[t]{\frametitle{Advection diffusion equation}\framesubtitle{weak formulation}
Find~$c \in W(0,T)$ such that
\begin{align*}
 \frac{\partial}{\partial t}(c,z)_{0,\Omega_{1}} + a_{d}(c,z) &= 0, \quad t \in (0,T]\\
 (c(\cdot, 0),z)_{0,\Omega_{1}} &= (c^{0},z)_{0,\Omega_{1}}
\end{align*}
holds true for all~$z \in H^{1}(\Omega_{1})$.
}

\frame[t]{\frametitle{Advection diffusion equation}\framesubtitle{discretization in space}
Consider
\begin{align*}
 V_{h} := \{ v_{h} \in C(\Omega_{1}) \,\mid \, v_{h}|_K \in P_{2}(K), K \in \mathcal{T}_{h}(\Omega_{1})\}.
\end{align*}
Find then~$\T{c} \in C^{1}(0,T;V_{h})$ s. t. it holds for all~$\psi \in V_{h}$:
\begin{align*}
 \sum_{K \in \mathcal{T}_{h}(\Omega_{1})} (\frac{\mathrm{d} \T{c}}{\mathrm{d}t}, \psi + \tau_{K} h_{K} (\T{v} \cdot \nabla \psi))_{0,K} +
(D\nabla \T{c}, \nabla \psi)_{0, \Omega_{1}} +\\ (\T{v} \cdot \nabla \T{c}, \psi)_{0, \Omega_{1}} + \\
\sum_{K \in \mathcal{T}_{h}(\Omega_{1})} \tau_{K} h_{K} (-D \Delta \T{c} + \T{v} \cdot \nabla \T{c}, \T{v} \cdot \nabla \psi)_{0,K} &= 0\\
(\T{c}(\cdot,0),\psi)_{0, \Omega_{1}} &= (\T{c}^{0}, \psi)_{0,\Omega_{1}}.
\end{align*}
}

\frame[t]{\frametitle{Discretization in space}
\begin{picture}(300,0)\thicklines
\put(17,-113){\vector(0,-1){27}}\put(0,-15){\framebox(300,28){$\text{min} \quad J( \T{u} ) = \frac{1}{2} \| c(\cdot, T)- c^{\text{foc}} \|_{0,\Omega_{1}}^{2}$}}\put(0,-112){\framebox(300,60){\centering\tabular{@{}l@{}}$
        M_{s} \frac{\partial \T{v}_{h} (t)}{\partial t} + A_{s} \T{v}_{h} (t) - B_{s}^{T} p_{h}(t) + C_{s} \T{u}(t) = 0,\quad  t \in (0,T]$\\
	    $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{3.25 mm} B_{s} \T{v}_{h}(t) = 0, \quad t \in (0,T]$\\
	    $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{1.2 mm} M_{s}\T{v}_{h}(0) = \T{v}_{h}^{0}$\endtabular
	    }}\put(0,-180){\framebox(300,40){\centering\tabular{@{}l@{}}$\hspace{6mm}(M_{d}^{1} +M_{d}^{2}(\T{v}_{h})) \frac{\partial c_{h}(t)}{\partial t} + A_{d}(\T{v}_{h}) c_{h}(t) = 0, \quad t \in (0,T]$\\
	    $\quad\quad\quad\quad\quad\quad\hspace{26.1 mm} M_{d}^{1} c_{h}(0) = c_{h}^{0}$\endtabular}}
	    \put(19,-136){\makebox(20,20){$\T{v}_{h}$}}\put(17,-27){\vector(0,-1){25}}\put(19,-47){\makebox(20,20){$\T{u}$}}
\end{picture}
}

%MR Folien

\section[POD]{Proper Orthogonal Decomposition}

\subsection{Idea}

\frame[t]{\frametitle{Motivation}
  We want to solve
  \begin{align*}
    \tfrac{\mathrm{d}}{\mathrm{d}t}\T{y}(t) &= A \T{y}(t) + F(\T{y}(t)) \\
    \T{y}(0) &= \T{y}_0
  \end{align*}
  with varying values of parameters, where
  $\T{y}(t) \in \mathbb{R}^n$ is unknown and $A \in \mathbb{R}^{n \times n}$, $F{:}\, \mathbb{R}^n \to \mathbb{R}^n$,
  $\T{y}_0 \in \mathbb{R}^n$ are given.
  \vfill

  \only<1>{
  Such problems arise in iterative algorithms for solving optimization problems with 
  differential equations as constraints. 
  }

  \only<2>{
  \emph{Empirical observation:}
  The solution trajectories are often approximately contained in
  a low-dimensional subspace of~$\mathbb{R}^{n}.$
  }
}

\frame[t]{\frametitle{Plan}
  \emph{Main idea:}
  Because we do not need the full flexibility of~$\mathbb{R}^{n}$, we can
  instead search for the solutions in a subspace having much smaller dimension~$\ell \ll n.$
}










%\section[POD]{Proper Orthogonal Decomposition}
\frame[t]{\frametitle{Snapshots}
  \emph{Question:} \\
  How to find the low-dimensional supspace of~$\mathbb{R}^{n}$ which
  approximately contains the trajectories?
  \vfill
  \pause
  \emph{One possibility:} \\
  Record snapshots~$\T{y}_i := \T{y}(t_i) \in \mathbb{R}^{n}$
  of a ``typical'' trajectory at certain times~$t_1,\ldots,t_{n_{s}}$.
  Then find an~$\ell$-dimensional subspace with smallest distance
  to the snapshots.}


\frame[t]{\frametitle{Proper Orthogonal Decomposition}
  Find an~$\ell$-dimensional subspace, $\ell \ll n$, with the smallest distance
  to the snapshots:
  \vfill

  \only<1>{
   Minimize
  \[ \sum_{i=1}^{n_{s}} \|\T{y}_i - P_V(\T{y}_i)\|^2 \]
   such that
  \begin{align*}
    V &\in \text{set of all~$\ell$-dimensional} \\
    &\mathrel{\phantom{\in}} \text{subspaces of~$\mathbb{R}^{n}$,}
  \end{align*}
  where~$P_V$ denotes the orthogonal projection onto~$V$.
  }
  
  \only<2>{
  \emph{Better formulation:} Minimize
  \[ J(\T{v}_1,\ldots,\T{v}_{\ell}) := \sum_{i=1}^{n_{s}} \Bigl\|\T{y}_i - \sum_{k=1}^{\ell} \langle\T{y}_i,\T{v}_k\rangle\T{v}_k\Bigr\|^2 \]
   such that
  \begin{align*}
    \T{v}_1,\ldots,\T{v}_{\ell} &\in \mathbb{R}^{n} \\
    \langle \T{v}_j, \T{v}_k \rangle &= \delta_{jk},
    \ 1 \leq j,k\leq \ell.
  \end{align*}
  }
}

\subsection{Numerical solution}
\frame[t]{\frametitle{Numerical solution}
\begin{enumerate}
 \item by using the singular value decomposition of~$Y := (\T{y}_{1} | \cdots | \T{y}_{n_{s}}) \in \mathbb{R}^{n \times n_{s}}$
 \item by using the eigenvalue decomposition of~$\mathcal{K}:= ((\T{y}_{i},\T{y}_{j}))_{i,j} \in \mathbb{R}^{n_{s} \times n_{s}}$
\end{enumerate}
}

\frame[t]{\frametitle{Solution by singular value decomposition}
  \begin{satz}[Singular value decomposition, ca. 1873]
    Let~$Y \in \mathbb{R}^{n \times n_{s}}$. Then there exist orthogonal 
    matrices~$\widetilde V \in \mathbb{R}^{n \times n}$ and $W \in \mathbb{R}^{n_{s} \times n_{s}}$ with
    \[ Y = \widetilde V \Sigma W^{T}, \]
    where~$\Sigma \in \mathbb{R}^{n \times n_{s}}$ is a (rectangular) diagonal matrix.
    The diagonal elements are called the \emph{singular values}. They are nonnegative
    and given in descending order.
  \end{satz}

  \vfill
  Then a solution of the optimization problem is given by
  the first~$\ell$~columns of~$\widetilde V$, when $Y := (\T{y}_1 | \cdots |
  \T{y}_{n_{s}}) \in \mathbb{R}^{n \times n_{s}}$ denotes the matrix of the snapshots.
}

\frame[t]{ \frametitle{Solution by eigenvalue decomposition}
  Consider the eigenvalue decomposition of~$\mathcal{K}$:
  \begin{align*}
    \mathcal{K} = T D T^{*} \in \mathbb{R}^{n_{s} \times n_{s}}.
  \end{align*}
  Then the POD basis vectors are given by
  \begin{align*}
    \T{u}_{i} := \frac{1}{\sqrt{D_{ii}}} Y \, \T{t}_i
  \end{align*}
  for~$1 \leq i \leq N$, $D_{ii} \neq 0$, with~$T = (\T{t}_1 | \cdots | \T{t}_{n_{s}}) \in \mathbb{R}^{n_{s} \times n_{s}}$
  and the snapshot matrix~$Y := (\T{y}_1 | \cdots | \T{y}_{n_{s}})$.
}

\frame[t]{\frametitle{Approximation error}
  The approximation error is given by
  \[ J(\T{v}_1,\ldots,\T{v}_k)
    = \sum_{i=1}^{n_{s}} \|\T{y}_i\|^2 - \sum_{k=1}^\ell \sigma_k^2, \]
  where~$\sigma_j$ denotes the singular values of $Y = (\T{y}_1 | \cdots |\T{y}_{n_{s}}) \in \R^{n \times n_{s}}.$
  \vspace{1em}

  Thus, the POD basis~$\T{v}_1, \ldots, \T{v}_k$ is ordered
  by importance.
}



\subsection[Reduction by projection]{Model reduction by projection}
%\section[Projektion]{model reduction via projection} 
\frame[t]{\frametitle{Model reduction by projection}
  Let~$\T{v}_1, \ldots, \T{v}_{\ell} \in \mathbb{R}^{n}$ denote an orthonormal basis
  of a low-dimensional subspace of~$\mathbb{R}^n$,~$\ell \ll n$, and
  let~$V_{\ell} := (\T{v}_1 | \cdots | \T{v}_{\ell}) \in \mathbb{R}^{n \times \ell}$.
  We make the ansatz
  \[ \T{y}(t) := V_{\ell} \T{\tilde{y}}(t), \]
  with~$\T{\tilde y} \in \mathbb{R}^{\ell}$.
  The Galerkin projection is then given by
  \begin{align*}
     \ddt\T{\tilde{y}}(t) &= V_{\ell}^{T} A V_{\ell} \T{\tilde{y}}(t) + V_{\ell}^{T} F(V_{\ell} \T{\tilde{y}}(t)), \\
     \T{\tilde{y}}(0) &= V_{\ell}^{T} \T{y}_0,
  \end{align*}
  in which the linear part is \textcolor{darkgreen}{reduced}~($V_{\ell}^{T} A V_{\ell} \in \mathbb{R}^{\color{darkgreen}{\ell
  \times \ell}}$), but the nonlinear one is \textcolor{darkred}{not}.
}


\section[DEIM]{Discrete Empirical Interpolation Method}
\subsection{Idea}
\frame[t]{\frametitle{Discrete Empirical Interpolation Method}\framesubtitle{[Chaturantabut, Sorensen (2009)]}
  \only<1>{
  The partially reduced order model is given by
  \begin{align*}
    \ddt \ytilde(t) &= \textcolor{darkgreen}{V_{\ell}^{T} A V_{\ell}} \ytilde(t) +
    \textcolor{darkred}{V_{\ell}^{T} F(V_{\ell}} \ytilde(t)\textcolor{darkred}{)}, \\
    \ytilde(0) &= V_{\ell}^{T} \T{y}_0.
  \end{align*}
  \vfill
  }
  For example let~$F{:}\, \R^n \to \R^n$ have the form
  \[ F\!\begin{pmatrix}x_1\\\vdots\\x_n\end{pmatrix} =
    \begin{pmatrix}f(x_1)\\\vdots\\f(x_n)\end{pmatrix}\!, \]
  where~$f{:}\, \R \to \R$.
  \vfill
  \only<2>{
  To construct the reduced order model, we record snapshots~$\T{z}_i = F(\T{y}(t_i)) \in \R^n$,~$1
  \leq i \leq n_{s}$ and determine a POD basis~$\T{u}_1,\ldots,\T{u}_k \in \R^n$, $k \ll n$.
  }
}

\frame[t]{\frametitle{Projection of the nonlinearity}
  \vspace*{-0.5em}
  Let~$\T{u}_1,\ldots,\T{u}_k \in \R^n$, $k \ll n$ be a POD-basis and
  set~$U_{k} := (\T{u}_1 | \cdots | \T{u}_k) \in \R^{n \times k}$.
  \vfill

  Recall the partially reduced order model
  \begin{align*}
    \ddt \ytilde(t) &= \textcolor{darkgreen}{V_{\ell}^{T} A V_{\ell}} \ytilde(t) +
    \textcolor{darkred}{V_{\ell}^{T} F(V_{\ell}} \ytilde(t)\textcolor{darkred}{)}.
  \end{align*}
  \vfill

  \emph{First idea:} The equation
  \begin{align*}
    \ddt \ytilde(t) &= V_{\ell}^T A V_{\ell} \ytilde(t) + V_{\ell}^T U_{k} U_{k}^T F(V_{\ell} \ytilde(t))
  \end{align*}
  should still be a good approximation, because~$U_{k} U_{k}^T$ is the orthogonal
  projection onto the span of~$\T{u}_1,\ldots,\T{u}_k$.
}

\frame[t]{\frametitle{Projection of the nonlinearity}
   \small
     We search for a projection matrix~$Q \in \R^{n \times n}$ onto the span of the optimal basis
    $\T{u}_1,\ldots,\T{u}_k$, such that the nonlinearity 
    $V_{\ell}^T \, Q \, F(V_{\ell} \ytilde(t))$ can be evaluated efficiently.
    To define~$Q \T{x}$ for~$\T{x} \in \R^n$,
    we make the ansatz
    \[ U_{k} \T{c} \approx \T{x} \]
    where the coefficient vector~$\T{c} \in \R^k$ is unknwon.
    We can only approximately fulfill a certain choice~$p_1,\ldots,p_k$ of the equations:
    \[ P^T U_{k} \T{c} \approx P^T \T{x} \]
    with~$P := (\T{e}_{p_1} | \cdots | \T{e}_{p_k}) \in \R^{n \times k}$
    and~$U = (\T{u}_1 | \cdots | \T{u}_\ell) \in \R^{n \times k}$.
    \vfill
    Then we set~$Q\T{x} := U_{k} \T{c} = U_{k} (P^T U_{k})^{-1} P^T \T{x} \in \R^n$.
}




\frame[t]{\frametitle{Reduced order model}
  Recall the partially reduced order model
  \begin{align*}
    \ddt \ytilde(t) &= \textcolor{darkgreen}{V_{\ell}^T A V_{\ell}} \ytilde(t) + \textcolor{darkred}{V_{\ell}^T F(V_{\ell}} \ytilde(t)\textcolor{darkred}{)}, \\
    \ytilde(0) &= V_{\ell}^T \T{y}_0.
  \end{align*}
  \vfill
  With the projection matrix
  \[ Q = U_{k} (P^T U_{k})^{-1} P^T \in \R^{n \times n} \]
  we obtain the fully reduced order model
  \begin{align*}
    \ddt \ytilde(t) &= V_{\ell}^T A V_{\ell} \ytilde(t) +
    V_{\ell}^T \, U_{k} (P^T U_{k})^{-1} P^T \, F (V_{\ell} \ytilde(t)) \\
    \ytilde(0) &= V_{\ell}^T \T{y}_0.
  \end{align*}
}



\subsection{Selection algorithm}
\frame[t]{\frametitle{Selection algorithm}
  \small
  Input: \tabto{3cm} orthonormal basis~$\T{u}_1,\ldots,\T{u}_k \in \R^n$ \\
  Output: \tabto{3cm} selection matrix~$P$ such that\\
  \tabto{3cm} $U_{k} (P^T U_{k})^{-1} P^T$ is a good projection matrix
  \vfill

  \begin{enumerate}
    \item $\T{r}_1 := \T{u}_1$. \\
          $p_1 := \argmin\limits_{i = 1,\ldots,n} |(\T{r}_1)_i|$,
	  $P := (\T{e}_{p_1}) \in \R^{n \times 1}$.
    \item $\T{r}_2 := \T{u}_2 - \widetilde U (P^T \widetilde U)^{-1} P^T
    \T{u}_2$ with~$\widetilde U = (\T{u}_1) \in \R^{n \times 1}$. \\
          $p_2 := \argmin\limits_{i = 1,\ldots,n} |(\T{r}_2)_i|$,
	  $P := (\T{e}_{p_1} | \T{e}_{p_2}) \in \R^{n \times 2}$.
    \item $\T{r}_3 := \T{u}_3 - \widetilde U (P^T \widetilde U)^{-1} P^T
    \T{u}_3$ with~$\widetilde U = (\T{u}_1|\T{u}_2) \in \R^{n \times 2}$. \\
          $p_3 := \argmin\limits_{i = 1,\ldots,n} |(\T{r}_3)_i|$,
	  $P := (\T{e}_{p_1} | \T{e}_{p_2} | \T{e}_{p_3}) \in \R^{n \times 3}$.
    \item and so on~$\ldots$
  \end{enumerate}
}

\subsection{Error estimate}
\frame[t]{\frametitle{Error estimate}
  \begin{satz}[Chaturantabut, Sorensen (2009)]
    For the approximation
    \[ \widehat F(\T{x}) := U_{k} (P^T U_{k})^{-1} P^T F(\T{x}) \]
    holds the error estimate
    \[ \|F(\T{x}) - \widehat F(\T{x})\|_2 \leq \|(P^T U_{k})^{-1}\|_2\, \|(I - U_{k} U_{k}^T) \T{F}(x)\|_2. \]
  \end{satz}
  Up to the constant~$\|(P^T U_{k})^{-1}\|_2$ we have just the
  consistency error
  \[ \|(I - U_{k} U_{k}^T) \T{F}(x)\|_2 = \min\limits_{\T{v} \in \operatorname{im} U_{k}} \|\T{F}(x) - \T{v}\|_2. \]
}

\frame[t]{\frametitle{Error estimate}
   The DEIM algorithm garanties that~$P^T U_{k}$ is invertible.
   The term~$\|(P^T U_{k})^{-1}\|_2$ can be estimated by a constant,
   but the bound is very conservative.
}

%ab hier die anderen Folien
\section[DEIM II]{DEIM in a general Hilbert space}
\frame[t]{\frametitle{DEIM in a general Hilbert space}
We want to reduce a general nonlinear function
\begin{align*}
 F {:}\, K \longrightarrow H
\end{align*}
where~$K$ is an arbitrary parameter space and~$H$ is a finite-dimensional Hilbert space.
\vspace{1em}

For example, we use~$H := \mathbb{R}^{n_c \times n_c}$ for reducing the advection diffusion equation.
}

\frame[t]{\frametitle{DEIM in a general Hilbert space}
\begin{enumerate}
 \item Record Snapshots~$z_{1}, \ldots, z_{n_s} \in H$.
\item Calculate a POD basis~$u_{1},\ldots, u_{k} \in H$ by either
\begin{enumerate}
\item using the operator singular value decomposition of
\[\begin{array}{@{}rrcl@{}}
 \mathcal{R}{:} & H &\longrightarrow& H\\
  & x &\longmapsto& \sum_{i=1}^{n_s} (x,z_{i})_{H} z_{i}
\end{array}\]
\item or using the eigenvalue decomposition of the matrix
\begin{align*}
 \mathcal{K} := ((z_{i},z_{j})_{H})_{ij} \in \mathbb{R}^{n_s \times n_s}.
\end{align*}
\end{enumerate}
\item Apply the DEIM algorithm to~$\mathcal{I}(u_{1}), \ldots, \mathcal{I}(u_{k})$ where~$\mathcal{I} {:}\, H \to \mathbb{R}^{n}$ is a suitable isomorphism.
\end{enumerate}
}

\frame[t]{\frametitle{Error estimate}
Then we obtain the error estimate
\begin{align*}
\|F(\T{x}) - \widehat F(\T{x})\|_{H} \leq \|\mathcal{I}^{-1} \|\, \|(P^T U_{k})^{-1}\|_2\, \|(I - U_{k} U_{k}^T) \mathcal{I}(\T{F}(x))\|_2,
\end{align*}
which depends on the isomorphism~$\mathcal{I}$.
}

\end{document}
