Algorithms that find a good partition of highly unstructured graphs are critical for developing efficient solutions for a wide range of problems in many application areas on both serial and parallel computers. For example, large-scale numerical simulations on parallel computers, such as those based on finite element methods, require the distribution of the finite element mesh to the processors. This distribution must be done so that both the number of elements assigned to each processor is the same and the number of elements adjacent to elements assigned to different processors is minimized. The goal of the first condition is to balance the computations among the processors. The goal of the second condition is to minimize the communication between adjacent elements residing on different processors. Graph partitioning is also used for computing fill-reducing ordering of sparse matrices as well as for solving optimization problems arising in numerous areas such as design of VLSI circuits, storing and accessing spatial databases on disks, and transportation management
You stand at your back door and think, "That old garage isn't going to hold up under many more Minnesota thunderstorms. I'd be better off tearing it down and building a new one." You don't have a lot of money, so you decide to be your own general contractor. There is a lot of work ahead. You will look up electricians, masons, roofers, and garage door companies. You will make a lot of calls and try to get estimates of what can be done when and for how much. Then you have to figure out which companies to choose so that the project runs smoothly and under budget. Paying a general contractor is starting to look pretty good!
METIS
METIS is a family of software packages for partitioning large irregular graphs, computing fill-reducing orderings of sparse matrices, and for partitioning large hypergraphs. The algorithms in METIS are based on the multilevel graph partitioning paradigm. Traditional graph partitioning algorithms compute a partition of a graph by operating directly on the original graph and are often too slow and/or provide poor quality partitions. Multilevel partitioning algorithms, on the other hand, take a completely different approach. These algorithms reduce the size of the graph by collapsing vertices and edges, partition the smaller graph, and then use this partitioning to construct a high-quality partition for the original graph.
The METIS family of multilevel algorithms consists of three different packages: METIS, ParMETIS, and hMETIS. METIS has been designed to partition very large unstructured graphs on serial computers. ParMETIS is a highly parallel implementation of the serial algorithms in METIS and can scale to thousands of processors and is used routinely to partition graphs with over a billion vertices. hMETIS is suited for partitioning large unstructured hypergraphs and is the state-of-the-art partitioning tool for very large circuits. METIS and hMETIS were written by Professor George Karypis, and ParMETIS was written by Professor George Karypis and Dr. Kirk Schloegel.
The entire METIS family of algorithms is freely available on the web http://www.cs.umn.edu/~karypis/metis. Since their introduction, they have been used extensively by many government, educational, and commercial organizations. Over fifty companies including SUN, Intel, Microsoft, Synopsys, Boeing, Hitachi, NEC, and Motorola have licensed and use METIS in their commercial and internal applications. Moreover, METIS and ParMETIS are critical tools for enabling the solution of very large numerical simulations that take place in the context of the Accelerate Strategic Computing Initiative (ASCI) program in the Department of Energy and the Common High Performance Computing Software Support Initiative (CHSSI) projects of the Department of Defense.
-George Karypis