National High-Performance Software Exchange
Software Catalog

Back to the NHSE Software Catalog

METIS

Abstract
Experiments on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI, and transportation show that METIS produces partitions that are consistently better than those produced by other widely used algorithms. The partitions produced by METIS are consistently 10% to 50% better than those produced by spectral partitioning algorithms. Experiments on a wide range of graphs has shown that METIS is one to two orders of magnitude faster than other widely used partitioning algorithms. Graphs with over 1,000,000 vertices can be partitioned in 256 parts in under 20 seconds on a Pentium Pro personal computer. The fill-orderings produced by METIS are significantly better than those produced by other widely used algorithms including multiple minimum degree. For many classes 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. Moreover, unlike multiple minimum degree, the elimination trees produced by METIS are suitable for parallel direct factorization. Furthermore, METIS is able to compute these orderings very fast. Matrices with over 200,000 rows can be reordered in just a few seconds on current generation workstations and PCs.
DateOfInformation
Mon Sep 21 12:53:46 1998
Domain
Grid Generation!Hexahedral!Unstructured
Name
METIS
Version
4.0
VersionDate
September 1998
Webpage
http://www.cs.umn.edu/~metis
ContactIs
METIS Support
Metis Support

Meta Data URL from which this entry was created:
http://www.nhse.org/rib/repositories/CEWES_Grid_Gen/objects/Asset/metis.html
nhse-tech@nhse.org