METIS is a software package for graph partitioning that implements various multilevel algorithms. METIS' multilevel approach has three phases and comes with several algorithms for each phase: 1. \n* Coarsen the graph by generating a sequence of graphs G0, G1, ..., GN, where G0 is the original graph and for each 0 ≤ i ≤ j ≤ N, the number of vertices in Gi is greater than the number of vertices in Gj. 2. \n* Compute a partition of GN 3. \n* Project the partition back through the sequence in the order of GN, ..., G0, refining it with respect to each graph.