Serial Graph Partitioning, Finite Element Analysis and Fill Order Reduction for Sparse Matrices

Graph Partitioning, Finite Element Analysis and Fill Order Reduction

METIS is a set of serial programs for graph partitioning, finite element analysis, and fill order reduction for sparse matrices. The algorithms implemented in METIS are based on the multilevel recursive-bisection, multilevel k-way, and multi-constraint partitioning schemes developed in the University of Minnesota’s Digital Technology Center (DTC) labs.

High Quality Graph Partitions

METIS produces graph partitions that are consistently better than those produced by other widely used algorithms. Graph partitions produced by METIS are consistently 10% to 50% better than those produced by spectral partitioning algorithms.

Fast Finite Element Analysis

Extensive testing has proven METIS to be one to two orders of magnitude faster than other widely used graph partitioning algorithms. Graphs with over 1,000,000 vertices can be partitioned in 256 parts in just a few seconds on current generation workstations and PCs.

Low Fill Orderings

The low fill orderings produced by METIS are significantly better than those produced by other finite element analysis algorithms – including those produced by Multiple Minimum Degree. For many types of problems arising in scientific computations and linear programming, METIS is able to reduce the storage and computational requirements of sparse matrix factorization by up to an order of magnitude. Unlike the finite element analysis produced by Multiple Minimum Degree, the elimination trees produced by METIS are suitable for parallel direct factorization. Lastly, METIS’ efficiency allows it to reorder matrices with over 200,000 rows in just a few seconds on current generation workstations and PCs.

Expand On The Functionality of METIS

hMETIS expands on the functionality of METIS with a set of programs for partitioning hypergraphs such as those of Very Large Scale Integration (VLSI) circuits. The algorithms implemented by hMETIS are based on the multilevel hypergraph partitioning schemes developed in the University of Minnesota’s Digital Technology Center (DTC) labs.

ParMETIS expands on the functionality of METIS with routines that are well suited for parallel Adaptive Mesh Refinement (AMR) computations and large scale numeric simulations.

FEATURES AND BENEFITS OF METIS PARTITIONING ALGORITHM:

• High quality graph partitions
• Finite element analysis 10-50% better than that of competitors
• Graph partitions with over 1,000,000 vertices divided into 256 parts in just a few seconds

Phase of Development Tested, complete, ready for deployment.