The Mandelbrot set is the set of complex numbers $c$ obtained by the quadratic recurrence equation :
$$
\left\{\begin{array}{r}
z_0=0\\
z_{(n+1)} = z_n^2+ c
\end{array} \right.
$$
such the suite does not diverge when $n \rightarrow\infty$.
\end{block}
\end{frame}
\begin{frame}[containsverbatim]
\frametitle{Mandelbrodt set}
\begin{block}{Important remarks}
\begin{itemize}
\item{load balancing}
\item{a \textit{colored plot} is obtained by coloring the points with the number of steps required to reach the cut-off value $r_{max}$ value (usually $r_{max} =2$)}
\item{Mandelbrot set is considered as a ``map'' of all the Julia sets because it uses a different $c$ at each $z$.}
{\tiny Figure credit: David Applegate, Robert Bixby, Vasek Chvatal and William Cook.}
\end{center}
\begin{block}{Problem description}
Let us have an undirected weighted graph where : cities are the vertices, the edges are the paths, the weight a distance between two cities. The TSP solution is the shortest path starting and finishing at the same vertice and by visiting all the other vertices one and only one time.
The N-queens problem is the problem of placing $N$ queens on an $N \times N$ board ($N>3$) so that no queen see each other. A queen can move on its row, its column and its diagonals.
The Fast Fourier Transform (FFT) Cooley-Tukey algorithm computes the Discrete Fourier Transform (DFT) of a sequence recursively by a devide-and-conquer approach. The radix-2 decimation in time divides a DFT of size $N$ into two interleaved DFT of size $N/2$.
\end{block}
\end{frame}
%\begin{frame}[containsverbatim]
%\frametitle{FFT with Cooley-Tukey}
%A DFT is described as :
%$$
%X_k = \sum_{n=0}^{N-1} x_n e^{- \frac{2 \pi i}{N} n k}
A minimum spanning tree is a spanning tree of a connected, undirected and weighted graph. It connects all the vertices together with the minimal total weighting for its edges
Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph. It can be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined
The n-body problem aims at simulating a dynamical system of particles under the influence of physical forces. We'll restrain on the gravity field applied on celestial bodies:
Find all the prime numbers $p$ such $p < N$ where $N$ is very large. Enumerate all the multiples of $p$ by counting to $N$ in incerements of $p$ and mark them as ``non-primes''. Do that to $\sqrt{N}$. The list of $p_i$ are all the primes between $p=2$ to $p=\sqrt{N}$.
The game of life is a cellular automaton with simple elements: a cell $c_i$ can be dead ($c_i =0$) or alive ($c_i =1$). At each time step, the following rules are applied :
\begin{itemize}
\item{if $c_i =1$ and its neighbours are 0, 1 or 4 living cells, then $c_{i+1} =0$}
\item{if $c_i =1$ and its neighbours are 2 or 3 living cells, then $c_{i+1} =1$}
\item{if $c_i =0$ and its neighbours are exactly 3 living cells, then $c_{i+1} =1$}
\end{itemize}
\end{block}
\end{frame}
\begin{frame}[containsverbatim]
\frametitle{Game of Life}
\begin{block}{Important remarks}
\begin{itemize}
\item{as this problem is very close to Poisson, we'll accept only non-standard subdomain decomposition (topology)}
\end{itemize}
\end{block}
\end{frame}
\subsection{Jacobi iterative method}
\begin{frame}[containsverbatim]
\frametitle{Jacobi iterative method}
\begin{block}{Problem description}
The Jacobi method solves a linear system $Ax = b$ iteratively:
$$
A = D + R
$$
where D is the diagonal matrix of $A$ and $R$ the rest. The solution $x_{(k+1)}$ is obtained with:
$$
x_{(k+1)} = D^{-1} ( b - R x_k)
$$
where $x_k$ is the $k$-th iteration of $x$
\end{block}
\end{frame}
\subsection{Gauss-Seidel iterative method}
\begin{frame}[containsverbatim]
\frametitle{Gauss-Seidel iterative method}
\begin{block}{Problem description}
The Gauss-Seidel method solves a linear system $Ax = b$ iteratively:
$$
A = L + U
$$
where $L$ is the lower triangular elements of $A$ and $U$ the strict upper elements of $A$. The solution $x_{(k+1)}$ is obtained with: