When solving a system of linear equations with a sparse matrix by the direct method, it is crucial to run a reordering algorithm to reduce fill-in in the factor. Without this, it just does not work.

METIS is a reordering algorithm developed by Prof Karypis at the University of Minnesota – Karypis Lab. It is just phenomenal and from what I see all the sparse direct solvers use it. Once I have compared different rerodering algorithms included with TAUCS for a symmetric matrix 79171×79171 with ~ 2.2 10⁶ nonzeros in its half.

As one can see, METIS takes more time than other rerodering algorithms but then the factor has much less nonzeros and as a result it is takes much less time to compute it and it takes also much less memory. I should note that these tests have been done on 450 MHz Sun and time today should be considered as relative.

METIS is pretty easy to compile. Just run make and that’s it. I do not remember any problem in this respect. If you use Microsoft Visual C++, then the simplest way is probably to use GNU Make

1) Install Cygwin with GNU Make.

2) Replace Makefile.in in the METIS root directory, modife compiler flags as necessary.

3) Replace Makefile and metis.h in lib.

4) cd lib; make should produce libmetis.lib.

I have been working for long time with METIS version 4. Now at the Karypis Lab site there is an alpha version 5 but I have not tried it yet.

METIS is written in C by using int and when one uses a solver on a 64-bit system that employs 8-byte integers this must be changed. Recently I have compiled MUMPS with -i8 and this was exactly this case. The newest version seems have an option to compile METIS with long but it is still alpha so I have decided to hack METIS 4 by myself. My experience in this respect is written below.

Compiling METIS 4 for 64-bit computing with long int