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 binary distributions of PaToH for different architectures.
- Linux: 32-bit x86-based, 64-bit x86-based
- Mac OS X 10.6: 32-bit x86-based , 64-bit x86-based
- Mac OS X 10.5: 32-bit x86-based , 64-bit x86-based (last update: Oct 9, 2009)
- Linux: 64-bit IA64-based (last update: Nov 24, 2008)
- Mac OS X: 32-bit PowerPC (last update: May 12, 2006)
- Sun Solaris (last update: May 12, 2006)
- IBM AIX (last update: Nov 11, 2004)
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.
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.
- 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.
Data & Results
- Exp-1: ISPD98: 2% actual area results comparison with hMeTiS and UCLA MLPart
- Exp-2: Comparison of hMeTiS and PaToH on 134 hypergraphs arising from different areas, Sparse-Matrix Vector Multiplication, LP, VLSI (including ISPD98).
- Integrated Data Placement and Task Assignment for Scientific Workflows in Clouds U.V. Catalyurek, K. Kaya, and B. Ucar. The Fourth International Workshop on Data Intensive Distributed Computing (DIDC 2011), in conjunction with the 20th International Symposium on High Performance Distributed Computing (HPDC 2011), Jun 8, 2011, to appear.
- A matrix partitioning interface to PaToH in MATLAB. B. Ucar, U.V. Catalyurek, and C. Aykanat. Parallel Computing, , Vol. 36, No. 5-6, pp. 254 - 272, Jun 2010.
- On scalability of hypergraph models for sparse matrix partitioning. B. Ucar and U.V. Catalyurek. Proceedings of the PDP 2010: 18th Euromicro International Conference on Parallel, Distributed and Network-Based Computing, 2010.
- On two-dimensional sparse matrix partitioning: Models, Methods, and a Recipe. U. Catalyurek, C. Aykanat and B. Ucar. SIAM Journal of Scientific Computing, Vol. 32, No. 2, pp. 656-683, 2010.
- A Hypergraph-Partitioning Approach for Coarse-Grain Decomposition. U. Catalyurek and C. Aykanat. ACM/IEEE SC2001, Denver, CO, November 2001. [ps] [pdf]
- A Fine-Grain Hypergraph Model for 2D Decomposition of Sparse Matrices. U. Catalyurek and C. Aykanat. Proceedings of International Parallel and Distributed Processing Symposium (IPDPS), 8th International Workshop on Solving Irregularly structured Problems in Parallel (Irregular 2001), San Francisco, April 2001. [ps] [pdf]
- Hypergraph Models for Sparse Matrix Partitioning and Reordering. Ü. V. Çatalyürek, Ph.D. thesis, Computer Engineering and Information Science Bilkent University, November 1999.
- Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication. U. Catalyurek and C. Aykanat. IEEE Transaction on Parallel and Distributed Systems, Vol. 10, No. 7, pp. 673-693, 1999. [ps] [pdf]
- Decomposing irregularly sparse matrices for parallel matrix-vector multiplications. U. Catalyurek and C. Aykanat. Lecture Notes in Computer Science, vol. 1117, pp. 75-86, 1996. [ps] [pdf]
- Decomposing linear programs for parallel solution. A. Pinar, U. Catalyurek, C. Aykanat, and M. Pinar. Lecture Notes in Computer Science, vol. 1041, pp. 473-482, 1996. [ps] [pdf]
- A hypergraph model for mapping repeated sparse matrix-vector product computations onto multicomputers. Ü. V. Çatalyürek and C. Aykanat, Proceedings of International Conference on High Performance Computing, HiPC ’95, Goa, India, December 1995. [ps] [pdf]