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

• Autorzy: Zahari Zlatev , Krassimir Georgiev
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Iterative methods; Linear sysytems of equations; Preconditioners

Kategorie tematyczne

• 65F10: Iterative methods for linear systems
• 65F50: Sparse matrices
• 65F05: Direct methods for linear systems and matrix inversion

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2013
• Tom: 11
• Numer: 8
• Strony: 1510-1530

Daty

wydano

2013-08-01

online

2013-05-22

Twórcy

autor

Zahari Zlatev

• Aarhus University

autor

Krassimir Georgiev

• Bulgarian Academy of Sciences

Bibliografia

• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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

Identyfikatory

DOI

10.2478/s11533-013-0248-2