METIS – Fill-reducing Matrix Ordering

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
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.

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


Comments

11 responses to “METIS – Fill-reducing Matrix Ordering”

Comments are now closed
  1. matt says:

    Hello

    When i am in step 4 and make, it output error like this

    LIB : fatal error LNK1181: cannot open input file ‘../libmetis.a’
    make: *** [../libmetis.a] Error 157

    Is there anything wrong with my setting?

    Thank you very much

    Matt

  2. matt says:

    Sorry, my mistake.

    I have got it.

    Matt

  3. I am glad to hear that you have done it. The message says that the librarian considers ../libmetis.a as an input file. This happens if there is a space between -out: and the file name. MS lib does not like it.

  4. kyewong says:

    Hi Rudnyi ,thanks for ur sharing
    However, i still cannot produce libmetis.lib using GNU Make under winxp.
    I first used vs2008 to produce make.exe
    then i copied the three files to the folders as you said.
    then i switch to the “Lib” folder and entered “make”
    An error occurs that:

    cl -D__VC__ -02 -MD -I. -c coarsen.c
    process_begin: CreateProces failed.
    make : The system cannot find the file specified.
    make.exe: *** [coarsen.o] Error 2

  5. The message says that either make cannot find cl or cl cannot find the file. Just check if you can run cl from the command line and if the file is there. It is a good idea first to try to run the command manually.

  6. kyewong says:

    Hi Rudnyi,thanks for the reply and I’ve fixed the problem by producing make from GNU make and running it in vs2008 command prompt, the “cl” can work now.
    However, I have the same problem as matt: There is a link error:
    fatak error LNK1181: cannot open input file ‘../libmetis.a’
    make: *** [../libmetis.a] Error 1181

    And I try to delete the space between “-out:$@” and “$(OBJS)” in line 25 of Makefile.txt, it still does not work.
    Is it because of my misunderstandings on what you have said? Could you please tell me the details of how to modify the makefile files in Windows for Visual Studio users please?

  7. kyewong says:

    Sorry my mistake too…
    Windows automatically renamed the “Makefile” you provided into “Makefile.txt”, I did not notice that and just copy the “Makefile.txt” into the folder “Lib”, and everything went wrong…
    Now I’ve successfully built “libmetis.lib”!
    Thanks very much!

  8. sadeghi says:

    Hi guys,
    I appreciate if someone can help me with following questions:

    1. when I am downloading Cygwin do I have to change the default package to include GNU Make? if yes, what should I add to the package.

    2. In step 4, how can I produce libmetis.lib. should I call GNU Make from Cygwin terminal? I never used Cygwin or GNU Make before. I appreciate if you can tell me detailed producer in step 4.

  9. 1. Yes, you need to to it separately:

    http://matrixprogramming.com/2008/03/installcygwin

    2. If everything goes well, make will make it for you. You have just type make and press enter.

    You may also want to look at

    http://matrixprogramming.com/2008/03/usingmake

  10. vahid says:

    Hi,

    I have a problem in step 4. when I type make and press enter it gives me the following error:

    cl -D__VC__ -O2 -MD -I. -c coarsen.c
    make: cl: Command not found
    make: *** [coarsen.obj] Error 127

    I tried make command for the example in: http://matrixprogramming.com/2008/03/usingmake and it works fine.

    I can not find what is the problem in METIS library case.

    Thanks!

  11. vahid says:

    My guess is it can not find the compiler. In Makefile.in file, do I have to change the following part?
    # Which compiler to use
    CC = cl -D__VC__