Evgenii B. Rudnyi, 2008, (c) All rights reserved
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 79171x79171 with ~ 2.2 106 nonzeros in its half.
| method | time to reorder, s | nnz in factor | time to factor, s |
| genmmd | 1.9 | 130 106 | 1166 |
| md | 4.0 | 160 106 | 1684 |
| mmd | 4.0 | 127 106 | 1135 |
| amd | 1.4 | 127 106 | 1135 |
| metis | 17.1 | 47 106 | 239 |
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: How to Install Cygwin
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
Please post your comments, questions, suggestions to the discussion group at http://groups.google.com/group/matrixprogramming.