\documentclass[12pt,a4paper]{article}

\usepackage{amstext}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{cancel}
\usepackage{fancyhdr}
\usepackage{listings}
\usepackage{pstricks}
\usepackage{pst-plot}
\usepackage{wasysym}
\usepackage{rotating}

\title{\textsc{Numerical Algorithms for Visual Computing II \\ \large Assignment 7}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \scriptsize 2031259} \and \shortstack[c]{Andreas Steinel \\ \scriptsize
2029984}}
\date{}

\pagestyle{fancy}

\lhead{Assignment 7}
\chead{}
\rhead{Dithmar (2031259), Steinel (2029984)}
\lfoot{NAVC II}
\cfoot{Page \thepage}
\rfoot{WS 2008/2009}

\begin{document}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\newcommand{\exercise}[1]{\subsection{#1}}
\renewcommand{\theenumi}{\textbf{\alph{enumi}}}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[2]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[#1]{#2}\\[0.2cm]
	\end{figure}
	}

\newcommand{\m}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\+}{\phantom{-}}
\newcommand{\f}{\dfrac}

\maketitle

\thispagestyle{empty}

\newpage
\setcounter{page}{1}
\setcounter{section}{7}

\exercise{Linear $\stackrel{Paranormal..?}{\text{Parabolic}}$ Stuff}
We know that $\Delta x = \Delta y = h$ and therefore $|\sigma_i| = h^2$. $i$ means here the pixel position and
$ i \in \SetR^2$. Furthermore, $D = I$, which makes $D$ negligible due to $D \nabla u = \nabla u$. $n$ means the current time
step, and $n+1$ is the next timestep.

Considering (12.16), one has to derive (with respect to one axis only, $i$ means here 1D-coordinate)
for the $x$-axis ($\vec{n} = (\pm 1,0)^\top$):
\begin{eqnarray*}
  \nabla u \big|_{m_{i,1}} &\approx& \frac{1}{h} (u_{i+1} - u_{i}) \\
  \nabla u \big|_{m_{i,3}} &=& \nabla u \big|_{m_{i-1,1}} (1,0)^\top\\
    &=& \frac{1}{h} (u_{i} - u_{i-1}) (1,0)^\top\\
    &=& -1 \frac{1}{h} (u_{i} - u_{i-1}) (-1,0)^\top\\
\end{eqnarray*}
$y$-axis follows analogously. So, we derive all $m_{i,k}$ as
\begin{eqnarray*}
  \nabla u \big|_{m_{i,1}} &\approx& \frac{1}{h} (u_{i+1} - u_{i}) \quad \quad \text{$i$ is $x$-axis}\\
  \nabla u \big|_{m_{i,3}} &\approx& -\frac{1}{h} (u_{i} - u_{i-1}) \quad \; \text{$i$ is $x$-axis} \\
  \nabla u \big|_{m_{i,2}} &\approx& \frac{1}{h} (u_{i+1} - u_{i}) \quad \quad \text{$i$ is $y$-axis} \\
  \nabla u \big|_{m_{i,4}} &\approx& -\frac{1}{h} (u_{i} - u_{i-1}) \quad \; \text{$i$ is $y$-axis}
\end{eqnarray*}
Now, let's derive the final diffusion equation with a nonlinear part $c_i$ (needed in Exercise 2):
\begin{eqnarray*}
  \underbrace{u_i( t + \delta t)}_{u^{n+1}_i} &\stackrel{(12.4)}{=}& \underbrace{u_i(t)}_{u^{n}_i} + c^n_i
       \int_{t}^{t+\delta t} \left[ \frac{\mathrm d}{\mathrm dt} \underbrace{u_i(t)}_{u^{n+1}_i} \right] \; \mathrm dt' \\
  u^{n+1}_i &\stackrel{(12.3)}{=}& u^{n}_i + c^n_i
       \int_{t}^{t+\delta t} \left[ \frac{1}{h^2} \sum_{k=1}^4 \int_{l_{i,k}} (\nabla u_i \vec{n}) ds \right] \; \mathrm dt' \\
  u^{n+1}_i &\stackrel{(12.11)}{=}& u^{n}_i + c^n_i
       \frac{\delta t}{h^2} \sum_{k=1}^4 \int_{l_{i,k}} (\nabla u^n_i \vec{n}) \; \mathrm ds
\end{eqnarray*}
\begin{eqnarray*}
  u^{n+1}_i &\stackrel{(12.13)}{=}& u^{n}_i + c^n_i
       \frac{\delta t}{h^2} \sum_{k=1}^4 h \left[ \nabla u^n_i \vec{n} \right] \Big|_{m_{i,k}} \\
  u^{n+1}_i &=& u^{n}_i + c^n_i
       \frac{\delta t}{h} \sum_{k=1}^4 \left[ \nabla u^n_i \vec{n} \right] \Big|_{m_{i,k}} \\
\end{eqnarray*}
Now, let's split the coordinate $i$ into its components $(x,y)$:
\begin{eqnarray*}
  u^{n+1}_{x,y} &\stackrel{(12.16)}{=}& u^{n}_{x,y} + c^n_{x,y}
       \frac{\delta t}{h^2} \Big[
           (u_{x+1,y} - u_{x,y}) \\ && \quad \quad \quad \quad \quad \quad +( -(u_{x,y} - u_{x-1,y}))
           (u_{x,y+1} - u_{x,y}) \\ && \quad \quad \quad \quad \quad \quad +( -(u_{x,y} - u_{x,y-1}))
       \Big] \\
  u^{n+1}_{x,y} &=& u^{n}_{x,y} + c^n_{x,y}
       \frac{\delta t}{\Delta x^2} (u_{x+1,y} - 2 u_{x,y} + u_{x-1,y}) \\ && \quad \quad + c^n_{x,y}
       \frac{\delta t}{\Delta y^2} (u_{x,y+1} - 2 u_{x,y} + u_{x,y-1})
\end{eqnarray*}
The proof concludes with  $c^n_{x,y} = 1$  (isotropic, linear diffusion).

%Similar to (12.11), we have for $t = n \delta t$
%$$\dfrac{1}{|\sigma_i|} \int_t^{t + n \delta t} \left[\sum_{k=1}^4 \int_{l_{i,k}} (D \nabla u) \cdot \vec{n} \; \mathrm ds\right] \; \mathrm dt' \approx \dfrac{n \delta t}{|\sigma_i|} \sum_{k=1}^4 \int_{l_{i,k}} (D \nabla u) \Big|_t \cdot \vec{n} \; \mathrm ds$$
%Since we have $h = \Delta x = \Delta y$, we get similar to (12.12):
%$$|\sigma_i| = h^2$$
%The boundary integrals can now be approximated as
%$$\int_{l_{i,k}} (D \nabla u) \cdot \vec{n} \approx h \cdot \left[(D \nabla u) \cdot \vec{n}\right] \Big|_{m_{i,k}}$$
%It follows
%$$\dfrac{n \delta t}{h^2} \sum_{k=1}^4 h \left[(D \nabla u) \cdot \vec{n}\right] \Big|_{m_{i,k}}$$
%We know that -- at each point $m_{i,k}$ -- we only need to approximate the $x$- or $y$-direction of $D \nabla u$, respectively. Let's stick to what we've done in the script, i.e. let's consider the right boundary segment of $\sigma_i$. Taking into account that $D=I$, we get $I \nabla u = \nabla u$. We have as an intermediate result
%$$\dfrac{n \delta t}{h} \sum_{k=1}^4 [\nabla u \cdot \vec{n}] \Big|_{m_{i,1}}$$
%According to (12.16), we can approximate $\nabla u \Big|_{m_{i,1}}$ by $\dfrac{1}{h} (\bar{u}_{i+1} - \bar{u}_i)$.

\exercise{Creepy nonlinear $\stackrel{Paranormal..?}{\text{Parabolic}}$ Phenomenae}
\begin{enumerate}
	\item First, let's reformulate our problem:
		\begin{eqnarray*}
            u_t &=& \nabla(D \nabla u) \\
                &=& \nabla \left(\begin{pmatrix}g(|\nabla u|^2)& 0 \\ 0 & g(|\nabla u|^2)\end{pmatrix}  \begin{pmatrix}u_x \\ u_y \end{pmatrix} \right)\\
                &=& \nabla \left( g(|\nabla u|^2) \begin{pmatrix}u_x \\ u_y \end{pmatrix} \right)\\
                &=& g(|\nabla u|^2) \: \nabla (\nabla u) \\
                &=& c \: \nabla ( \nabla u) 
		\end{eqnarray*}
        So, it's exactly in the form of the result of the previous exercise. Whereas $c$ is now depending on $u$ of the
        current time step, so this is the nonlinear term.

        For a numerical scheme, we need to discretise $c$, so
		\begin{eqnarray*}
            c^t_{i,j} &=& g(|\nabla u|^2) \\
                 &=& \frac{1}{1+|\nabla u|^2} \\
                 &=& \dfrac{1}{1+\frac{1}{4\Delta x^2} (u_{i+1,j} - u_{i-1,j})^2 +
                                 \frac{1}{4\Delta y^2} (u_{i,j+1} - u_{i,j-1})^2}
		\end{eqnarray*}
        If we consider again $\Delta x = \Delta y = h$ and $\bar{h} = \frac{1}{4 \: h^2}$, we get
		\begin{eqnarray*}
            c^t_{i,j} &=& \dfrac{1}{1+ 
                 \bar{h} \: (u_{i+1,j} - u_{i-1,j})^2 + \bar{h} \: (u_{i,j+1} - u_{i,j-1})^2} \\
                 &=& \frac{4 \: h^2}{4 \: h^2 + (u_{i+1,j} - u_{i-1,j})^2 + (u_{i,j+1} - u_{i,j-1})^2} 
		\end{eqnarray*}

%		\begin{eqnarray*}
%			g(|\nabla u|^2) I \nabla u & = & \dfrac{1}{1 + |\nabla u|^2} I \nabla u \\
%			& = & \left(\begin{array}{cc}\dfrac{1}{1 + |\nabla u|^2} & 0 \\[0.3cm] 0 & \dfrac{1}{1 + |\nabla u|^2}\end{array}\right) \left(\begin{array}{c}u_x \\[0.3cm] u_y\end{array}\right) \\
%			& = & \dfrac{1}{1 + |\nabla u|^2} (u_x + u_y)
%		\end{eqnarray*}
%		It follows
%		$$\dfrac{\mathrm d}{\mathrm dt} \bar{u}_i(t) = \dfrac{1}{|\sigma_i|} \sum_{k=1}^4 \int_{l_{i,k}} \left(\dfrac{1}{1 + |\nabla u|^2} (u_x + u_y)\right) \cdot \vec{n} \; \mathrm ds$$
%		Let's consider the time integration. For the left hand side, we get
%		$$\int_t^{t + \delta t} \left[\dfrac{\mathrm d}{\mathrm dt} \bar{u}_i(t)\right] \; \mathrm dt = \bar{u}_i(t + \delta t) - \bar{u}_i(t)$$
%		For the right hand side, we have
%		$$\dfrac{1}{|\sigma_i|} \int_t^{t + \delta t} \left\{\sum_{k=1}^4 \int_{l_{i,k}} \left(\dfrac{1}{1 + |\nabla u|^2} (u_x + u_y)\right) \cdot \vec{n} \; \mathrm ds\right\} \; \mathrm dt$$
%		For the spatial integration, let's consider the Euler forward scheme which yields for the interval $[t, t + \delta t]$ the following:
%		$$\dfrac{1}{|\sigma_i|} \int_t^{t + \delta t} \left[\sum_{k=1}^4 \int_{l_{i,k}} \left(\dfrac{1}{1 + |\nabla u|^2}(u_x + u_y)\right) \cdot \vec{n} \; \mathrm ds\right] \; \mathrm dt'$$ $$\approx \dfrac{\delta t}{|\sigma_i|} \sum_{k=1}^4 \int_{l_{i,k}}\left(\dfrac{1}{1 + |\nabla u|^2} (u_x + u_y)\right) \Big|_t \cdot \vec{n} \; \mathrm ds$$
%		Let's go on by assuming $|\sigma_i| = h^2$ (since $h = \Delta x = \Delta y$) and
%		$$\int_{l_{i,k}} \left(\dfrac{1}{1 + |\nabla u|^2} (u_x + u_y)\right) \cdot \vec{n} \; \mathrm ds \approx h \cdot \left[\left(\dfrac{1}{1 + |\nabla u|^2} (u_x + u_y)\right) \cdot \vec{n}\right] \Big|_{m_{i,k}}$$
	\item One can use here the standard notion of Neumann boundary conditions. This would mean the following:
	$$\dfrac{\partial u_t}{\partial v}(x) = 0 \quad \forall x \in \partial\Omega$$
	where $v$ denotes the normal to the boundary $\partial \Omega$. \\
	This ensures that no diffusion happens across the boundaries.
\end{enumerate}

\end{document}
