Previous | Next --- Slide 28 of 58
Back to Lecture Thumbnails
zhanpenf

Besides ParMETIS for partitioning meshes, METIS is also a great tool for partitioning general graphs. The general idea for "METIS" algorithm is that first use random matching algorithm to collapse nodes to coarsen the graph. Second, compute initial partition on the coarse graph, and this computation is fast due to the size of the coarse graph. Finally, uncoarsen the partition and project it back to the original graph. Further details of the algorithm can refer to the following papers:

http://glaros.dtc.umn.edu/gkhome/metis/parmetis/publications