Metis

Build Status

Metis.jl is a Julia wrapper to the Metis library which is a library for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices.

Graph partitioning

Metis.partition calculates graph partitions. As an example, here we partition a small graph into two, three and four parts, and visualize the result:

Metis.partition(g, 2)	Metis.partition(g, 3)	Metis.partition(g, 4)

Metis.partition calls METIS_PartGraphKway or METIS_PartGraphRecursive from the Metis C API, depending on the optional keyword argument alg:

• alg = :KWAY: multilevel k-way partitioning (METIS_PartGraphKway).
• alg = :RECURSIVE: multilevel recursive bisection (METIS_PartGraphRecursive).

Vertex separator

Metis.separator calculates a vertex separator of a graph. Metis.separator calls METIS_ComputeVertexSeparator from the Metis C API. As an example, here we calculate a vertex separator (green) of a small graph:

Metis.separator(g)

Fill reducing permutation

Metis.permutation calculates the fill reducing permutation for a sparse matrices. Metis.permutation calls METIS_NodeND from the Metis C API. As an example, we calculate the fill reducing permutation for a sparse matrix S originating from a typical (small) FEM problem, and visualize the sparsity pattern for the original matrix and the permuted matrix:

perm, iperm = Metis.permutation(S)

⠛⣤⢠⠄⠀⣌⠃⢠⠀⠐⠈⠀⠀⠀⠀⠉⠃⠀⠀⠀⠀⠀⠀⠀⠀⠘⠀⠂⠔⠀ ⠀⠖⠻⣦⡅⠘⡁⠀⠀⠀⠀⠐⠀⠁⠀⢂⠀⠀⠠⠀⠀⠀⠁⢀⠀⢀⠀⠀⠄⢣ ⡀⢤⣁⠉⠛⣤⡡⢀⠀⠂⠂⠀⠂⠃⢰⣀⠀⠔⠀⠀⠀⠀⠀⠀⠀⠀⠀⠄⠄⠀ ⠉⣀⠁⠈⠁⢊⠱⢆⡰⠀⠈⠀⠀⠀⠀⢈⠉⡂⠀⠐⢀⡞⠐⠂⠀⠄⡀⠠⠂⠀ ⢀⠀⠀⠀⠠⠀⠐⠊⠛⣤⡔⠘⠰⠒⠠⠀⡈⠀⠀⠀⠉⠉⠘⠂⠀⠀⠀⡐⢈⠀ ⠂⠀⢀⠀⠈⠀⠂⠀⣐⠉⢑⣴⡉⡈⠁⡂⠒⠀⠁⢠⡄⠀⠐⠀⠠⠄⠀⠁⢀⡀ ⠀⠀⠄⠀⠬⠀⠀⠀⢰⠂⡃⠨⣿⣿⡕⠂⠀⠨⠌⠈⠆⠀⠄⡀⠑⠀⠀⠘⠀⠀ ⡄⠀⠠⢀⠐⢲⡀⢀⠀⠂⠡⠠⠱⠉⢱⢖⡀⠀⡈⠃⠀⠀⠀⢁⠄⢀⣐⠢⠀⠀ ⠉⠀⠀⠀⢀⠄⠣⠠⠂⠈⠘⠀⡀⡀⠀⠈⠱⢆⣰⠠⠰⠐⠐⢀⠀⢀⢀⠀⠌⠀ ⠀⠀⠀⠂⠀⠀⢀⠀⠀⠀⠁⣀⡂⠁⠦⠈⠐⡚⠱⢆⢀⢀⠡⠌⡀⡈⠸⠁⠂⠀ ⠀⠀⠀⠀⠀⠀⣠⠴⡇⠀⠀⠉⠈⠁⠀⠀⢐⠂⠀⢐⣻⣾⠡⠀⠈⠀⠄⠀⡉⠄ ⠀⠀⠁⢀⠀⠀⠰⠀⠲⠀⠐⠀⠀⠡⠄⢀⠐⢀⡁⠆⠁⠂⠱⢆⡀⣀⠠⠁⠉⠇ ⣀⠀⠀⢀⠀⠀⠀⠄⠀⠀⠀⠆⠑⠀⠀⢁⠀⢀⡀⠨⠂⠀⠀⢨⠿⢇⠀⡸⠀⢀ ⠠⠀⠀⠀⠀⠄⠀⡈⢀⠠⠄⠀⣀⠀⠰⡘⠀⠐⠖⠂⠀⠁⠄⠂⣀⡠⠻⢆⠄⠃ ⠐⠁⠤⣁⠀⠁⠈⠀⠂⠐⠀⠰⠀⠀⠀⠀⠂⠁⠈⠀⠃⠌⠧⠄⠀⢀⠤⠁⠱⢆

⣕⢝⠀⠀⢸⠔⡵⢊⡀⠂⠀⠀⠄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣑⠑ ⠀⠀⠑⢄⠀⠳⠡⢡⣒⣃⢣⠯⠆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠌ ⢒⠖⢤⡀⠑⢄⢶⡈⣂⠎⢎⠉⠩⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⡱⢋⠅⣂⡘⠳⠻⢆⡥⣈⠆⡨⡩⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀ ⠠⠈⠼⢸⡨⠜⡁⢫⣻⢞⢔⠀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠠ ⠀⠀⡭⡖⡎⠑⡈⡡⠐⠑⠵⣧⣜⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀ ⠀⠁⠈⠁⠃⠂⠃⠊⠀⠘⠒⠙⠛⢄⠀⠀⢄⠀⠤⢠⠀⢄⢀⢀⠀⡀⠀⠀⢄⢄ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠑⢄⠊⠀⣂⠅⢓⣤⡄⠢⠠⠀⠌⠉⢀⢁ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠑⠊⠀⠑⢄⠁⣋⠀⢀⢰⢄⢔⢠⡖⢥⠀⠁ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣃⠌⠜⡥⢠⠛⣤⠐⣂⡀⠀⡀⡁⠍⠤⠒⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢄⠙⣴⠀⢀⠰⢠⠿⣧⡅⠁⠂⢂⠂⠋⢃⢀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢐⠠⡉⠐⢖⠀⠈⠅⠉⢕⢕⠝⠘⡒⠠⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⠂⠐⣑⠄⠨⠨⢀⣓⠁⣕⢝⡥⢉⠁⠠ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡆⠁⠜⣍⠃⡅⡬⠀⠘⡈⡅⢋⠛⣤⡅⠒ ⢕⠘⡂⠄⠀⠀⠁⠀⠀⡂⠀⢠⠀⢕⠄⢐⠄⠀⠘⠀⠉⢐⠀⠀⠁⡀⢡⠉⢟⣵

S (5% stored values)

S[perm,perm] (5% stored values)

We can also visualize the sparsity pattern of the Cholesky factorization of the same matrix. It is here clear that using the fill reducing permutation results in a sparser factorization:

⠙⢤⢠⡄⠀⣜⠃⢠⠀⠐⠘⠀⠀⠀⠀⠛⠃⠀⠀⠀⠀⠀⠀⠀⠀⠘⠀⠂⡔⠀ ⠀⠀⠙⢦⡇⠾⡃⠰⠀⠀⠀⠐⠀⠃⠀⢂⠀⠀⠠⠀⠀⠀⠃⢀⠀⢀⠀⠀⠆⢣ ⠀⠀⠀⠀⠙⢼⣣⢠⠀⣂⣂⢘⡂⡃⢰⣋⡀⣔⢠⠀⠀⠀⡃⠈⠀⢈⠀⡄⣄⡋ ⠀⠀⠀⠀⠀⠀⠑⢖⡰⠉⠉⠈⠁⠁⢘⢙⠉⡊⢐⢐⢀⣞⠱⠎⠀⠌⡀⡣⡊⠉ ⠀⠀⠀⠀⠀⠀⠀⠀⠙⢤⣴⢸⣴⡖⢠⣤⡜⢣⠀⠀⠛⠛⡜⠂⠀⢢⠀⡔⢸⡄ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢼⣛⣛⣛⣛⣓⣚⡃⢠⣖⣒⣓⢐⢠⣜⠀⡃⢘⣓ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿⣿⣿⣿⢸⣿⣿⣿⣾⣿⣿⠀⣿⢸⣿ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣒⣿⣺⣿ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣤⣿⣼⣿ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿⣿⣿⣿⣿⣿⣿ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿⣿⣿⣿⣿ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿⣿⣿ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿

⠑⢝⠀⠀⢸⠔⡵⢊⡀⡂⠀⠀⠄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣕⢕ ⠀⠀⠑⢄⠀⠳⠡⢡⣒⣃⢣⠯⠆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠌ ⠀⠀⠀⠀⠑⢄⢶⡘⣂⡎⢎⡭⠯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠶⠴ ⠀⠀⠀⠀⠀⠀⠙⢎⣷⣏⢷⣯⡫⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠛⡛ ⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⢼⣧⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠤⡤ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠑⢿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣭⣯ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢄⠀⠀⢄⠀⠤⢠⠀⢄⢀⢀⠀⡀⠀⠀⢟⢟ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠑⢄⠊⠀⣂⠅⢓⣤⡄⠢⠠⠀⠌⠉⢀⢁ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠑⢄⠉⣋⠀⢁⢰⢔⢔⢠⡖⢥⠁⠃ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢤⠘⣶⡂⠠⡀⣡⠭⣤⢓⢗ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢷⡇⡇⣢⣢⠂⣯⣷⣶ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠑⢕⢟⢝⣒⠭⠭⡭ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠑⢝⣿⣿⡭⡯ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿

chol(S) (16% stored values)

chol(S[perm,perm]) (6% stored values)

Direct access to the Metis C API

For more fine tuned usage of Metis consider calling the C API directly. The following functions are currently exposed:

• METIS_PartGraphRecursive
• METIS_PartGraphKway
• METIS_ComputeVertexSeparator
• METIS_NodeND

all with the same arguments and argument order as described in the Metis manual.