Running Metis

The Metis package contains two programs, pmetis and kmetis. They use different partitioning algorithms--I prefer pmetis because it often produces better connectivity. Kmetis is supposed to scale better for large numbers of partitions.

     gjoa% pmetis partition 19
**********************************************************************
  METIS 4.0.1 Copyright 1998, Regents of the University of Minnesota

Graph Information ---------------------------------------------------
  Name: partition, #Vertices: 911, #Edges: 1755, #Parts: 19

Recursive Partitioning... -------------------------------------------
  19-way Edge-Cut:     234, Balance:  1.04 

Timing Information --------------------------------------------------
  I/O:                             0.010
  Partitioning:                    0.040   (PMETIS time)
  Total:                           0.050
**********************************************************************

The number to note here is Balance: 1.04. A value of 1.00 means that it is load balanced, while 1.04 means that it has produced a partitioning which has some imbalance. The output is in partition.part.19.