Snapshots of Mobile Jacobi

Alan Edelman* Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139 and Thinking Machines Corporation 245 First St. Cambridge, MA 02142

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.) 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 [5]. 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.

Key words and phrases: eigenvalues, graphics, Jacobi ∗Supported by Thinking Machines Corp. and a Hertz Foundation Fellowship

The inner loop of the algorithm is as follows:

1. Compute rotations based on {a_{ii}, a_{i+1,i+1}, a_{i,i+1}} for i odd.

2. Apply rotations and permute the pairs of rows and the pairs of columns i and i + 1.

3. Repeat steps 1 and 2 for i even.

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 [3]. 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,∞) 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×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 [1]. 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.

References

[1] M. Berry and A. Sameh, Parallel algorithms for the singular value and dense symmetric eigenvalue problems JCAM, to appear.

[2] R.P. Brent and F.T. Luk, The solution of singular-value and symmetric eigenvalue problems on multiprocessor arrays, SIAM J. Sci. Stat. Comput. 6 (1985), 69–84.

[3] L.M. Ewerbring, F.T. Luk, and A.H. Ruttenberg, Matrix computations on the Connection Machine, Twenty First Asilomar Conference on Signals, Systems, and Computers.

[4] G.H. Golub and C.F. Van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore, 1983.

[5] J. Modi and J.D. Price, Efficient implementation of Jacobi’s diagonalization method on the DAP, Numerische Mathematik 46 (1985), 443– 454.