Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/KarypisLab/ParMETIS/llms.txt

Use this file to discover all available pages before exploring further.

ParMETIS partitions a distributed graph across MPI processes so that the number of edges cut between partitions is minimized while keeping vertex weights balanced. Each process owns a contiguous range of vertices and the local adjacency lists for those vertices. The library handles all inter-process communication internally, so you only need to build the distributed data structures and call the appropriate function.

​
Choosing a partitioning function

FunctionWhen to use
ParMETIS_V3_PartKwayGeneral-purpose k-way partitioning. Best default choice.
ParMETIS_V3_PartGeomKwayYou have geometric coordinates (e.g. mesh node positions). Combines geometric and graph information for better initial partitioning.
ParMETIS_V3_PartGeomGeometry-only partitioning (no graph structure). Useful as a fast initial partition or when no adjacency data is available.
Use PartGeomKway when vertex coordinates are available and the graph has spatial locality — it typically produces lower edge cuts than PartKway alone for structured meshes.

​
Step-by-step setup

1

Build vtxdist

vtxdist is a replicated array of length npes + 1. vtxdist[i] holds the global index of the first vertex owned by process i. vtxdist[npes] equals the total number of vertices.
/* Example: 12 vertices distributed across 3 processes */
idx_t vtxdist[4] = {0, 4, 8, 12};
Every process must hold an identical copy of vtxdist.
2

Build local xadj and adjncy in CSR format

Each process stores the adjacency lists of its local vertices in compressed sparse row (CSR) format. xadj has length local_nvtxs + 1; xadj[i] is the index into adjncy where vertex i’s neighbor list begins.
idx_t local_nvtxs = vtxdist[mype+1] - vtxdist[mype];

/* xadj[i+1] - xadj[i] = degree of local vertex i */
idx_t xadj[5]   = {0, 2, 5, 7, 9};   /* local_nvtxs=4, so length 5 */
idx_t adjncy[9] = {1, 4,              /* neighbors of local vertex 0 */
                   0, 2, 5,           /* neighbors of local vertex 1 */
                   1, 6,              /* neighbors of local vertex 2 */
                   2, 7};             /* neighbors of local vertex 3 */
Neighbor indices are global vertex numbers.
3

Set wgtflag

wgtflag controls which weight arrays are used:
ValueMeaning
0No weights (pass NULL for vwgt and adjwgt)
1Edge weights only
2Vertex weights only
3Both vertex and edge weights
idx_t wgtflag = 3;  /* use both vwgt and adjwgt */
4

Set tpwgts

tpwgts is an array of nparts * ncon floats specifying the target fraction of total weight for each (partition, constraint) pair. The values for each constraint must sum to 1.0.
idx_t  ncon   = 1;
idx_t  nparts = 4;
real_t tpwgts[4];
for (int i = 0; i < nparts * ncon; i++)
    tpwgts[i] = 1.0f / nparts;  /* equal-weight partitioning */
5

Set ubvec

ubvec is an array of ncon floats, one per constraint, giving the maximum allowed imbalance ratio. A value of 1.05 permits up to 5% imbalance.
real_t ubvec[1] = {1.05f};
6

Call the function and read outputs

After the call, edgecut holds the number of cut edges and part[i] holds the partition number (0-based) assigned to local vertex i.
idx_t edgecut;
idx_t part[local_nvtxs];

ParMETIS_V3_PartKway(vtxdist, xadj, adjncy, vwgt, adjwgt,
                     &wgtflag, &numflag, &ncon, &nparts,
                     tpwgts, ubvec, options, &edgecut, part, &comm);

​
Complete example

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include <parmetis.h>

int main(int argc, char *argv[])
{
    MPI_Comm comm;
    int npes, mype;

    MPI_Init(&argc, &argv);
    MPI_Comm_dup(MPI_COMM_WORLD, &comm);
    MPI_Comm_size(comm, &npes);
    MPI_Comm_rank(comm, &mype);

    /*
     * Simple 8-vertex ring graph distributed across 2 processes:
     *   process 0 owns vertices 0-3
     *   process 1 owns vertices 4-7
     */
    idx_t vtxdist[3] = {0, 4, 8};

    /* Local adjacency (CSR) for each process */
    idx_t xadj_p0[]   = {0, 2, 4, 6, 8};
    idx_t adjncy_p0[] = {7, 1,  0, 2,  1, 3,  2, 4};

    idx_t xadj_p1[]   = {0, 2, 4, 6, 8};
    idx_t adjncy_p1[] = {3, 5,  4, 6,  5, 7,  6, 0};

    idx_t *xadj   = (mype == 0) ? xadj_p0   : xadj_p1;
    idx_t *adjncy = (mype == 0) ? adjncy_p0 : adjncy_p1;

    /* Uniform vertex and edge weights */
    idx_t nvtxs_local = vtxdist[mype+1] - vtxdist[mype];
    idx_t *vwgt   = (idx_t *)malloc(nvtxs_local * sizeof(idx_t));
    idx_t *adjwgt = (idx_t *)malloc(xadj[nvtxs_local] * sizeof(idx_t));
    for (idx_t i = 0; i < nvtxs_local; i++)          vwgt[i]   = 1;
    for (idx_t i = 0; i < xadj[nvtxs_local]; i++)    adjwgt[i] = 1;

    idx_t  wgtflag = 3, numflag = 0, ncon = 1, nparts = 2;
    real_t tpwgts[2] = {0.5f, 0.5f};
    real_t ubvec[1]  = {1.05f};

    /* options[0]=0 uses default settings */
    idx_t options[3] = {0, 0, 0};

    idx_t  edgecut;
    idx_t *part = (idx_t *)malloc(nvtxs_local * sizeof(idx_t));

    ParMETIS_V3_PartKway(vtxdist, xadj, adjncy, vwgt, adjwgt,
                         &wgtflag, &numflag, &ncon, &nparts,
                         tpwgts, ubvec, options, &edgecut, part, &comm);

    if (mype == 0)
        printf("Edge cut: %d\n", (int)edgecut);

    for (int p = 0; p < npes; p++) {
        if (mype == p) {
            for (idx_t i = 0; i < nvtxs_local; i++)
                printf("process %d: vertex %d -> partition %d\n",
                       mype, (int)(vtxdist[mype] + i), (int)part[i]);
        }
        MPI_Barrier(comm);
    }

    free(vwgt); free(adjwgt); free(part);
    MPI_Comm_free(&comm);
    MPI_Finalize();
    return 0;
}

​
Function signatures

int ParMETIS_V3_PartKway(
    idx_t *vtxdist, idx_t *xadj, idx_t *adjncy,
    idx_t *vwgt, idx_t *adjwgt,
    idx_t *wgtflag, idx_t *numflag, idx_t *ncon, idx_t *nparts,
    real_t *tpwgts, real_t *ubvec, idx_t *options,
    idx_t *edgecut, idx_t *part, MPI_Comm *comm);

int ParMETIS_V3_PartGeomKway(
    idx_t *vtxdist, idx_t *xadj, idx_t *adjncy,
    idx_t *vwgt, idx_t *adjwgt,
    idx_t *wgtflag, idx_t *numflag, idx_t *ndims, real_t *xyz,
    idx_t *ncon, idx_t *nparts,
    real_t *tpwgts, real_t *ubvec, idx_t *options,
    idx_t *edgecut, idx_t *part, MPI_Comm *comm);

int ParMETIS_V3_PartGeom(
    idx_t *vtxdist, idx_t *ndims, real_t *xyz,
    idx_t *part, MPI_Comm *comm);

​
Compilation

mpicc -o prog prog.c -lparmetis -lmetis
Set numflag = 0 for C-style 0-based indexing. Set numflag = 1 for Fortran-style 1-based indexing.
To enable default settings, set options[0] = 0. To override specific options, set options[0] = 1 and then set options[PMV3_OPTION_DBGLVL] and options[PMV3_OPTION_SEED] as needed.

Build docs developers (and LLMs) love

Get started for freeTalk to us