Office for Technology Commercialization
http://www.research.umn.edu/techcomm
612-624-0550

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

Technology #98039

Questions about this technology? Ask a Technology Manager

Download Printable PDF

Image Gallery
Various ways to coarsen a graph partitionVarious ways to coarsen a graph partitionVarious ways to coarsen a graph partitionFinite element analysis with heavy-edge matchingFinite element analysis with random matching Contact/Impact simulation with finite element meshContact/Impact simulation with finite element meshContact/Impact simulation with finite element mesh
Categories
Researchers
George Karypis, PhD
Professor, Department of Computer Science and Engineering, College of Science and Engineering
External Link (www.cs.umn.edu)
Managed By
Andrew Morrow
Technology Licensing Officer

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.

MN-IP Try and Buy
This technology is available via a standard negotiated license agreement. Contact Andrew Morrow for specific details.

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.