software

Below are a few older software projects. For more recent software, please visit TDAlab’s software page.

PaToH v3.3

PaToH (Partitioning Tools for Hypergraph) is a Multilevel Hypergraph Partitioning tool that I developed during my doctoral studies at Bilkent University (1994-1999). It was the fastest hypergraph partitioner when I wrote it, and probably it is still the fastest sequential partitioner today.

Important features of PaToH:

  • Fast, stable multilevel hypergraph partitioner,
  • Hypergraph partitioning with fixed cells,
  • Multi-constraint hypergraph partitioner.

Below you will find the latest binary distributions of PaToH for Linux and Mac OS X.

Below you will find older binary distributions of PaToH for different architectures.

Please note that some distributions are not updated as often as the others, if ever. If you are interested in running PaToH on a different/newer platform, please notify me, and I will attempt to prepare a version for your preferred platform provided I have access to it. Each distribution also contains a version of the manual for that specific distribution. Here is the most recent manual in PDF format.

You can also use PaToH via Zoltan for hypergraph partitioning or via Mondriaan for matrix partitioning.

PaToH Matlab Interface:

The aim of the PaToH Matrix Partitioning Interface is to provide sparse matrix partitioning routines in Matlab. The partitioning routines are based on hypergraph models (see related publications below) and use PaToH hypergraph partitioning tool within a mex function. Apart from the mex function routine that builds a hypergraph and calls PaToH, everything else is based on matrices and vectors and implemented in Matlab.

Download:

PaToH Matlab Interface source files and the manual (last update: May 6, 2020).

Latest Changes:

  • Jul 15, 2020: Minor fix: removing an unnecessary re-alloc in hypergraph read that caused problem in very large hypergraph.
  • May 6, 2020: Minor edits to PaToH Matlab interface to get PaToHSpy working with new Matlab versions.
  • May 4, 2020: A minor, and rare, reproducibility bug fixed. Bug only occurred for tiny hypergraphs (less than 100 vertices).
  • Nov 7, 2019: v3.3 has major improvement in fixed cell partitioning (average ~20% on my test set).
  • Oct 1, 2019: latest v3.2 a rare bug in partitioning with fixed cells is fixed.
  • Sep 29, 2019: patoh executable now gives warning when a cell is repeated in the net list and ignores repeated cells.
  • Aug 29, 2019: yet another a very minor final output bug: Multi-Constraint partitioning’s final output cut cost was not taking the net weights into account.
  • Jun 20, 2019: a very minor corner bug fixed in patoh executable only occurred when k=2 and perfect balance is requested and some nets were filtered with threshold.
  • Mar 22, 2011: a new parameter “balance” is added to allow users to relax balance constraints during recursive bisections.
  • Mar 13, 2011: v3.2 includes multi-constraint partitioning with non-unit net weights and target part weights. A minor bug fixed in V-cycle for disconnected hypergraphs.
  • Oct 28, 2010: A small typo is fixed in Matlab Interface.
  • Aug 13, 2010: Matlab Interface license info added.
  • Jun 27, 2010: Minor bug fix to improve balance for disconnected hypergraphs.
  • May 31, 2010: A new unified interface for regular, multi-constraint and fix-vertex hypergraph partitioning, that also allows user to specify target part weights (ratios).
  • Oct 9, 2009: Small load imbalance improvement for partitioning hypergraphs with isolated vertices into non-power of two parts. Also added a cuttype option to PaToH Matlab MEX interface.
  • Jun 28, 2009: Matlab Interface is available!
  • Nov 24, 2008: Added PaToH_Refine_Bisec to interface.
  • May 12, 2006: Fixed the memory alignment on 64-bit libraries, improving the performance significantly on IA64 architectures. Thanks to Duraid Madina for noticing the alignment problem on IA64 and suggesting the fix!
  • Jan 10, 2005: Changed the default behavior to continue to partition, with default values, if the chosen algorithm is not implemented in the particular partitioner Also a minor balance improvement was made.
  • Nov 11, 2004: Mac OS X distribution has been added.
  • Aug 15, 2002: Fixed a couple of small bugs and changed the default values of a few parameters.

Selected Publications

  1. Chap
    PaToH (Partitioning Tool for Hypergraphs)
    Ümit V. Çatalyürek, and Cevdet Aykanat
    In Encyclopedia of Parallel Computing, 2011.
  2. JRNL
    A matrix partitioning interface to PaToH in MATLAB
    Bora Uçar, Ümit V. Çatalyürek, and Cevdet Aykanat
    Parallel Computing, 2010.
  3. JRNL
    On Two-Dimensional Sparse Matrix Partitioning: Models, Methods, and a Recipe
    Ümit V. Çatalyürek, Cevdet Aykanat, and Bora Uçar
    SIAM Journal on Scientific Computing (SISC), 2010.
  4. Conf
    A Hypergraph-Partitioning Approach for Coarse-Grain Decomposition
    Ümit V. Çatalyürek, and Cevdet Aykanat
    In ACM/IEEE SC2001, 2001.
  5. Conf
    A Fine-Grain Hypergraph Model for 2D Decomposition of Sparse Matrices
    Ümit V. Çatalyürek, and Cevdet Aykanat
    In Proceedings of 15th International Parallel and Distributed Processing Symposium (IPDPS), 2001.
  6. PhD
    Hypergraph Models for Sparse Matrix Partitioning and Reordering
    Ümit V. Çatalyürek
    PhD thesis, Bilkent University, Computer Engineering and Information Science , 1999.
  7. JRNL
    Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication
    Ümit V. Çatalyürek, and Cevdet Aykanat
    IEEE Transactions on Parallel and Distributed Systems, 1999.
  8. Tech
    PaToH: A Multilevel Hypergraph Partitioning Tool, Version 3.0
    Ümit V. Çatalyürek, and Cevdet Aykanat
    Bilkent University, Department of Computer Engineering , 1999.

Zoltan:

Zoltan, developed and maintained by Sandia National Laboratories, is a toolkit for load balancing and parallel data management. I had the pleasure of collaborating with the Zoltan team. As an outcome of this collaboration we developed a parallel multilevel hypergraph partitioning algorithm, as well as distance-1 and distance-2 coloring algorithms. Zoltan release v2.0 (and later) includes the implementation of these algorithms and its source code is distributed under the GNU Lesser General Public License.

More information and the distribution of Zoltan can be found at the Zoltan project web site.