Metis.jl
Metis.jl copied to clipboard
JuliaSparse
Julia interface to Metis graph partitioning
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_PartGraphRecursiveMETIS_PartGraphKwayMETIS_ComputeVertexSeparatorMETIS_NodeND
all with the same arguments and argument order as described in the Metis manual.
JuliaSparse