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. For both these methods, we rotate elements out in a column-wise fashion.
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. In particular, linked lists are employed in order to pin-point elements that need to be rotated out as efficiently as possible, whereas standard sparse vectors and compressed sparse row formats are used for updating the matrix during the factorization process.
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 as the opposing standard. We also compare them against incomplete QR factorizations we obtain when elimination via Givens rotations is performed in a row-wise fashion.
With few exceptions, ILU factorizations, when fine-tuned, tend to perform much better than any incomplete Givens QR preconditioner we mentioned above, the reason being that incomplete QR factorizations that are qualitatively good preconditioners are much more expensive to compute, mainly in terms of sparse matrix structures one has to maintain and update throughout the factorization process.
The situation is more interesting for rectangular systems arising from least squares problems. Here, an incomplete QR factorization can still be obtained for the original matrix. This factorization can then be used to precondition conjugate gradients for normal equations. We report some results for such problems using both our methods (column-wise Givens reduction) and the standard row-wise incomplete reduction via Givens rotations as preconditioner.