A Software Package of MultiLevel Block ILU Preconditioning Techniques for
Solving General Sparse Linear Systems
Preliminary Examination Version, November 1997
Latest Update, March 18, 1998
Department of Computer Science and Engineering
University of Minneapolis
Minneapolis, MN 55455, USA
Department of Computer Science
University of Kentucky
Lexington, KY 405060047, USA
Introduction to BILUM
BILUM is a set of programs designed for solving general sparse linear systems by
using Krylov subspace methods preconditioned by some multilevel block
ILU (BILUM) preconditioning techniques. BILUM combines the benefits of
generality and robustness of ILU preconditioning techniques with those of
gridindependent
convergence of multigrid methods. The multilevel algorithms implemented by
BILUM are based on the block independent set ordering and multielimination
techniques. At each level, a block independent set is found by some greedy
algorithms such that each block is decoupled with other blocks in the
independent set. There is an inherited parallelism associated with this
technique. The coefficient matrix is then reordered according to the
independent set ordering and an approximate block ILU factorization is
performed with a reduced system of smaller size. The multilevel structure
is constructed by recursively applying the
above idea to the approximate Schur complement (the reduced system) until
the last reduced system is small enough to be solved by a direct method
or a preconditioned iterative method.
The advantages of BILUM compared to other more traditional incomplete LU
(ILU) factorizations are the followings:

Robustness

Experiments on a large number of test matrices arising in various domains
including finite element methods, finite difference methods, computational
fluid dynamics, highorder discretized convectiondiffusion equations,
HarwellBoeing collections, FIDAP matrices, Simon matrices, Wigto matrices,
driven cavity problems, have shown that BILUM is much more robust than
traditional ILUtype preconditioners. For many hard problems, the improved
robustness and faster convergence rate are accompanied by less memory
consumption, which is a surprising contrary to many socalled robust
preconditioning techniques.

Scalability

Gridindependent convergence is almost synonymous with multigrid methods.
In fact, without some multilevel or multiscale implementation, the
convergence rate of
an iterative method tends to decrease as the size of the problems increases.
This is a very undesirable feature as iterative methods are usually designed to
solve large scale problems. However,
experiments on certain type of problems have shown that BILUM demonstrates
nearly gridindependent convergence. For some convectiondiffusion problems,
its convergence rate can be shown to be nearly independent of the strength of
the convection or the Reynolds number.

Fast Convergence

For many problems, BILUM is much faster than ILU(0), ILUT or other popular
preconditioners and uses less memory. The interesting thing is that the
construction of BILUM can be economic, i.e., the preconditioner
construction time and the solution time are of the same order. This is
in contrast to many ``modern'' preconditioners whose constructions are
many times more expensive than their solution time. Hence, BILUM is more
suitable as a general purpose preconditioning technique.

Inherited Parallelism

Due to its construction, all blocks in an independent set can be processed
in parallel. Inherited parallelism can be extracted in both BILUM
construction and BILUM application phases. Although the current version of
BILUM is not a parallel code, its implementation on vector machines such as
Cray C90 benefits from the inherited vectorization and parallelism. In
addition, BILUM provide a general framework which encapsulates both
coarsegrain and finegrain domain decomposition approaches.

References

Multilevel preconditioning techniques are, to some extend,
related to the hierarchical
basis multigrid in finite element analysis, the recursive redblack
factorization in finite difference analysis, multigrid methods with
matrixdependent transfer operators, algebraic multigrid methods, and
blackbox multigrid methods. However, most other methods need
grid information from the underlying partial differential equations.
BILUM is constructed purely algebraically and does not assume any
property from the coefficient matrix and needs no grid information.
Here is a list of references that
are related to multilevel preconditioning techniques.

Authorship and Acknowledgment

BILUM was written by
Yousef Saad and
Jun Zhang
under the support of
National Science Foundation and National Institute of Standards and
Technology as an effort to create parallel scalable libraries for
large scale applications. However, BILUM does not reflect the official
view of either National
Science Foundation or National Institute of Standards and Technology.
The authors have also benefited from Edmond Chow and Kesheng Wu for
their helpful discussions and professional advice.
Obtaining BILUM
Downloading a preliminary examination version of BILUM
is as easy as just pointing your web browser to
BILUM
and click it.
The software package of BILUM contains a number of files
written entirely in Fortran 77. It utilizes some routines from
LAPACK and SPARSKIT. BILUM is portable
on most Unix systems that have a Fortran 77 compiler.
It has been extensively tested on SGI, SUN and Cray C90 machines.
The distribution of BILUM consists of a Unix gziped tar file whose size is
approximately 0.16 megabyte.
After downloading BILUM you need to uncompress it and untar it. This
is achieved by executing the following command:
gunzip bilum.tar.gz
tar xvf bilum.tar
At this point you should have a directory named BILUM.
This directory contains the main makefile and several subdirectories.
Instructions are contained in README file and test drivers are contained
in a subdirectory TESTRUN. There are two test problems with test
results obtained on three types of machines and the test results can be
found in a subdirectory TESTRUN/SAMPLE.
Version Update
We keep updating and improving BILUM. This web page will keep the
uptodate version. For major modifications and the relation to the
old version, please check the
update file.
There is a Belorussian translation of
this page on BILUM software. Thanks to the efforts of Bohdan Zograf.
Contact Information
Even though BILUM contains no known bugs, it does not mean that all
of its bugs have been found and fixed. If you find any problems, please send
an email to jzhang@cs.uky.edu,
with a brief description of the problem you have found.
Also if you have any comments regarding BILUM or any suggestions for
additional functionality that you want to see being incorporated in future
releases of BILUM, send them to
jzhang@cs.uky.edu.
If you want to keep tracking of the continuous development of BILUM,
please put the URL address:
http://www.cs.uky.edu/~jzhang/bilum.html
in your collection of bookmarks.
Disclaimer
This is a preliminary examination version of BILUM. Permission is granted
for using the software for the purpose of examination. Users are
not permitted to distribute the software.
This software package comes with no warranty. The authors
are not liable for any loss/damage or inconvenience caused
in the use of this software package or any modification thereof.
You use it at your own risk.
This page is created by
Jun Zhang
originally created: Friday, October 13, 1997.
Last modified: Monday, August 22, 2011.