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

The problem of multiplying a large sparse matrix by a vector is ubiquitous in
scientific computation.  Together with inner products and elementwise vector
operations (e.g., addition, multiplication by scalars), it is one of the basic
primitives used in iterative numerical methods, and is among the most
communication-intensive.  For example, 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 (and some simpler elementwise operations).  It is important to
note at this point that although the nonzero entries of the matrix may change
for nonlinear problems, the nonzero structure of the matrix is fixed.

We now consider the communication requirements for calculating the product $y$
of a sparse $n \times n$ matrix $A$ and an $n$-element vector $x$.  Assume
that there are $n$ processors, and each processor $i$ stores a single element
$x_i$ of the vector.  In order to calculate $y_i$, processor $i$ must receive
the values $x_j$ from each processor $j$ such that $A_{ij} \neq 0$.  The value
$x_j$ must be multiplied by $A_{ij}$, which can be thought of as an edge
weight, at either the source or the destination.  Thus the set of routing
paths which we must implement on the network of processors includes an edge
from processor $j$ to processor $i$ whenever $A_{ij} \neq 0$. Since in our
application areas the nonzero structure of $A$ is typically symmetric (even if
$A$ is asymmetric), this set of routing paths is
just the undirected graph on $n$ vertices
whose adjacency matrix is $A$. We will refer to this graph as $G$. This
reduces the problem of calculating the product of a sparse matrix and a vector
to that of exchanging data across all edges of $G$.

Given $G$, the problem of performing an inner product $x \cdot y$ is
relatively simple, because each processor $i$ holds the values of both $x_i$
and $y_i$.  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 $G$. Elementwise operations on the
vectors require no communication, but distribution of scalars for
scalar-vector multiplication will require a broadcast, which can use the same
spanning tree.  These two primitives, data exchange and
accumulation/broadcast, are sufficient to implement most iterative methods.
Since the data exchange graph contains the spanning tree for the
accumulation/broadcast operation, we need only consider the implementation of
the communication needed for the sparse matrix-vector multiplication.

