\documentstyle[11pt]{article}
\begin{document}

\renewcommand{\thefootnote}{\alph{footnote}}
\setcounter{footnote}{-10}




\title{Snapshots of Mobile Jacobi}
\author{\sl{Alan Edelman*}
\footnotemark[0]
\\ Department of Mathematics \\
Massachusetts Institute of Technology \\ Cambridge, MA 02139 \\
and \\
Thinking Machines Corporation \\
245 First St. \\
Cambridge, MA 02142}
\date{}
 
\maketitle
\footnotetext{\\ Key words and phrases: 
eigenvalues,
graphics,
Jacobi
}
\footnotetext{\\ ${}^*$Supported by Thinking Machines Corp.\ and a
Hertz Foundation Fellowship}



We wish to document the short but dramatic life of a special matrix  
undergoing the Jacobi diagonalization procedure to compute its
eigenvalues. The combination of a massively parallel supercomputer
with a real time graphics display allows us to understand 
algorithms in entirely new ways, giving insight that can be surprising
as well as beautiful. In this  note, we would like to give 
one illustration. We regret that the printed medium only allows for
snapshots; the video is far more dramatic.

Jacobi's original method and its 
modification for parallel machines
is carefully explained in
many texts and recent papers on parallel algorithms (for example,
see any of the references.)
%There remains, however, some exciting theoretical issues to be explored.
%Namely, there are no convergence proofs for arbitrary orderings
%and little good understanding as to how different orderings differ.
%Nevertheless, there are no counterexamples to theoretical convergence
%for any ordering,
%if we insist that undefined Jacobi rotations must be zero rotations. 
Here we provide snapshots to illustrate the underlying symmetries
of a particular mobile scheme applied to a particular matrix.

The mobile scheme here is given by \cite{MP}.
The key feature of this scheme is that the rotation parameters
are computed only on the diagonal.  The off diagonal
elements march into the diagonal and are zeroed at the diagonal. 
Visually, this is quite striking.  The elements make
bishops' moves, some towards the main diagonal
and some away.  The latter will bounce off the border and
return towards the main diagonal.
Conceptually, in between each march step a rotation is
computed and  applied. In fact, the march step and the rotation
application occur at the same time; it is a matter of storing
the elements in permuted positions after applying the rotation.

The inner loop of the algorithm is as follows:
\begin{enumerate}
  \item Compute rotations based on $\{a_{ii}, a_{i+1,i+1},
a_{i,i+1}\}$ for $i$ odd.
  \item Apply rotations and permute the pairs of rows and
the pairs of columns $i$ and $i+1$.
  \item Repeat steps 1 and 2 for $i$ even.
\end{enumerate}
For more specific details, please consult the literature.
This scheme allows for only local communication.
The alternating blocks of  white
in figure (c) illustrate the zeros that were introduced on
the super and sub-diagonals.

This scheme was originally implemented on the Connection
Machine by Ewerbring, Luk, and Ruttenberg {\cite{ELR}.
The Connection Machine is a 65,536
processor machine with processors arranged in a hypercube. 
Hypercubes conveniently unfold onto grids and
thus this scheme is possible.  


Here  we document how Jacobi evolves.  
We found it convenient to represent the absolute value
of each
matrix element with one of five  colors depending on which
of the intervals  [0,.1],(.1,.5],(.5,.75],(.75,1],(1,$\infty$) 
the value is found.  The colors are white, purple, black, blue, and orange,
respectively.



We take a very special matrix that is one on upper and lower triangles
and zero on the interior diagonals. 
To be precise, we have a $128 \times 128$ matrix  with fifty
diagonals of ones in each of the triangles.
Thus this is a fairly sparse,
Toeplitz, zero-one matrix. 
Though arbitrary symmetric matrices lead to interesting symmetry patterns,
we feel this special matrix
leads to particularly beautiful patterns.

In (a) the matrix is born; the blue triangles indicate the ones
while the inner band is zero.
In (b) we notice the ones marching checkerboard pattern
toward the diagonal, but no rotations have occurred. Notice the holes
that are left where the ones used to be.  In (c) drama occurs, as the
ones finally clash with the diagonal and 
non-trivial rotations emerge.
Rotations continue with a later stage illustrated in (d).  In (e),
notice the off-diagonal elements dying out and finally in (f) we
have convergence to diagonal.

The quilt patterns seen in (c) manifest themselves in arbitrary
matrices though not as neatly.
A related observation was made by \cite{BS}.
We have also observed that often, though not always, the
largest eigenvalue emerges more rapidly than the smaller ones.
This phenomenon needs to be better understood, but it may point
the way towards faster algorithms.




\def\\{\medskip\noindent\hangindent .3in{}}
\setlength{\baselineskip 12pt}
\frenchspacing
\begin{thebibliography}{99}

\vspace{.1in}

\bibitem{BS}
M.~Berry and A.~Sameh,
Parallel algorithms for the singular value and dense
symmetric eigenvalue problems
{JCAM}, to appear.

\bibitem{BL}
R.P.~Brent and F.T.~Luk, The solution of singular-value
and symmetric eigenvalue problems on multiprocessor
arrays,
{\sl SIAM J.\ Sci.\ Stat.\ Comput.\ 6} (1985), 69--84.

\bibitem{ELR}
L.M.~Ewerbring, F.T.~Luk, and A.H.~Ruttenberg,
Matrix computations on the Connection Machine,
{\sl Twenty First Asilomar Conference on
Signals, Systems, and Computers}.

\bibitem{GVL}
G.H.~Golub and C.F.~ Van Loan,
{\sl Matrix Computations},
The Johns Hopkins University Press, Baltimore, 1983.

\bibitem{MP}
J.~Modi and J.D.~Price,
Efficient implementation of Jacobi's diagonalization
method on the DAP,
{\sl Numerische Mathematik 46} (1985), 443--454.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{thebibliography}
\end{document}
