Incomplete orthogonal factorization preconditioning with given rotations
by
Andreas T. Papadopoulos
Oxford University Computing Laboratory

We explain, examine and present computational results for some incomplete Givens QR factorisation methods recently introduced as preconditioning methods by Z.-Z. Bai, I.S. Duff and A.J. Wathen (BIT 41(1), March 2001). Given a (sparse) nonsingular system of linear equations, these algorithms produce an incomplete QR-type factorization of the original matrix. The factors can be used as preconditioners for any standard iterative method applied either to the original system or to the associated system of normal equations, in order to speed up its convergence.

In this talk we will deal with two of these algorithms: the Incomplete Givens Orthogonalization (IGO-method), where the sparsity patterns of the resulting factors are determined by the sparsity pattern of the original matrix (dropping by position) and the Threshold IGO-method (TIGO-method) which drops entries dynamically by their magnitudes.

In the first part of the talk we will concentrate on programming aspects and difficulties related to the implementation of these algorithms: when we construct the factors using one of these methods we proceed by both columns and rows; thus, special matrix storage formats need to be adopted in order to avoid excessive computational time and memory requirements. The current program (written in Fortran 77) uses doubly-linked lists to this respect for reasons that can be effectively justified.

In the second part, we will identify classes of matrices for which these methods can produce useful preconditioners without too high requirements. A comparative analysis of the performance of these methods against standard general incomplete LU type factorizations will also be presented, having chosen Saad's SPARSKIT toolbox (also written in Fortran) as the opposing standard.

So far, we have identified two classes of problems for which the results seem promising: the general outcome is that as with the corresponding complete factorisations, the IGO methods display a robustness which is shown for some difficult matrices for which standard ILU methods fail. We will highlight a class of matrices arising from the modelling of advection-diffusion problems using stabilised finite element methods and also matrices arising in chemical kinetics (created by the FACSIMILE software package). We will also present results of GMRES and CGNE iteration for various matrices from the Matrix Market database, as well as matrices arising in other current research. Although these factorization methods (characterized by their robustness and stability) are intended for general systems, we have identified cases where the algorithms will fail, due to potential zeroes on the main diagonal. Techniques on how to remedy this will also be presented.

Date received: January 9, 2001