Graph Partitioning Using Separators

Partitioning of Sparse Matrix-Vector Multiplication

In general, the sparse matrix-vector multiplications used in scientific computing can have millions of variables, which is far more than the number of processors in current parallel machines. Therefore we partition the problem into subproblems and map the subproblems to the available processors, while allowing for the necessary communication between subproblems.

The most natural way to partition a graph G is to remove some subset of its edges, leaving some connected components of vertices remaining. These connected components are assigned to processors. This is called vertex partitioning, because each vertex is assigned to a single processor.

Current finite element implementations suggest a different partitioning approach. A finite element mesh is a partitioning of space into elements. An element is a polygon (usually a triangle or rectangle) in two dimensions, or a polytope (usually a tetrahedron or rectangular prism) in three dimensions. The mesh is made up of nodes connected by edges (faces in 3D). Physical quantities are associated with each node (for instance, the vector x, whose length n is the number of nodes in the mesh, might specify the displacement of each node.) Nodes within a single element have a direct physical effect on each other; thus, A_{ij} is nonzero if and only if nodes i and j are in some common element e.

Given a finite element mesh M, the corresponding graph G is generated by creating one vertex in G for each node in M, and adding an edge to G for each pair of nodes which share a common element. Thus, if M is composed of triangular elements, G will be identical to M. If M is composed of square elements, G will be similar to M, but with the addition of edges between

It is possible to partition the graph by cutting between elements and putting copies of the nodes and edges along the cut in both bordering blocks of the partition, so as to keep entire elements on single processors. This will allow the computation of matrix entries to be performed locally, and although it will require some extra memory, the borders of the partition blocks will be shown to be small so this is not a problem. In this case, the multiple copies of a node will each be able to collect some partial sum of their entry in the product, and only these partial sums need to be communicated. Therefore for this partitioning scheme, the communication is between the multiple copies of each node, rather than between neighboring nodes.

In order to get an efficient implementation there are two measures we must keep in mind. First, we must keep the sizes of the partition blocks relatively balanced — note that for this problem, the amount of local work done on a processor is the number of edges contained in its partition block, not the number of vertices. Second, we want to keep the boundaries of the partition blocks as small as possible, as this corresponds to the amount of interprocessor communication we must perform. In the next subsection we will discuss how graph separators allow us to satisfy both of these concerns.

If we have partitioned 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 supervertex for each block of the partition, and an edge between two supervertices if their corresponding blocks need to communicate with each other (i.e., they either have a cut edge between them or contain copies of the same vertex, depending on the partitioning approach). The weight on a edge is the number of values which must be communicated between those two subproblems in order to perform a multiplication. This weighted minor on the p supervertices is what we must place and route on the target machine.

Implementation of Separators in Two and Three Dimensions

Miller, Teng, Thurston and Vavasis [?] 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 or duplicated nodes (corresponding to data which must be routed), depending on the method of partitioning. This approach to graph partitioning has been implemented in MATLAB.

We have implemented the random linear time separator algorithm of Miller et al. [?]. The input to the algorithm is a finite element mesh (or graph embedded in two or three dimensions), given as a pair (A, xyz), where A describes the combinatorial structure of the mesh and xyz gives the geometric information. For a finite element mesh, A could be the list of elements of the mesh, where each element is given by the information describing the hierarchical structure of the elements – its lower dimensional structures such as its faces, edges, and vertices. Moreover, each vertex has geometric coordinates in two or three dimensions given by xyz.

The detailed description the mesh partitioning algorithm can be found in [?]. The following is an outline of the basic steps. Algorithm (Partitioning Finite Element Meshes) Input: A, xyz in IR^{d}.

Choose a random sample P of constant size^{1}

See ?? for the theoretical justification.

According to our experiments, 400 to 800 points