Before a computation can be performed on a multiprocessor, it must first be partitioned into parts that are assigned to different processors. Efficiency requires that each processor have about the same amount of work to do (load balancing) and that the quantity of interprocessor communication be kept small. For example, in the solution of Parallel Differential Equations (PDEs) on parallel computers, a physical domain is typically partitioned into several sub-domains, and a global solution is recovered from the solutions of independent subproblems associated with the subdomains. The discretization of a PDE problem typically leads to a sparse linear system. Sparse linear systems may also arise from applications other than PDEs, such as electrical networks or queueing models. The dependencies between the unknowns in this system may be conveniently represented by a graph. The graph may be partitioned and the subgraphs assigned to processors so as to take advantage of coarse-grained parallelism during the solution procedure, with the goal being to achieve good load balancing while minimizing communication. Thus, graph or mesh partitioning is an important preprocessing steps for the parallel solution of PDEs and sparse linear systems.

- Geometry Center, University of Minnesota
- SUMMA3D Project, University of Tennessee and Argonne National Lab

hpc-netlib@netlib.org