GetWiki

{{primary sources|date=August 2022}}{{Distinguish|Metis (disambiguation){{!}}metis}}METIS is a software package for graph partitioning that implements various multilevel algorithms.TECH REPORT, George Karypis, Vipin Kumar, amp, METIS - Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0, 1995,weblink {{dead link|date=January 2018 |bot=InternetArchiveBot |fix-attempted=yes }}JOURNAL, A fast and high quality multilevel scheme for partitioning irregular graphs, Karypis, G., Kumar, V., amp, SIAM Journal on Scientific Computing, 20, 1, 359, 1999, 10.1137/S1064827595287997, 10.1.1.39.3415, 3628209, METIS' multilevel approach has three phases and comes with several algorithms for each phase:

1. 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. Compute a partition of GN
3. Project the partition back through the sequence in the order of GN, ..., G0, refining it with respect to each graph.

The final partition computed during the third phase (the refined partition projected onto G0) is a partition of the original graph. According to Metis authors Karypis and Kumar, "Metis is the Greek word for wisdom. Metis was a titaness in Greek mythology. She was the consort of Zeus and the mother of Athena. She presided over all wisdom and knowledge".REPORT,weblink METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices, Karypis, George, Kumar, Vipin, 1997, en-US,

References

{{Reflist}}

External links

• METIS website

{{algorithm-stub}}