METIS: graph partitioning and fill reducing ordering for sparse solvers

Three jobs built on one multilevel partitioning core

METIS is a set of serial programs that do three related things. They partition graphs, they partition finite element meshes, and they produce fill reducing orderings for sparse matrices. The underlying algorithms are the multilevel recursive-bisection, multilevel k-way and multi-constraint partitioning schemes developed in the authors' lab, which is the phrase that tells you the intellectual core. All three capabilities descend from the same partitioning machinery, so a library that solves the mesh partitioning problem also solves the graph problem that the mesh problem reduces to, and the ordering problem that a sparse solver needs.

The repository layout maps onto that structure. The library itself is in libmetis/, the public header and the include/ directory hold the API, programs/ holds the command line tools, the manual/ directory holds the documentation, and test/ plus graphs/ and utils/ hold the test material and helper utilities. There is a perf/ directory, a PERF-REVIEW.md file at the root and a Changelog file, which is a good sign about how performance work is tracked. The version in the Makefile is 5.1.0, and the package name built from it is metis-5.1.0. The copyright notice runs from 1998 to 2020 and belongs to the Regents of the University of Minnesota, and the README states the licence is the Apache License, Version 2.0, although the repository listing records a licence that GitHub could not classify, so the LICENSE file is the place to read the authoritative terms. The repository carries a CLAUDE.md file, a BUILD-Windows.txt file and a vsgen.bat script for Visual Studio users, so a Windows build path is provided even though the documented flow is Unix oriented.

Cloning, then installing GKlib before METIS

Getting the source is a single clone.

git clone https://github.com/KarypisLab/METIS.git

The build, however, has a dependency that catches people out. METIS depends on GKlib, a separate library that has to be downloaded and installed first by following the instructions in its own repository, and the METIS build then has to be told where GKlib landed. The general build dependencies are gcc, cmake and build-essential, and the README gives the apt command for the Ubuntu case.

sudo apt-get install build-essential
sudo apt-get install cmake

Once GKlib is installed, the build is driven by make config, which takes options as arguments rather than through a separate configuration file. The example given builds a shared library with GCC and installs into a prefix under your home directory.

make config shared=1 cc=gcc prefix=~/local
make install

That installs the binaries, the header files and the libraries into ~/local/bin, ~/local/include and ~/local/lib respectively. The gklib_path option takes the installation prefix where GKlib was installed, and the README is careful about a detail that trips up people, which is that you pass the prefix itself, not ~/local/lib or ~/local/lib64. You can skip it entirely if the two prefixes happen to be the same. The Makefile is mostly a thin proxy for the CMake build in the build directory, translating each make option into a CMake flag, and the CMAKE_VERBOSE_MAKEFILE option is on so you can see what is actually invoked.

Configuration options that change the numeric width and the build

Two of the make options matter for anyone with a large problem, and they are the ones to decide before building. The i64=1 option sets the width of the datatype storing information about vertices and their adjacency lists to 64 bits, and the r64=1 option does the same for floating point numbers. The default is 32 bits for both, and the Makefile shows the mechanism, writing an IDXTYPEWIDTH and a REALTYPEWIDTH define into a generated metis.h in the build directory. Graph partitioning problems blow past the 32 bit limit sooner than you would expect, and a partitioner that silently refuses your graph because the vertex count overflows an index is a bad afternoon. The second group of options is about build quality. gdb=1 builds with GDB support, debug=1 enables debugging support, assert=1 enables asserts and assert2=1 enables what the README calls very expensive asserts. There are also gprof=1, valgrind=1 and openmp=1 in the Makefile for profiling, memory checking and threading, and the openmp option is worth a note because the programs are described as serial, so OpenMP is an opt-in experiment rather than the default mode.

The housekeeping targets are the usual set. make uninstall removes everything that make install put in place, make clean removes the object files while keeping the configuration options, and make distclean removes the build directory completely, which is what you want when changing a configuration option that affects the generated header.

The performance review file is part of the repository

What is unusual here, and worth a look before you evaluate the library, is that the repository contains a PERF-REVIEW.md file and a perf/ directory, alongside a Changelog. For a library whose copyright dates from 1998, a performance review document checked into the same tree as the code is a signal about how the maintainers think about the hot path. The partitioning algorithms are the kind where constant factors and the quality of the multilevel coarsening decide whether a solve finishes tonight or next week, so a per-partition performance review that lives next to the source is a reasonable thing to expect from the people who wrote the original papers on multilevel schemes.

The other thing to weigh is what METIS is not. The description says serial programs, and the Makefile's openmp option being off by default confirms that. So METIS is a library for the partitioner and the ordering, and if your actual need is a parallel graph processing framework for very large graphs, this is the wrong category of tool. The same applies to the ordering problem. METIS produces fill reducing orderings for sparse matrices, and it is designed to be used by a direct sparse solver, so on its own it does not factor anything. It reduces the fill that a solver will incur, and the solver remains your responsibility. The practical benefit is large, because fill in a sparse factorization is what determines the memory and the time of the solve, but the cost of a bad ordering is something METIS cannot absorb for you.

Where METIS is the wrong tool

Three cases stand out. The first is a parallel or very large scale graph workload. The programs are serial, and although a partition of a graph with hundreds of millions of edges is conceivable with the 64 bit index option, the partitioning itself is single threaded work, and a distributed graph framework is the tool for that scale. The second is a team that needs a maintained package. There are no GitHub releases, the version lives in the Makefile, the build requires you to install GKlib separately, and the documented flow is a source build with a make config step. That is entirely reasonable for a research library and its dependents, such as finite element and sparse solver codes, but a team that expects apt or conda packages and a semantic versioned release stream will find this friction. The third is a project that needs graph algorithms rather than partitioning. METIS partitions and reorders. It does not give you a general graph library, so if your problem is traversal, centrality or community detection, a dedicated graph library is the right shape of dependency. On the licence, the README describes the terms as the Apache License, Version 2.0, which is permissive but still requires keeping the licence and copyright notices, and the copyright sits with the Regents of the University of Minnesota, so commercial use is not a question you need to answer before evaluating the algorithms. The one caveat is that the repository listing classifies the licence as one GitHub could not categorise, so read the LICENSE file rather than relying on a summary. The practical point about maintenance is that the last push was on 2026-06-10, which is recent enough that the tree is not abandoned, but the absence of tagged releases means you should record the commit you built.

Editorial conclusion

METIS suits a numerical computing team that needs a high quality graph partition for a domain decomposition solver, or a fill reducing ordering for a sparse direct solver, and that is willing to build a C library and its GKlib dependency from source. It does not suit a project needing parallel graph processing, since the programs are explicitly serial, and it does not suit a team that needs a maintained package rather than a source build. Before you start, install GKlib and set gklib_path to its prefix, decide whether you need 64 bit indices with i64=1, and check the Changelog and the PERF-REVIEW.md file, since the repository has no GitHub releases and the last push was on 2026-06-10.

Frequently asked questions

Official sources

1. Issues
2. KarypisLab/METIS on GitHub
3. README