\section{Graph Partitioning Using Separators}

In general, finite-element calculations can have
tens of thousands or even hundreds of thousands 
of variables, which is more
than the number of processors in current parallel machines.  Therefore
we must partition the problem, and map the subproblems to the available
processors.  In effect, we partition the associated combinatorial
graph into subgraphs, so that communication across edges within the blocks
of the partition takes place locally while communication across edges
which cross between partition blocks requires communication between processors.
Thus when we partition the graph we wish to keep the
boundaries of the blocks of the partition as small as possible, 
as this corresponds to the amount of communication we must perform,
as well as keeping the sizes of the partition blocks relatively balanced.

Miller, Teng, Thurston and Vavasis \cite{MTTV} give provably
good separators in two or three dimensions for the sort of combinatorial
graphs generated by these problems.  These separators can be used recursively
to obtain a partition of the graph with both good balance among block sizes
(corresponding to processor load)
and a relatively small number of cut edges (corresponding to data which must
be routed).  This approach to graph partitioning has been implemented in
MATLAB.

If we have partition the original graph into $p$ blocks, where $p$ is
the number of available processors, then we can
define the $p$-node minor derived from the original
graph and the partition.  The minor is a weighted graph with a supernode 
for each block of
the partition, and an edge between two super 
nodes if their corresponding blocks
have a cut edge from some separator between them.  The weight on a edge
is the number of original edges between the corresponding supernodes, 
since this
is the number of values which must be communicated between those two 
subproblems in order to perform a multiplication.  
This weighted graph on the blocks of the partition is what we must
place and route on the target architecture.

