\section{A Combinatorial Graph Representation of 
\newline Sparse Matrix-Vector Multiplication}


The basic iterative step of the conjugate-gradient method for
finite-element calculations consists of several inner-product
calculations followed by one multiplication of a sparse matrix by
a vector.  It is important to note at this point that although the
non-zero entries of the matrix
may change from iteration to iteration, the non-zero
structure of the matrix is fixed.

We now consider the communications requirements for calculating the
product $y$ of a
sparse symmetric $n \times n$ matrix $A$ and an $n$-element vector $x$.  
Suppose that each of $n$ processor 
stores a single
element of the vector.  In order to calculate $y_i$, the processor holding 
$x_i$ must receive from other processors
the values $x_j$ for all $j$ such that $A_{ij} \neq 0$.
Thus the resulting communication graph which we must implement on the
processors includes a bidirectional edges between processors $i$ and $j$
whenever $A_{ij} \neq 0$.  This is just the combinatorial graph on $n$
nodes whose adjacency matrix is the matrix $A$.  This reduces the problem
of calculating the product of a sparse matrix and a vector to that of
exchanging data across each edge of an combinatorial graph.

Given this graph, the problem of performing an inner product is relatively
simple, assuming that the processor containing each $x_i$ also contains
the $i$th element of the other factor in the inner product.  Then all that
is required is for the $i$th processor to calculate $x_i y_i$, and then
for the resulting values to be accumulated over the $n$ processors using
a spanning tree in the (presumably connected) graph just described.  These
two primitives, data exchange and accumulation/broadcast, 
are sufficient to implement
a parallel conjugate-gradient method.

