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 106 nonzeros in its half.
|method||time to reorder, s||nnz in factor||time to factor, s|
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.
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.