# Applying approximate LU-factorizations as preconditioners in eight iterative methods for solving systems of linear algebraic equations

Zahari Zlatev; Krassimir Georgiev

Open Mathematics (2013)

- Volume: 11, Issue: 8, page 1510-1530
- ISSN: 2391-5455

## Access Full Article

top## Abstract

top## How to cite

topZahari Zlatev, and Krassimir Georgiev. "Applying approximate LU-factorizations as preconditioners in eight iterative methods for solving systems of linear algebraic equations." Open Mathematics 11.8 (2013): 1510-1530. <http://eudml.org/doc/269392>.

@article{ZahariZlatev2013,

abstract = {Many problems arising in different fields of science and engineering can be reduced, by applying some appropriate discretization, either to a system of linear algebraic equations or to a sequence of such systems. The solution of a system of linear algebraic equations is very often the most time-consuming part of the computational process during the treatment of the original problem, because these systems can be very large (containing up to many millions of equations). It is, therefore, important to select fast, robust and reliable methods for their solution, also in the case where fast modern computers are available. Since the coefficient matrices of the systems are normally sparse (i.e. most of their elements are zeros), the first requirement is to efficiently exploit the sparsity. However, this is normally not sufficient when the systems are very large. The computation of preconditioners based on approximate LU-factorizations and their use in the efforts to increase further the efficiency of the calculations will be discussed in this paper. Computational experiments based on comprehensive comparisons of many numerical results that are obtained by using ten well-known methods for solving systems of linear algebraic equations (the direct Gaussian elimination and nine iterative methods) will be reported. Most of the considered methods are preconditioned Krylov subspace algorithms.},

author = {Zahari Zlatev, Krassimir Georgiev},

journal = {Open Mathematics},

keywords = {Iterative methods; Linear sysytems of equations; Preconditioners; iterative methods; systems of linear equations; preconditioners; approximate LU-factorizations; numerical results; Gaussian elimination; Krylov subspace algorithms},

language = {eng},

number = {8},

pages = {1510-1530},

title = {Applying approximate LU-factorizations as preconditioners in eight iterative methods for solving systems of linear algebraic equations},

url = {http://eudml.org/doc/269392},

volume = {11},

year = {2013},

}

TY - JOUR

AU - Zahari Zlatev

AU - Krassimir Georgiev

TI - Applying approximate LU-factorizations as preconditioners in eight iterative methods for solving systems of linear algebraic equations

JO - Open Mathematics

PY - 2013

VL - 11

IS - 8

SP - 1510

EP - 1530

AB - Many problems arising in different fields of science and engineering can be reduced, by applying some appropriate discretization, either to a system of linear algebraic equations or to a sequence of such systems. The solution of a system of linear algebraic equations is very often the most time-consuming part of the computational process during the treatment of the original problem, because these systems can be very large (containing up to many millions of equations). It is, therefore, important to select fast, robust and reliable methods for their solution, also in the case where fast modern computers are available. Since the coefficient matrices of the systems are normally sparse (i.e. most of their elements are zeros), the first requirement is to efficiently exploit the sparsity. However, this is normally not sufficient when the systems are very large. The computation of preconditioners based on approximate LU-factorizations and their use in the efforts to increase further the efficiency of the calculations will be discussed in this paper. Computational experiments based on comprehensive comparisons of many numerical results that are obtained by using ten well-known methods for solving systems of linear algebraic equations (the direct Gaussian elimination and nine iterative methods) will be reported. Most of the considered methods are preconditioned Krylov subspace algorithms.

LA - eng

KW - Iterative methods; Linear sysytems of equations; Preconditioners; iterative methods; systems of linear equations; preconditioners; approximate LU-factorizations; numerical results; Gaussian elimination; Krylov subspace algorithms

UR - http://eudml.org/doc/269392

ER -

## References

top- [1] Alexandrov V.N., Owczarz W., Thomson P.G., Zlatev Z., Parallel runs of a large air pollution model on a grid of Sun computers, Math. Comput. Simulation, 2004, 65(6), 557–577 http://dx.doi.org/10.1016/j.matcom.2004.01.022
- [2] Alexandrov V., Sameh A., Siddique Y., Zlatev Z., Numerical integration of chemical ODE problems arising in air pollution models, Environmental Modeling and Assessment, 1997, 2(4), 365–377 http://dx.doi.org/10.1023/A:1019086016734
- [3] Arioli M., A stopping criterion for the conjugate gradient algorithms in a finite element method framework, Numer. Math., 2004, 97(1), 1–24 http://dx.doi.org/10.1007/s00211-003-0500-y Zbl1048.65029
- [4] Arioli M., Loghin D., Wathen A.J., Stopping criteria for iterations in finite element methods, Numer. Math., 2005, 99(3), 381–410 http://dx.doi.org/10.1007/s00211-004-0568-z Zbl1069.65124
- [5] Arioli M., Noulard E., Russo A., Stopping criteria for iterative methods: applications to PDE’s, Calcolo, 2001, 38(2), 97–112 http://dx.doi.org/10.1007/s100920170006 Zbl1072.65045
- [6] Axelsson O., Kaporin I., Error norm estimation and stopping criteria in preconditioned conjugate gradient iterations, Numer. Linear Algebra Appl., 2001, 8(4), 265–286 http://dx.doi.org/10.1002/nla.244 Zbl1051.65024
- [7] Demmel J.W., Applied Numerical Linear Algebra, Society for Industrial and Applied Mathematics, Philadelphia, 1997 http://dx.doi.org/10.1137/1.9781611971446
- [8] Eirola T., Nevanlinna O., Accelerating with rank-one updates, Linear Algebra Appl., 1989, 121, 511–520 http://dx.doi.org/10.1016/0024-3795(89)90719-2 Zbl0683.65018
- [9] Freund R.W., A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM J. Sci. Stat. Comput., 1993, 14(2), 470–482 http://dx.doi.org/10.1137/0914029 Zbl0781.65022
- [10] Gallivan K., Sameh A., Zlatev Z., A parallel hybrid sparse linear system solver, Computing Systems in Engineering, 1990, 1(2–4), 183–195 http://dx.doi.org/10.1016/0956-0521(90)90006-7
- [11] Gallivan K.A., Sameh A.H., Zlatev Z., Comparison of ten methods for the solution of large and sparse linear algebraic systems, In: Numerical Methods and Applications, Lecture Notes in Comput. Sci., 2542, Springer, Berlin, 2003, 24–35 http://dx.doi.org/10.1007/3-540-36487-0_3 Zbl1032.65030
- [12] Golub G.H., Meurant G., Matrices, moments and quadrature II; How to compute the norm of the error in iterative methods, BIT, 1997, 37(3), 687–705 http://dx.doi.org/10.1007/BF02510247 Zbl0888.65050
- [13] Golub G.H., Strakoš Z., Estimates in quadratic formulas, Numer. Algorithms, 1994, 8(2–4), 241–268 http://dx.doi.org/10.1007/BF02142693 Zbl0822.65022
- [14] Higham N.J., Accuracy and Stability of Numerical Algorithms, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, 2002 http://dx.doi.org/10.1137/1.9780898718027 Zbl1011.65010
- [15] Meier Yang U., Gallivan K.A., A new family of block methods, Appl. Numer. Math., 1999, 30(2–3), 155–173 http://dx.doi.org/10.1016/S0168-9274(98)00108-1 Zbl0930.65023
- [16] Meurant G., The computations of bounds for the norm of the error in the conjugate gradient algorithm, Numer. Algorithms, 1997, 16(1), 77–87 http://dx.doi.org/10.1023/A:1019178811767 Zbl0897.65026
- [17] Meurant G., Numerical experiments in computing bounds for the norm of the error in the preconditioned conjugate gradient algorithm, Numer. Algorithms, 1999, 22(3–4), 353–365 http://dx.doi.org/10.1023/A:1019179412560
- [18] Meurant G., The Lanczos and conjugate gradient algorithms, Software Environ. Tools, 19, Society for Industrial and Applied Mathematics, Philadelphia, 2006 Zbl1113.65032
- [19] Saad Y., Schultz M.H., GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 1986, 7(8), 856–869 Zbl0599.65018
- [20] Simoncini V., Szyld D.B., Recent computational developments in Krylov subspace methods for linear systems, available at http://www.dm.unibo.it/~simoncin/survey.pdf Zbl1199.65112
- [21] Sonneveld P., CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 1989, 10(1), 36–52 http://dx.doi.org/10.1137/0910004 Zbl0666.65029
- [22] Strakoš Z., Tichý P., On error estimation by conjugate gradient method and why it works in finite precision computations, Electron. Trans. Numer. Anal., 2002, 13, 56–80 Zbl1026.65027
- [23] Strakoš Z., Tichý P., Error estimation in preconditioned conjugate gradients, BIT, 2005, 45(4), 789–817 http://dx.doi.org/10.1007/s10543-005-0032-1 Zbl1095.65029
- [24] Trefethen L.N., Bau D., Numerical Linear Algebra, Society for Industrial and Applied Mathematics, Philadelphia, 1997 http://dx.doi.org/10.1137/1.9780898719574 Zbl0874.65013
- [25] Vinsome P.K.W., Orthomin, an iterative method for solving sparse sets of simultaneous linear equations, In: SPE Symposium on Numerical Simulation of Reservoir Performance, February 19–20, 1976, Los Angeles, Society of Petroleum Engineers, 1976, #5729–MS
- [26] van der Vorst H.A., Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 1992, 13(2), 631–644 http://dx.doi.org/10.1137/0913035 Zbl0761.65023
- [27] Vuik C., van der Vorst H.A., A comparison of some GMRES-like methods, Linear Algebra Appl., 1992, 160, 131–162 http://dx.doi.org/10.1016/0024-3795(92)90444-F Zbl0749.65027
- [28] Zlatev Z., On some pivotal strategies in Gaussian elimination by sparse technique, SIAM J. Numer. Anal., 1980, 17(1), 18–30 http://dx.doi.org/10.1137/0717003 Zbl0427.65016
- [29] Zlatev Z., Use of iterative refinement in the solution of sparse linear systems, SIAM J. Numer. Anal., 1982, 19(2), 381–399 http://dx.doi.org/10.1137/0719024 Zbl0485.65022
- [30] Zlatev Z., Computational Methods for General Sparse Matrices, Math. Appl., 65, Kluwer, Dordrecht, 1991 http://dx.doi.org/10.1007/978-94-017-1116-6
- [31] Zlatev Z., Computer Treatment of Large Air Pollution Models, Springer, Berlin, 1995 http://dx.doi.org/10.1007/978-94-011-0311-4
- [32] Zlatev Z., Impact of future climatic changes on high ozone levels in European suburban areas, Climatic Change, 2010, 101, 447–483 http://dx.doi.org/10.1007/s10584-009-9699-7
- [33] Zlatev Z., Havasi Á., Faragó I., Influence of climatic changes on pollution levels in Hungary and surrounding countries, Atmosphere, 2011, 2(3), 201–221 http://dx.doi.org/10.3390/atmos2030201
- [34] Zlatev Z., Moseholm L., Impact of climate changes on pollution levels in Denmark, Ecological Modelling, 2008, 217(3–4), 305–319 http://dx.doi.org/10.1016/j.ecolmodel.2008.06.030
- [35] Sparse Matrix Market, available at http://math.nist.gov/MatrixMarket/index.html

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.