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

Abstract

top
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.

How to cite

top

Zahari 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [18] Meurant G., The Lanczos and conjugate gradient algorithms, Software Environ. Tools, 19, Society for Industrial and Applied Mathematics, Philadelphia, 2006 Zbl1113.65032
  19. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [35] Sparse Matrix Market, available at http://math.nist.gov/MatrixMarket/index.html 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.