Computational & Technology Resources
an online resource for computational,
engineering & technology publications 

Computational Science, Engineering & Technology Series
ISSN 17593158 CSETS: 12
PROGRESS IN ENGINEERING COMPUTATIONAL TECHNOLOGY Edited by: B.H.V. Topping, C.A. Mota Soares
Chapter 5
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", SaxeCoburg Publications, Stirlingshire, UK, Chapter 5, pp 81109, 2004. doi:10.4203/csets.12.5
Keywords: sparse linear systems of equations, iterative solvers, Krylov subspace methods, preconditioning, reordering.
Summary
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 nonsingular 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 fillin 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 [6]. However, for nonsymmetric 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 [9], we study the Generalised Minimum Residual method (GMRES) [10]. On the other hand, we study the Biconjugate Gradient Stabilised method (BiCGSTAB) [11] and its quasiminimal residual variant, the QMRCGSTAB algorithm [12]. Besides, we consider the use of the Leastsquare QR method (LSQR) [13] based on the normal equation. References
purchase the fulltext of this chapter (price £20)
go to the previous chapter 
