PaToH Experimental Results

Comparison of hMeTiS and PaToH on 134 hypergraphs arising from different areas, Sparse-Matrix Vector Multiplication, LP, VLSI (including ISPD98).

First table is the absolute value resuls (beware it is big :)

Second table displays the normalized performance results wrt to those of hMeTiS.

Here is the summary table (yes this one is really small :)

	PaToH param=SPEED				PaToH param=DEFAULT				PaToH param=QUALITY
	Cut Size			Exec	Cut Size			Exec	Cut Size			Exec
	min	max	avg	Time	min	max	avg	Time	min	max	avg	Time
Others	1.01	2.25	1.12	0.07	1.01	0.88	1.00	0.15	1.00	0.88	0.99	0.61
LP	0.98	1.39	1.05	0.15	0.96	0.95	0.94	0.25	0.95	0.91	0.91	0.88
Matrix	1.01	1.46	1.13	0.16	1.01	1.00	1.00	0.25	1.00	0.94	0.97	0.78
VLSI	1.05	1.43	1.22	0.11	1.03	1.05	1.04	0.27	1.00	0.98	0.99	1.04
Overall	1.01	1.45	1.13	0.14	0.99	0.99	0.99	0.25	0.98	0.94	0.95	0.89

As seen in the table, if you accept 13% worse results you can use PaToH's "SPEED" settings and it will run about 8 times faster than hMeTiS. On the overall average, the "DEFAULT" settings produce partitionings that are comparable with hMeTiS. With this settings PaToH runs about 4 times faster than hMeTiS. In general "QUALITY" settings gives a little better partitionings at the expense of slower execution.

Please also note that, in terms of execution time, performance gap between PaToH and hMeTiS increases with the increasing problem size in favor of PaToH.