%---------------------------------------------------------------------
% $Header: $
%---------------------------------------------------------------------
% RAW Benchmark Suite Jacobi documentation
% from 1992 6.846 Problem set 1
%---------------------------------------------------------------------

\documentstyle[times]{article}
\textwidth 17.6cm \textheight 23.5cm
\oddsidemargin -0.3in
\evensidemargin -0.3in
\topmargin -0.8in
\parskip 0.85ex
\columnsep 0.33in
\sloppy
\raggedbottom

\include{psfig}

\begin{document}

\section{Jacobi Relaxation}

{\em Jacobi relaxation} is an iterative algorithm which, given a set
of boundary conditions, finds (discretized) solutions to differential
equations of the form $\nabla^2 {\cal A} + {\cal B} = 0$. We begin by
choosing the grid which will form the basis of our discretization:

\begin{center}
\mbox{\psfig{width=4.40in,height=1.42in,figure=grid.psi}}
\end{center}

To find a solution on a grid, we repeatedly apply the following
iterative step until we converge on a solution. 
\begin{equation}
\label{eq:relax}
A_{\rm i,\, j}^{k+1} = \frac{ A_{\rm i+1,\, j}^{k} + A_{\rm i-1,\, j}^{k} +
A_{\rm i,\, j+1}^{k} + A_{\rm i,\, j-1}^{k} }{4} + b_{\rm i,\, j}
\end{equation}

Jacobi differs from other iterative relaxation algorithms in that the
update of each point (at iteration step $k+1$) requires the {\it
previous} values of the neighboring points (from iteration step $k$).

We use a simple graphical representation to capture those features we
are interested in and abstract away excess detail. In this
representation, graph nodes represent fixed amounts of computation;
graph edges represent communication between computation nodes. In such
a representation, a single iteration of Jacobi relaxation looks as
follows:

\begin{center}
\mbox{\psfig{width=4.16in,height=1.51in,figure=jacobi.psi}}
\end{center}

In this graph, each node represents the computation required to
compute a new value for a single grid point. To compute a new value
for a grid point, Jacobi relaxation dictates that we average the
previous values of each of the neighboring grid points -- thus each
node is connected to its four neighboring nodes with an edge that
represents the communication of two grid values (one in each
direction).

The following figure shows one step of a relaxation on a four by four
grid.  The $A^k$ matrix contains the values of the grid at step $k$,
and the $A^{k+1}$ matrix has the values for the next step.  The
boundary conditions are shown on the edges of the $A^k$ and $A^{k+1}$
matrices.  The $B$ matrix, which is constant, contains the values that
are added to the grid points on each step according to
Equation~\ref{eq:relax}.

\begin{center}
\mbox{\psfig{width=3.5in,figure=numbergrid.psi}}
\end{center}

You might want to think about the values in the $A^{k+2}$ matrix after
the next relaxation step.

%7 4 4 4
%6 1 3 3
%6 5 0 5
%6 2 1 6

There are a number of ways to partition the data in this grid to a
bunch of processors.  Figure~\ref{values-arrow} shows two possible
ways to partition the four by four grid to four processors.  One
partition allocates one row of the matrix to each processor, and the
other allocates a two by two submesh of the matrix to each processor.
For every step in the relaxation, {\it each processor will calculate
the new values for its own matrix cells.} To accomplish this
calculation, the processors need to get cell values from neighboring
processors.  The values on the arrows between the nodes represent the
data that must be communicated between processors.

\begin{figure}[htbp]
\centerline{\psfig{figure=numberpart.psi,width=4.16in}}
\caption{Partitioning by rows and by square tiles.}
\label{values-arrow}
\end{figure}

\end{document}
