Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Computational Science, Engineering & Technology Series
PROGRESS IN ENGINEERING COMPUTATIONAL TECHNOLOGY
Edited by: B.H.V. Topping, C.A. Mota Soares
Resolution of Sparse Linear Systems of Equations: the RPK Strategy
G. Montero, R. Montenegro, J.M. Escobar and E. Rodríguez
Institute of Intelligent Systems and Numerical Applications in Engineering, University of Las Palmas de Gran Canaria, Spain
G. Montero, R. Montenegro, J.M. Escobar, E. Rodríguez, "Resolution of Sparse Linear Systems of Equations: the RPK Strategy", in B.H.V. Topping, C.A. Mota Soares, (Editors), "Progress in Engineering Computational Technology", Saxe-Coburg Publications, Stirlingshire, UK, Chapter 5, pp 81-109, 2004. doi:10.4203/csets.12.5
Keywords: sparse linear systems of equations, iterative solvers, Krylov subspace methods, preconditioning, reordering.
An over view of advanced techniques for solving large sparse linear systems of equations is presented. We are interested in the resolution of,
where is a sparse, large and non-singular matrix. The first question is if it is better a direct or an iterative resolution. The main disadvantage of direct methods compared with iterative ones is that the rounding errors are accumulated along the process of direct solving. Besides they require more memory requirements due to the fill-in effect. On the other hand, in non steady problems where there must be solved many similar systems of equations, iterative solvers may use the solution obtained in the previous time step as initial guess. So, nowadays it is preferred to use iterative methods in front of direct ones for large scale sparse linear systems of equations.
The reordering techniques based on graph theory, that were initially applied in the resolution by using direct methods, provide matrices with smaller band width or a sparsity pattern with a lower number of nonzero inner entries. However, this reduction may be used in order to improve the effect of incomplete factorisation preconditioners on the rate of convergence of iterative methods. The effect several reordering techniques on different Krylov subspace methods may be seen in [1,2,3,4,5].
Preconditioning techniques improve the convergence of iterative methods. Here, we study some standard preconditioners, in particular, Jacobi, SSOR, ILU and sparse approximate inverse.
On the other hand, some Krylov subspace methods for solving linear systems of equations are considered. For symmetric problems, the Conjugate Gradient method is proposed . However, for non-symmetric linear systems there exist several alternatives that may be classified into three family of methods: orthogonalisation, biorthogonalisation and normal equation methods (see [7,8]). Among orthogonalisation methods for nonsymmetric linear systems that apply the Arnoldi algorithm , we study the Generalised Minimum Residual method (GMRES) . On the other hand, we study the Biconjugate Gradient Stabilised method (Bi-CGSTAB)  and its quasi-minimal residual variant, the QMRCGSTAB algorithm . Besides, we consider the use of the Least-square QR method (LSQR)  based on the normal equation.
purchase the full-text of this chapter (price £20)