
\subsection{\bf Parallelism in Gauss-Seidel Iteration}

\begin{slide}

\begin{itemize}
\item Conventional Gauss-Seidel canNOT be easily parallelized
because it has sequential update order

\begin{eqnarray*}
x_n^{(k)} & \mbox{requires} & x_{n-1}^{(k)}\ \ \ldots \\
&& \\
x_{n-1}^{(k)} & \mbox{requires} & x_{n-2}^{(k)}\ \ \ldots \\
\vdots\hspace{1em} \\
x_2^{(k)} & \mbox{requires} & x_1^{(k)}, \mbox{etc.} \\
\end{eqnarray*}

\item There are two parallelization strategies

\begin{enumerate}
\item Keep same algorithm---pipelined wavefront method
\item Change algorithm---red/black two-phase
\end{enumerate}

\end{itemize}

\end{slide}
