Keywords: environmental modelling, parse linear systems of equations, reordering, preconditioning, Krylov subspace methods.

Nowadays, environmental problems are a research objective of scientifics and engineers. The numerical resolution of these problems requires the formulation of mathematical models. The application of a discretization technique for solving these models (finite element, finite differences, finite volume, ...) leads to a linear systems of equations, which is usually large and sparse. On the other hand, these problems are time dependent. This means to apply also a time discretization scheme, and thus, to solve such a linear system in each time step. So, the size of the matrices and the high number of linear systems that must be solved, make the resolution of large and sparse linear systems an essential part for an efficient simulation.

Let us consider,

where is a sparse, large and non-singular matrix. The first question is if a direct or an iterative resolution is better. 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.

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 factorization 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].

On the other hand, preconditioning techniques improve the convergence of iterative methods. Here, we study some standard preconditioners, in particular, Jacobi, SSOR, ILU and sparse approximate inverse.

In addition, we study the three groups of Krylov subspace methods (see [4,5]): orthogonalisation, biorthogonalization and normal equation methods. For the case of symmetric linear systems of equations, the use of Conjugate Gradient method [6] is generally accepted as the best choice. It is based on the Lanczos orthogonalization method which is a simplification of Arnoldi algorithm for symmetric linear systems. Among orthogonalization methods for nonsymmetric linear systems that apply the Arnoldi algorithm [7], we study the Generalized Minimum Residual method (GMRES) [8]. We also study the Biconjugate Gradient Stabilized method (Bi-CGSTAB) [9] and its quasi-minimun residual version, the QMRCGSTAB algorithm [10].

1

M. Benzi, D.B. Szyld, A. van Duin, "Orderings for incomplete factorization preconditioning of nonsymmetric problems", SIAM J. Sci. Comput., 20, 5, 1652-1670, 1999. doi:10.1137/S1064827597326845

2

L.C. Dutto, "The Effect of Ordering on Preconditioned GMRES Algorithm", Int. Jour. Num, Meth. Eng., 36, 457-497, 1993. doi:10.1002/nme.1620360307

3

E. Flórez, M.D. García, L. González, G. Montero, "The effect of orderings on sparse approximate inverse preconditioners for non-symmetric problems", Adv. Engng. Software, 33, 7-10, 611-619, 2002. doi:10.1016/S0965-9978(02)00070-4

4

G. Montero, G. Winter, A. Suárez, M. Galán, D. García, "Contribution to Iterative Methods for Nonsymmetric Linear Systems: GMRES, BCG and QMR Type Methods", in Computational Methods and Neural Networks. Part Two: Computational Methods, M. Sambandhamy & M.P. Bekakos, Eds., Dynamic Publishers, Inc., 97-128, 1999.

5

N.M. Nachttigal, S.C. Reddy, L.N. Trefethen, "How Fast Are Nonsymmetric Matrix Iterations?", SIAM J. Matr. Anal. Appl., 13, 3, 796-825, 1992. doi:10.1137/0613049

6

M.R. Hestenes, E. Stiefel, "Methods of Conjugate Gradients for Solving Linear Systems", Jour. Res. Nat. Bur. Sta., 49, 6, 409-436, 1952.

7

W.E. Arnoldi, "The Principle of Minimized Iteration in the Solution of the Matrix Eingenvalue Problem", Quart. Appl. Math., 9, 17-29, 1951.

8

Y. Saad, M. Schultz, "GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems", SIAM J. Sci. Statist. Comput., 7, 856-869, 1986. doi:10.1137/0907058

9

H.A. van der Vorst, "Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems", SIAM J. Sci. Comput., 13, 631-644, 1992. doi:10.1137/0913035

10

T.F. Chan, E. Gallopoulos, V. Simoncini, T. Szeto, C.H. Tong, "A Quasi-Minimal Residual Variant of the Bi-CGSTAB Algorithm for Nonsymmetric Systems", SIAM J. Sci. Statist. Comput., 15, 338-247, 1994. doi:10.1137/0915023

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)