BILUM

A Software Package of Multi-Level Block ILU Preconditioning Techniques for Solving General Sparse Linear Systems

Preliminary Examination Version, November 1997
Latest Update, March 18, 1998

Introduction to BILUM

BILUM is a set of programs designed for solving general sparse linear systems by using Krylov subspace methods preconditioned by some multi-level block ILU (BILUM) preconditioning techniques. BILUM combines the benefits of generality and robustness of ILU preconditioning techniques with those of grid-independent convergence of multigrid methods. The multi-level algorithms implemented by BILUM are based on the block independent set ordering and multi-elimination 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 re-ordered according to the independent set ordering and an approximate block ILU factorization is performed with a reduced system of smaller size. The multi-level 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, high-order discretized convection-diffusion equations, Harwell-Boeing collections, FIDAP matrices, Simon matrices, Wigto matrices, driven cavity problems, have shown that BILUM is much more robust than traditional ILU-type 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 so-called robust preconditioning techniques.

Scalability

Grid-independent convergence is almost synonymous with multigrid methods. In fact, without some multi-level or multi-scale 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 grid-independent convergence. For some convection-diffusion 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 C-90 benefits from the inherited vectorization and parallelism. In addition, BILUM provide a general framework which encapsulates both coarse-grain and fine-grain domain decomposition approaches.

References

Multi-level preconditioning techniques are, to some extend, related to the hierarchical basis multigrid in finite element analysis, the recursive red-black factorization in finite difference analysis, multigrid methods with matrix-dependent transfer operators, algebraic multigrid methods, and black-box 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 multi-level 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 C-90 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 up-to-date version. For major modifications and the relation to the old version, please check the update file.

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 e-mail 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 page is created by Jun Zhang
originally created: Friday, October 13, 1997.
Last modified: Thursday, March 19, 1998.