karypislab / metis Goto Github PK

For such an important value (a sure-fire way to segfault if you get it wrong), it is remarkable how difficult it is to figure out the default value of this parameter in the documentation and even when searching the code.

Hi, since the official website is down (#37), is it possible to upload/tag the old releases in this repo?

Also, there's been quite some changes compared to v5.1.0 (the latest public release before the website was down). Is it possible to make a new release to capture these changes?

Thanks!

cc: @DmitryLyakh for vis

When I run mpmetis on a 4,000,000-element mesh, the function named FindCommonElements() costs about 11% of the total running time:

  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 19.52      0.98     0.98     1510     0.00     0.00  libmetis__Match_SHEM
 18.13      1.89     0.91     1511     0.00     0.00  libmetis__CreateCoarseGraph
 13.15      2.55     0.66        1     0.66     0.66  libmetis__Match_RM
 11.36      3.12     0.57  8000000     0.00     0.00  libmetis__FindCommonElements
  5.58      3.40     0.28        1     0.28     0.85  libmetis__CreateGraphDual

It is called in two loops in CreateGraphDual():

• The only purpose for the first loop is to get the total number of neighbours, i.e. xadj[ne] after L208, which is then used to allocate adjncy in L213.
• The second loop then do the real job, which has already done by the first one.

These two loops could be merged into one, if something supports push_back() like std::vector<int> was introduced.
If so, the total running time might be reduced by about 5%.

In 4.3 Programs, all of the five bookmarks point to the same gpmetis page.
In Page 2, the links of these items in the table of contents have the same problem.

It might be easier for users to report (and possibly fix) typos, if the manual was added to the repo as markdown or plain text files.

Looks like there is a bug in (at least) METIS_PartMeshDual(), leading the epart and npart vectors to contain 1s instead of 0s, with options[METIS_OPTION_NUMBERING] = 0.
When nparts > 1, the vectors actually contain 0s and 1s.

I'm using version 5.1.0, along with Apple clang version 14.0.0.

Is this a normal behaviour ? If yes, I couldn't find it in the manual.

Thanks !

As it is a dependency it would be nice to add the possibility in the CMakeLists.txt to specify the include and library directory for GKlib, for example when using it with VC++.

/METIS/build# cmake ..
CMake Deprecation Warning at CMakeLists.txt:1 (cmake_minimum_required):
Compatibility with CMake < 2.8.12 will be removed from a future version of
CMake.

Update the VERSION argument value or use a ... suffix to tell
CMake that the project does not need compatibility with older versions.

CMake Error at CMakeLists.txt:50 (add_subdirectory):
add_subdirectory given source "build/xinclude" which is not an existing
directory.

-- Configuring incomplete, errors occurred!
See also "/mnt/d/slam14/METIS/build/CMakeFiles/CMakeOutput.log".

Trying to build https://github.com/ceres-solver/ceres-solver without SuiteSparse BUT METIS , I got:

undefined reference to `METIS_NodeND'

Hi there,

I want to use METIS as a baseline in my research project. I would like to know if the partitioning time is the elapsed time or the user time?

Thanks

It seems that the 5.1.1 release has memory related issues as mentioned in #20, but which also appear to be the cause of the segmentation faults which are preventing the new release of this framework being packaged for conda-forge: conda-forge/metis-feedstock#30

For the segmentation faults at least, it seems like the 38a8fb0 and 36262ad commits resolve the issues.

@karypis would you be able to create a new tag for a 5.1.2 release (similar as was done for #13) to include the latest commits so we can proceed with the conda-forge packaging? It would be very much appreciated!

Similarly adding new tags for GKlib would also be great (especially as this is now an external dependency) as this would allow us to also package the latest release: conda-forge/staged-recipes#12547

Thanks for your help, and this fantastic framework!

Hello, I have a question about aggregation using Metis in AMG (algebraic multigrid) and want to discuss it with you
Due to the limited number of split subgraphs imposed by metis, when the fine grid matrix is large enough, Metis cannot aggregate enough coarse nodes (for example, there are one million nodes in the fine grid layer, where each two nodes aggregate into points on the next grid layer, which will result in about 500,000 aggregations, and Metis cannot split a graph of this size).
Do you have any good suggestions for this situation?
I look forward to receiving your reply, and I will benefit from any help you give me.

Thanks for creating this repository.

Before this, people from PETSc project maintained their own in https://bitbucket.org/petsc/pkg-metis/. We should review the changes they made and incorporate them here.

cc @prj- @balay @dalcinl

Running these commands:

mkdir INSTALL
VERSION_METIS=5.2.1
curl --retry 5 -fSsL "https://github.com/KarypisLab/METIS/archive/refs/tags/v${VERSION_METIS}.tar.gz" | tar xz
cd METIS-5.2.1
git clone [email protected]:KarypisLab/GKlib.git GKlib                    # Since we don't have a real release.
make config shared=1 prefix=$(realpath ../INSTALL)  gklib_path=$PWD/GKlib
make install                                                           # Evidently gklib_path gets ignored.

gives this error

In file included from /home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.selene/Temp/FOO/METIS-5.2.1/libmetis/auxapi.c:12:0:
/home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.selene/Temp/FOO/METIS-5.2.1/libmetis/metislib.h:17:10: fatal error: GKlib.h: No such file or directory
 #include <GKlib.h>
          ^~~~~~~~~
compilation terminated.
libmetis/CMakeFiles/metis.dir/build.make:78: recipe for target 'libmetis/CMakeFiles/metis.dir/auxapi.c.o' failed
make[3]: *** [libmetis/CMakeFiles/metis.dir/auxapi.c.o] Error 1

Currently the CMake build system is hidden by a Makefile and it cannot be used directly. This makes it difficult to use all the parameters CMake offers like compiler, flags, out-of-surce-build, generator (Ninja instead of make).
I'd like to see CMake becoming a first class citizen. The Makefile might stay as an alternative way to use CMake.

Would you accept according patches?

I installed version 5.1.1 with CentOS 7.9.2009, gcc compiler, c++11

When invoking METIS_PartGraphKway with the simplest program I found https://people.math.sc.edu/Burkardt/cpp_src/metis_test/metis_test.cpp, compiler reports "segmentation fault".

I searched and found that currently version 5.2.1 has some problems with the gklib dependency, so I tried to downgrade version to 5.1.0 instead from this archived url http://glaros.dtc.umn.edu/gkhome/metis/metis/download. With version 5.1.0, the bug no longer exists.

Post this information here for now, in case anyone encounters the same problem.

It is on p.9:

QUOTE
The header line contains either two (n, m), three (n, m, fmt), or four (n, m, fmt, ncon) parameters. The first two
parameters (n, m) are the number of vertices and the number of edges, respectively. Note that in determining the
number of edges m, an edge between any pair of vertices v and u is counted only once and not twice (i.e., we do not
count the edge (v; u) separately from (u; v)). For example, the graph in Figure 2 contains 11 vertices.
UNQUOTE

I am sure the very last word - vertices - should read "edges".

I have a graph that has 1K nodes, for example. I want to assign these nodes to a fat-tree network that has 32 nodes.
The output file after
gpmetis -ptype=rb graphfile 32
contains 0~31 labels for 1K nodes.

My understanding is that label 0-15 is the first bisected part, and label 16-31 is the second bisected part. Is this correct?
Reading the source code
it performs bisection and assign 0-15 to one bisected part and 16-31 to another bisected part.
Just want to make sure my understanding is correct.

I originally wanted to do
1)cluster 1K nodes to 32 nodes
2)perform bisection to assign two 16 nodes
3)perform bisection to assign two 8 nodes
4)so on
But I realized that it's already performed when I do 1) with Recursive Bisection option.

Thanks in advance.

I'm trying to build METIS 5.2.1 and get this compilation-error:

[ 59%] Building C object programs/CMakeFiles/gpmetis.dir/gpmetis.c.o
cd /home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.arm/Temp/METIS-5.2.1/build/programs && /usr/bin/cc  -I/home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.arm/Temp/METIS-5.2.1/build/xinclude -I/home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.arm/Temp/lib/include -I/home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.arm/Temp/include -I/home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.arm/Temp/METIS-5.2.1/programs/../libmetis -DLINUX -D_FILE_OFFSET_BITS=64 -std=c99 -fno-strict-aliasing -march=native -fPIC -Werror -Wall -pedantic -Wno-unused-function -Wno-unused-but-set-variable -Wno-unused-variable -Wno-unknown-pragmas -Wno-unused-label -DNDEBUG -DNDEBUG2 -DHAVE_EXECINFO_H -DHAVE_GETLINE -O3 -MD -MT programs/CMakeFiles/gpmetis.dir/gpmetis.c.o -MF CMakeFiles/gpmetis.dir/gpmetis.c.o.d -o CMakeFiles/gpmetis.dir/gpmetis.c.o -c /home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.arm/Temp/METIS-5.2.1/programs/gpmetis.c
/home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.arm/Temp/METIS-5.2.1/programs/gpmetis.c: In function ‘GPReportResults’:
/home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.arm/Temp/METIS-5.2.1/programs/gpmetis.c:248:66: error: implicit declaration of function ‘gk_GetProcVmPeak’ [-Werror=implicit-function-declaration]
   printf("  proc/self/stat/VmPeak:\t %7.3"PRREAL" MB\n", (real_t)gk_GetProcVmPeak()/(1024.0*1024.0));
                                                                  ^~~~~~~~~~~~~~~~
cc1: all warnings being treated as errors
programs/CMakeFiles/gpmetis.dir/build.make:78: recipe for target 'programs/CMakeFiles/gpmetis.dir/gpmetis.c.o' failed
make[3]: *** [programs/CMakeFiles/gpmetis.dir/gpmetis.c.o] Error 1
make[3]: Leaving directory '/home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.arm/Temp/METIS-5.2.1/build'
CMakeFiles/Makefile2:172: recipe for target 'programs/CMakeFiles/gpmetis.dir/all' failed
make[2]: *** [programs/CMakeFiles/gpmetis.dir/all] Error 2
make[2]: Leaving directory '/home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.arm/Temp/METIS-5.2.1/build'
Makefile:138: recipe for target 'all' failed
make[1]: *** [all] Error 2
make[1]: Leaving directory '/home/scratch.cponder_sw/Containers/ubuntu-pgi-openmpi.arm/Temp/METIS-5.2.1/build'
Makefile:80: recipe for target 'install' failed
make: *** [install] Error 2

I'm using the configuration line

make config shared=1 prefix=$(realpath ..) gklib_path=...

where gklib_path is set to the lib directory from building GKLib 5.1.1 (note that there is no GKLib 5.2.1).
From grep'ing the METIS 5.2.1 and GKlib 5.1.1 directories, I don't see any gk_GetProcVmPeak declared anywhere.

I want to transform a mesh(a 3D geometry in rendering) into a sets of triangles. Each set contains 64 triangles, which is also called a cluster or meshlet. So I conveted the mesh into a graph. For example the mesh has 768 triangles, so what I expect is 768/64 = 12 clusters.
However the returned part array shows the partition results arent strictly equal size. Some clusters have 65 vertices and some have 63, although most of the clusters have 64 vertices. So how do I force the Metis algorithm to return equal size clusters?
Function is METIS_PartGraphRecursive.

On the wikipedia METIS page I see an external link going to this page at umn.edu. Is one of them more official than the other? Is it a fork?
I ask as we want to put the best link on the third party libraries page for CGAL. When I get a reply I can also change on the wikipedia.

The xadj and adjncy nodal graph arrays obtained when using the MeshToNodal function contain nodes which are not part of the "root" node's adjacency list. For example, let's take the sample quad mesh/graph from METIS's documentation:

When using this mesh in the MeshToNodal API function with the eptr & eind arrays, and other inputs as follows:
eptr: 0 4 8 12 16 20 24 28 32
eind: 0 5 6 1 1 6 7 2 2 7 8 3 3 8 9 4 5 10 11 6 6 11 12 7 7 12 13 8 8 13 14 9
nn = 15
ne = 8
numflag = 0

The returned xadj and adjncy arrays are as follows:

xadj: 0 3 8 13 18 21 26 34 42 50 55 58 63 68 73 76
adjncy: 5 6 1, 0 5 6 7 2, 1 6 7 8 3, 2 7 8 9 4, 3 8 9, 0 6 1 10 11, 0 5 1 7 2 10 11 12, 1 6 2 8 3 11 12 13, 2 7 3 9 4 12 13 14, 3 8 4 13 14, 5 11 6, 5 10 6 12 7, 6 11 7 13 8, 7 12 8 14 9, 8 13 9
(I've included commas to help identify the "root" node lists)
The bolded values in the adjncy array are the nodes which should not be part of a nodes' adjacency list as I understand it's format.

I would expect the xadj and adjncy arrays to match the ones from the sample mesh/graph above, however it's including all nodes in the elements which the "root" node is a part of, and not only the nodes directly connected by a single edge.

Am I misunderstanding the purpose of the MeshToNodal function, or is there in fact an issue here?

Thank you,
Jeff Hadley

Failed to configure METIS

 CMake Deprecation Warning at CMakeLists.txt:1 (cmake_minimum_required):
   Compatibility with CMake < 2.8.12 will be removed from a future version of
   CMake.

   Update the VERSION argument <min> value or use a ...<max> suffix to tell
   CMake that the project does not need compatibility with older versions.

 CMake Error at CMakeLists.txt:50 (add_subdirectory):
   add_subdirectory given source "build/xinclude" which is not an existing
   directory.

 Configuring incomplete, errors occurred!
 See also "....../METIS/build/CMakeFiles/CMakeOutput.log".

Some jobs report the following error when run through Valgrind

==12272== Invalid read of size 8
==12272==    at 0x6B7ABF3: libmetis__Greedy_KWayCutOptimize (kwayfm.c:497)
==12272==    by 0x6B76A9E: libmetis__Greedy_KWayOptimize (kwayfm.c:26)
==12272==    by 0x6B73D39: libmetis__RefineKWay (kwayrefine.c:102)
==12272==    by 0x6B514BC: libmetis__MlevelKWayPartitioning (kmetis.c:135)
==12272==    by 0x6B512A6: METIS_PartGraphKway (kmetis.c:74)
==12272==    by 0x6B5C37D: metis_partgraphkway_ (frename.c:38)
...

This refers to

        if (pwgts[i] > maxpwgts[i] || pwgts[i] < minpwgts[i])

Looking at the preceding code it seems that maxpwgts and minpwgts are defined for the whole range 0:nparts+1, which leads me to suspect that pwgts is the problem. I can't see that pwgts, aka graph->pwgts is allocated the correct size of nparts+2 and also whether pwgts[nparts] and pwgts[nparts+1] are defined, but someone who is familiar with the code needs to look.

METIS is awesome and very useful for discrete math community. Now I am building a software dealing with dynamic weights of computation ML graph. Our operations and tensor are highly optimized and have shared codes in hardware, hence summation of the cost is dynamic. Also we have topical order constrain.

We have develop a solver. But to utilize the Multi-level framework, one of useful things I am trying to understand is how "idx_t Match_SHEM(ctrl_t *ctrl, graph_t *graph)" and "refine_KwayPartition" is coded. Is there any explanation here ? @karypis

Looking on https://github.com/KarypisLab/METIS/tags it is hard to say what is the latest version of the METIS.
Is it possible to change or add git tag to have exact version number consisting froim digirs and dots?

I systematically get a segmentation fault on the default metis version provided by petsc with --download-metis when I partition even simple and not too large graphs ( O(5 millions)). I tried a lot of cases as well as both the 32 and 64 bits version and also increasing ulimit (on Linux). I use Linux and have way enough RAM (32GB) for this example (less than 10% is used here).
Here is the shortest possible representative example with that problem (c++). I double checked it and I hope there is no mistake in this example.
The below example constructs the containers for a 1D line graph (n vertices connected by edges one by one as in a chain. Both end vertices only have a single neighbor while all other vertices have two neighbors).
Either this is something I am doing wrong or there is a bug in at least the metis version used in petsc. I haven't tried on the latest version of this repo and I would love to know if the bug also occurs here or if it was fixed in a recent commit (which one?).

Here is the example producing a segfault. If you don't get a segfault try a 10 millions or more vertices graph.

#include "metis.h"

int main(void)
{
// Number of vertices:
int n = 1000000;
// Addresses should for example be [0 1 3 5 7 8] for 5 vertices
idx_t addresses[n+1];
addresses[0] = 0; addresses[1] = 1;
for (int i = 2; i < n; i++)
addresses[i] = addresses[i-1] + 2;
addresses[n] = addresses[n-1]+1;

// Connected vertices should for example be [1 0 2 1 3 2 4 3] for 5 vertices
idx_t connectivities[2*(n-1)];
connectivities[0] = 1;
for (int i = 1; i < n-1; i++)
{
    connectivities[2*i-1] = i-1;
    connectivities[2*i+0] = i+1;
}
connectivities[2*(n-1)-1] = connectivities[2*(n-1)-2]-1;

idx_t nvtxs = n;
idx_t nEdges = n-1;

idx_t metisOptions[METIS_NOPTIONS];
METIS_SetDefaultOptions(metisOptions);
metisOptions[METIS_OPTION_NUMBERING] = 0; // c numbering (start at 0)

idx_t ncon = 1;
idx_t nParts = 2;
idx_t objval;
idx_t part[nvtxs];

int ret = METIS_PartGraphRecursive ( &nvtxs, &ncon, addresses, connectivities, NULL, NULL, NULL, &nParts, NULL, NULL, metisOptions, &objval, part );

}

I think there is a typo in page 9 of the manual.pdf
"For example, the graph in Figure 2 contains 11 vertices." -> "... 11 edges."

The METIS library depends on functions from GKlib however this is not linked to the metis target in CMake. Instead GKlib is linked against the program binaries in programs.

Using libmetis standalone results in errors missing refs to various gk_* routines

...
undefined reference: 'gk_malloc'
...

The latest version install is on https://cmake.org/install/ using a bootstrap.sh script

Hello,
I keep getting the error message that Metis has not freed its memory even though the system has more than 200 GB of free memory.

gpmetis -minconn -contig -niter=200 x1.2621442.graph.info 80
******************************************************************************
METIS 5.2 Copyright 1998-16, Regents of the University of Minnesota
 (HEAD: , Built on: Sep 22 2020, 20:36:25)
 size of idx_t: 32bits, real_t: 32bits, idx_t *: 64bits

Graph Information -----------------------------------------------------------
 Name: x1.2621442.graph.info, #Vertices: 2621442, #Edges: 7864320, #Parts: 80

Options ---------------------------------------------------------------------
 ptype=kway, objtype=cut, ctype=shem, rtype=greedy, iptype=metisrb
 dbglvl=0, ufactor=1.030, no2hop=NO, minconn=YES, contig=YES
 ondisk=NO, nooutput=NO
 seed=-1, niparts--1, niter=200, ncuts=1

Direct k-way Partitioning ---------------------------------------------------
munmap_chunk(): invalid pointer
munmap_chunk(): invalid pointer
***It seems that Metis did not free all of its memory! Report this.

***Metis returned with an error.
Could not find pointer 0xffffb6cb0010 in mcore

Aborted (core dumped)

I have tried different starting meshes and modified parameters (mainly the number of partitions). Thanks.

Division by 0 occurs in kmetis.c line 56 on this computation:

  /* set various run parameters that depend on the graph */
  ctrl->CoarsenTo = gk_max((*nvtxs)/(40*gk_log2(*nparts)), 30*(*nparts));

This is because gk_log2 will return 0 if its input is 1.

=================================================================
==6382==ERROR: AddressSanitizer: FPE on unknown address 0x5622b6c7e8f0 (pc 0x5622b6c7e8f0 bp 0x7fff6575cc10 sp 0x7fff6575cb70 T0)
    #0 0x5622b6c7e8f0 in METIS_PartGraphKway METIS/libmetis/kmetis.c:56

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: FPE METIS/libmetis/kmetis.c:56 in METIS_PartGraphKway
==6382==ABORTING```

There should be an error handling or a message of help for users.
(I am very happy that I could compile with gdb=1 to backtrack the bug, thanks !)

Hey,

SCIP download page recommend installing hMETIS but the link is not working. Is it possible to update the link?

Thanks in advance!

Hi,

I tried to compile METIS with GCC 11.1.0. I used the following config:

make config cc=gcc i64=1 gdb=1 debug=1

However, I got the following error:

[ 25%] Building C object libmetis/CMakeFiles/metis.dir/kwayfm.c.o
cd ~/METIS/build/libmetis && /usr/bin/gcc  -I~/METIS/build/xinclude -I"~/METIS/~/local/include" -I/root/local/include -I~/METIS/libmetis/. -DLINUX -D_FILE_OFFSET_BITS=64 -std=c99 -fno-strict-aliasing -march=native -fPIC -Werror -Wall -pedantic -Wno-unused-function -Wno-unused-but-set-variable -Wno-unused-variable -Wno-unknown-pragmas -Wno-unused-label -Werror -DDEBUG -DNDEBUG -DNDEBUG2 -DHAVE_EXECINFO_H -DHAVE_GETLINE -Og -MD -MT libmetis/CMakeFiles/metis.dir/kwayfm.c.o -MF CMakeFiles/metis.dir/kwayfm.c.o.d -o CMakeFiles/metis.dir/kwayfm.c.o -c ~/METIS/libmetis/kwayfm.c
~/METIS/libmetis/kwayfm.c: In function ‘libmetis__Greedy_McKWayCutOptimize’:
~/METIS/libmetis/kwayfm.c:954:46: error: ‘to’ may be used uninitialized in this function [-Werror=maybe-uninitialized]
  954 |                   +1, pwgts+to*ncon, pijbm+to*ncon))
      |                                            ~~^~~~~
~/METIS/libmetis/kwayfm.c: In function ‘libmetis__Greedy_McKWayVolOptimize’:
~/METIS/libmetis/kwayfm.c:1305:45: error: ‘to’ may be used uninitialized in this function [-Werror=maybe-uninitialized]
 1305 |                  +1, pwgts+to*ncon, pijbm+to*ncon))
      |                                           ~~^~~~~

I added CONFIG_FLAGS += -Wno-maybe-uninitialized to the Makefile, however it didn't work.

2 1 011
1 2 1 
2 1 1 

Graph file looks like above.
There are only two nodes, one with weight of 1 and another with weight of 2.
If I do
gpmetis -ptype=rb test_graphfile 2
the result is

1
1

I thought it's intuitive to return 0,1 when there are only two nodes and I am trying to partition them into two.
Is this expected?

I ran this command on a weather grid from NCAR at 5km resolution:

gpmetis -minconn -contig -niter=200 x1.*.graph.info 1792

This is the output it gave:

******************************************************************************
METIS 5.2 Copyright 1998-16, Regents of the University of Minnesota
 (HEAD: , Built on: Nov 30 2022, 10:22:25)
 size of idx_t: 32bits, real_t: 32bits, idx_t *: 64bits

Graph Information -----------------------------------------------------------
 Name: x1.5898242.graph.info, #Vertices: 5898242, #Edges: 17694720, #Parts: 1792

Options ---------------------------------------------------------------------
 ptype=kway, objtype=cut, ctype=shem, rtype=greedy, iptype=metisrb
 dbglvl=0, ufactor=1.030, no2hop=NO, minconn=YES, contig=YES
 ondisk=NO, nooutput=NO
 seed=-1, niparts--1, niter=200, ncuts=1

Direct k-way Partitioning ---------------------------------------------------
free(): invalid pointer
free(): invalid pointer
***It seems that Metis did not free all of its memory! Report this.

***Metis returned with an error.
Could not find pointer 0x7fad5e41f010 in mcore

Aborted (core dumped)

This is the only case I've seen of gpmetis failing. Does this happen if I exhaust the RAM memory?

Using METIS 5.1:

pyfr -p partition 8 -ebalanced -pmetis inc-cylinder.pyfrm foo/
 • Combine mesh parts (0.02s)
 • Construct graph (0.00s)
 • Partition graph (0.01s)
 • Renumber vertices (0.03s)
 • Repartition mesh (0.01s)
 • Write mesh (0.01s)

where the partitioning and renumbering (both of which make calls to METIS_PartGraphRecursive) complete almost immediately. By contrast using METIS 5.2.1:

pyfr -p partition 8 -ebalanced -pmetis inc-cylinder.pyfrm foo/
 • Combine mesh parts (0.01s)
 • Construct graph (0.00s)
 • Partition graph (17.33s)
 • Renumber vertices (7.22s)
 • Repartition mesh (0.01s)
 • Write mesh (0.01s)

where we can see a huge slow down (on the order of ~2000x) for the partition graph portion which makes a single call to METIS_PartGraphRecursive. The inputs are identical in both cases, also reproduced with METIS_PartGraphKway. Also reproduced on both Linux (x86-64) and macOS (AARCH64).

This occurs with all of our grids/meshes. Profiling 5.2.1 with perf record we find:

    17.05%  pyfr      libmetis.so.0                                      [.] libmetis__FM_Mc2WayCutRefine
     8.88%  pyfr      libmetis.so.0                                      [.] libmetis__CreateCoarseGraph
     8.03%  pyfr      libmetis.so.0                                      [.] libmetis__FM_2WayCutRefine
     7.93%  pyfr      libmetis.so.0                                      [.] libmetis__rpqInsert
     5.24%  pyfr      libmetis.so.0                                      [.] libmetis__rpqUpdate
     5.12%  pyfr      libc.so.6                                          [.] random
     4.21%  pyfr      libmetis.so.0                                      [.] libmetis__Compute2WayPartitionParams
     4.21%  pyfr      libmetis.so.0                                      [.] libmetis__rpqGetTop
     4.21%  pyfr      libmetis.so.0                                      [.] libmetis__Match_SHEM
     4.01%  pyfr      libmetis.so.0                                      [.] libmetis__SelectQueue
     2.79%  pyfr      libmetis.so.0                                      [.] libmetis__iset
     2.77%  pyfr      libmetis.so.0                                      [.] libmetis__Project2WayPartition
     2.20%  pyfr      libmetis.so.0                                      [.] libmetis__Match_RM
     1.99%  pyfr      libmetis.so.0                                      [.] libmetis__ComputeLoadImbalanceDiffVe
c
     1.93%  pyfr      libmetis.so.0                                      [.] libmetis__McGeneral2WayBalance
     1.85%  pyfr      libmetis.so.0                                      [.] libmetis__iaxpy
     1.34%  pyfr      libmetis.so.0                                      [.] libmetis__rpqDelete
     1.22%  pyfr      libmetis.so.0                                      [.] libmetis__BucketSortKeysInc

whereas with 5.1 (good) we find:

    10.18%  pyfr      libopenblas64_p-r0-15028c96.3.21.so                [.] blas_thread_server
     9.73%  pyfr      [unknown]                                          [k] 0xffffffff900001a2
     9.30%  pyfr      libc.so.6                                          [.] __sched_yield
     8.22%  pyfr      libpython3.11.so.1.0                               [.] _PyEval_EvalFrameDefault
     1.00%  pyfr      libpython3.11.so.1.0                               [.] 0x0000000000192fb0
     0.96%  pyfr      libpython3.11.so.1.0                               [.] 0x00000000001949c0
     0.80%  pyfr      libmetis.so.0                                      [.] libmetis__FM_Mc2WayCutRefine
     0.59%  pyfr      libpython3.11.so.1.0                               [.] _PyType_Lookup
     0.57%  pyfr      libmetis.so.0                                      [.] libmetis__rpqInsert

where METIS is just a rounding error in the runtime.

Problem

METIS assigns all vertices to one part, seemingly violating the max load imbalance.

How to reproduce

I am using METIS to partition a 900-vertices graph into 2 parts. And I give the target partition weights of 0.5 each, with a max load imbalance of 700. The command I used is:

./gpmetis graph.txt 2 -objtype=cut -minconn -tpwgts=target_weights.txt -ufactor=700

And here are the graph and target weights files:
graph.txt
target_weights.txt

The vertices have two weights in the graph, where one of the weights is always set to 1, hence representing the number of vertices in each part.

Observed

My understanding is that METIS should partition the graph into 2 parts, each part is no larger than 900*0.5*1.7=765 vertices. However, METIS assigned all the vertices to one part.

Expected

METIS should produce a partition that satisfies the 1.7 max load imbalance for both constraints in the graph.

The old website doesn't seem to exist any more
http://glaros.dtc.umn.edu
and I welcome the change of having the project hosted on GitHub instead.
Could you please make the 5.1.0 release visible from here though?

/usr/bin/gcc -DLINUX -D_FILE_OFFSET_BITS=64 -DMACOS -DNDEBUG -DNDEBUG2 -DHAVE_EXECINFO_H -DHAVE_GETLINE -O3 -arch arm64 -isysroot /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX13.1.sdk -dynamiclib -Wl,-headerpad_max_install_names -L/opt/homebrew/opt/openblas/lib -o libmetis.dylib -install_name /Users/o/experiments/METIS/build/libmetis/libmetis.dylib CMakeFiles/metis.dir/auxapi.c.o CMakeFiles/metis.dir/balance.c.o CMakeFiles/metis.dir/bucketsort.c.o CMakeFiles/metis.dir/checkgraph.c.o CMakeFiles/metis.dir/coarsen.c.o CMakeFiles/metis.dir/compress.c.o CMakeFiles/metis.dir/contig.c.o CMakeFiles/metis.dir/debug.c.o CMakeFiles/metis.dir/fm.c.o CMakeFiles/metis.dir/fortran.c.o CMakeFiles/metis.dir/frename.c.o CMakeFiles/metis.dir/gklib.c.o CMakeFiles/metis.dir/graph.c.o CMakeFiles/metis.dir/initpart.c.o CMakeFiles/metis.dir/kmetis.c.o CMakeFiles/metis.dir/kwayfm.c.o CMakeFiles/metis.dir/kwayrefine.c.o CMakeFiles/metis.dir/mcutil.c.o CMakeFiles/metis.dir/mesh.c.o CMakeFiles/metis.dir/meshpart.c.o CMakeFiles/metis.dir/minconn.c.o CMakeFiles/metis.dir/mincover.c.o CMakeFiles/metis.dir/mmd.c.o CMakeFiles/metis.dir/ometis.c.o CMakeFiles/metis.dir/options.c.o CMakeFiles/metis.dir/parmetis.c.o CMakeFiles/metis.dir/pmetis.c.o CMakeFiles/metis.dir/refine.c.o CMakeFiles/metis.dir/separator.c.o CMakeFiles/metis.dir/sfm.c.o CMakeFiles/metis.dir/srefine.c.o CMakeFiles/metis.dir/stat.c.o CMakeFiles/metis.dir/timing.c.o CMakeFiles/metis.dir/util.c.o CMakeFiles/metis.dir/wspace.c.o -L"/Users/o/experiments/METIS/~/local/lib" -L/Users/o/local/lib

ld: warning: directory not found for option '-L/Users/o/experiments/METIS/~/local/lib'
Undefined symbols for architecture arm64:
"_gk_CPUSeconds", referenced from:
_libmetis__CoarsenGraph in coarsen.c.o
_libmetis__Match_RM in coarsen.c.o
_libmetis__Match_SHEM in coarsen.c.o
_CoarsenGraphNlevels in coarsen.c.o
_libmetis__CreateCoarseGraph in coarsen.c.o
_libmetis__Match_2HopAny in coarsen.c.o
_libmetis__Match_2HopAll in coarsen.c.o
...

Is this how it is supposed to happen ?

I'm getting the following warning and error while trying to use the METIS package with OpenMPI:
"ld: warning: ignoring file /usr/local/lib/libmetis.a, building for macOS-arm64 but attempting to link with file built for macOS-x86_64
Undefined symbols for architecture arm64:
"_METIS_PartGraphRecursive", referenced from:
getPartitioning(int, int*) in main-37344f.o
ld: symbol(s) not found for architecture arm64"

I'm using the following command:
"mpic++ main.cpp -o main.o -I/usr/local/include -L/usr/local/lib -lmetis"

I'm using Macbook M1 Pro.

Do you have any suggestions to avoid this error?

I've encountered error (heap corruption detected) in gk_free() while reordering sparse matrix with METIS_NodeND.
My development environment: windows 10 + visual studio 2017.
How can I get pass? Any suggestion will be appreciated.

Here are the matrix data:
nvtxs:
30
xadj:
0 8 13 21 32 37 48 55 61 62 63 67 71 83 84 91 101 102 108 113 125 130 135 136 141 153 158 166 170 171 178
adjncy:
0 3 5 10 17 26 27 29
1 4 18 20 25
2 6 7 12 14 15 19 24
0 3 5 11 12 15 17 19 24 26 29
1 4 18 20 25
0 3 5 11 12 15 17 19 24 26 29
2 6 12 14 15 19 24
2 7 12 15 19 24
8
9
0 10 26 27
3 5 11 29
2 3 5 6 7 12 14 15 19 21 23 24
13
2 6 12 14 15 19 24
2 3 5 6 7 12 14 15 19 24
16
0 3 5 17 26 29
1 4 18 20 25
2 3 5 6 7 12 14 15 19 21 23 24
1 4 18 20 25
12 19 21 23 24
22
12 19 21 23 24
2 3 5 6 7 12 14 15 19 21 23 24
1 4 18 20 25
0 3 5 10 17 26 27 29
0 10 26 27
28
0 3 5 11 17 26 29

Function return wrong ordering on simplest graph. Results depend on input garbage in working parameters.

example:

const idx_t neqns = 2;
idx_t xadj[3]={1,2,3};
idx_t adjncy[2] = {2,1};

idx_t delta = 1;
idx_t maxint = IDX_MAX;

const idx_t nvtxs = 2;
std::unique_ptr<idx_t[]> perm(new idx_t [nvtxs+5]);
std::unique_ptr<idx_t[]> iperm(new idx_t [nvtxs+5]);
std::unique_ptr<idx_t[]> head(new idx_t [nvtxs+5]);
std::unique_ptr<idx_t[]> qsize(new idx_t [nvtxs+5]);
std::unique_ptr<idx_t[]> list(new idx_t [nvtxs+5]);
std::unique_ptr<idx_t[]> marker(new idx_t [nvtxs+5]);
idx_t nofsub;

bool is_bug_produced = true;
if(is_bug_produced){
    for(idx_t i=0;i<nvtxs+5;++i) head[i] = 2;
}else{
    for(idx_t i=0;i<nvtxs+5;++i) head[i] = -2;
}

genmmd(neqns,xadj,adjncy,iperm.get(),perm.get(),delta,head.get(),qsize.get(),list.get(),marker.get(),maxint,&nofsub);

Providing a cmake config file makes it easier to find and use Metis. Metis should create such a config file.
CMake offers some functions to do this without much effort: https://cmake.org/cmake/help/latest/module/CMakePackageConfigHelpers.html

Background

Hello METIS team, I write a simple bert model and test partition with METIS , it seems that the partition does not include topological order in consideration. I am going to add such support for native partition algorithms inside mutli-level framework. I suppose we are using KL algorithm inside ML framework:

The problem

The partition does not include topological order, hence part a graph [a, b, c, d] into 2 devices alternating, which is unacceptable, because across device communication with off chip memory is expensive. Hence in our native algorithm , we apply partition upon topological sorted array with divide and conquer solver bottom up.

Does METIS support this? If I want add such support in METIS, how should I start off?

CMake (GUI) can display project options with the same prefix under a single group.
For example, CMAKE_C_COMPILER and CMAKE_C_FLAGS can be displayed under the CMAKE group.
Currently, all of the options in this project are put under the "Ungrouped Entries" group.

First off, I just want to say this piece of software has been very very useful to the numerical math community and I would like to extend my appreciation for creating and maintaining METIS.

I was hoping that if there is any interest in exposing the libmetis/ header functionality. Right now when I install METIS based on the instructions metis.h is installed, but it does not expose the libmetis.so API. In order for me to use the code in libmetis.so I end up keeping a copy of METIS in my project folder and just manually linking from there. Would it be possible to install the other header files (like metislib.h, struct.h, etc. in libmetis/ to the install include folder along with metis.h?

Or maybe I am not properly understanding how to call libmetis.so functionality in C++ based on the current installation instructions.

Hello,

Thank you for sharing this valuable work! I am having some trouble understanding the behavior of metis with edge wights assigned. I suspect I am using the wrong options that caused this.
I am trying the METIS_PartGraphKway function on a toy undirected, weighted graph like this:

where the red edges have weight 1, and black edges have weight 10.
I was expecting the function would produce a partition that separate the top-left corner vertex, however it is assigned the top-mid vertex a single group. And I also noticed that the function produces the same output when I set edge weights as 10 for all.

options[METIS_OPTION_PTYPE] = METIS_PTYPE_KWAY;
options[METIS_OPTION_OBJTYPE] = METIS_OBJTYPE_CUT;
options[METIS_OPTION_CTYPE] = METIS_CTYPE_SHEM;
options[METIS_OPTION_IPTYPE] = METIS_IPTYPE_GROW;
options[METIS_OPTION_RTYPE] = METIS_RTYPE_FM;
options[METIS_OPTION_DBGLVL] = 255;
options[METIS_OPTION_UFACTOR] = 1000; 
options[METIS_OPTION_MINCONN] = 0;
options[METIS_OPTION_CONTIG] = 0;
options[METIS_OPTION_SEED] = -1;
options[METIS_OPTION_NITER] = 100;
options[METIS_OPTION_CCORDER] = 0;
options[METIS_OPTION_NCUTS] = 5;

Any help would be appreciated, thank you!

I am trying to build a conda package that depends on the master branch of this repo (not 5.1.0). Could you add a tag to this repo such as 5.2.0 or 5.1.1 so I can use it for the metis conda package at https://github.com/conda-forge/metis-feedstock/blob/master/recipe/meta.yaml

Thank you

I am using METIS for a CFD code. I would like to minimze the maximum degree of the subdomain graph. Following the documentation, I am currently doing the following

idx_t numflag = 0; // C-style ordering
idx_t *xadj, *adjncy;
ierr = METIS_MeshToDual(
    &nelem, &nnode, eptr.data(), eind.data(), &ncommon, &numflag, &xadj, &adjncy);
if (ierr != METIS_OK) {
    stringstream msg;
    msg << "Error with METIS_MeshToDual with exit code " << ierr;
    throw FatalException(msg.str());
}

idx_t options[METIS_NOPTIONS];
METIS_SetDefaultOptions(options);
options[METIS_OPTION_PTYPE] = METIS_PTYPE_KWAY;
options[METIS_OPTION_OBJTYPE] = METIS_OBJTYPE_CUT;
options[METIS_OPTION_IPTYPE] = METIS_IPTYPE_NODE;
options[METIS_OPTION_NCUTS] = 5;
options[METIS_OPTION_NUMBERING] = 0; // C-style ordering
options[METIS_OPTION_MINCONN] = 1;
options[METIS_OPTION_CONTIG] = 1;

idx_t ncon = 1; // number of balancing constraints, should be at least 1
ierr = METIS_PartGraphKway(
    &nelem, &ncon, xadj, adjncy,
    NULL, NULL, NULL,
    &nPart_lvl1, sub_reg_weights.data(), NULL,
    options, &objval, elem_part_id.data());
if (ierr != METIS_OK) {
    stringstream msg;
    msg << "Error with METIS_PartGraphKway with exit code " << ierr;
    throw FatalException(msg.str());
}

free((void *) xadj);
free((void *) adjncy);

In particular, I am using options[METIS_OPTION_MINCONN] = 1; to achieve my objective. Compared to the following code

ierr = METIS_PartMeshDual(
    &nelem, &nnode, eptr.data(), eind.data(),
    NULL, NULL,
    &ncommon, &nPart_lvl1, sub_reg_weights.data(),
    NULL /*options*/, &objval, elem_part_id.data(), node_part_id.data());
if (ierr != METIS_OK) {
    stringstream msg;
    msg << "Error with METIS_PartMeshDual with exit code " << ierr;
    throw FatalException(msg.str());
}

I have observed that, with the first approach, the sum of the subdomains' degree is usually smaller whereas the maximum subdomain's degree can be larger which isn't what I expected.

Is this the expected behavior or am I doing something wrong?

Thank you very much for your help.