Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 11 | 8 | 1510-1530
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
Języki publikacji
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.
Opis fizyczny
  • [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
  • [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
  • [3] Arioli M., A stopping criterion for the conjugate gradient algorithms in a finite element method framework, Numer. Math., 2004, 97(1), 1–24
  • [4] Arioli M., Loghin D., Wathen A.J., Stopping criteria for iterations in finite element methods, Numer. Math., 2005, 99(3), 381–410
  • [5] Arioli M., Noulard E., Russo A., Stopping criteria for iterative methods: applications to PDE’s, Calcolo, 2001, 38(2), 97–112
  • [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
  • [7] Demmel J.W., Applied Numerical Linear Algebra, Society for Industrial and Applied Mathematics, Philadelphia, 1997
  • [8] Eirola T., Nevanlinna O., Accelerating with rank-one updates, Linear Algebra Appl., 1989, 121, 511–520
  • [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
  • [10] Gallivan K., Sameh A., Zlatev Z., A parallel hybrid sparse linear system solver, Computing Systems in Engineering, 1990, 1(2–4), 183–195
  • [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
  • [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
  • [13] Golub G.H., Strakoš Z., Estimates in quadratic formulas, Numer. Algorithms, 1994, 8(2–4), 241–268
  • [14] Higham N.J., Accuracy and Stability of Numerical Algorithms, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, 2002
  • [15] Meier Yang U., Gallivan K.A., A new family of block methods, Appl. Numer. Math., 1999, 30(2–3), 155–173
  • [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
  • [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
  • [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
  • [21] Sonneveld P., CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 1989, 10(1), 36–52
  • [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
  • [24] Trefethen L.N., Bau D., Numerical Linear Algebra, Society for Industrial and Applied Mathematics, Philadelphia, 1997
  • [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
  • [27] Vuik C., van der Vorst H.A., A comparison of some GMRES-like methods, Linear Algebra Appl., 1992, 160, 131–162
  • [28] Zlatev Z., On some pivotal strategies in Gaussian elimination by sparse technique, SIAM J. Numer. Anal., 1980, 17(1), 18–30
  • [29] Zlatev Z., Use of iterative refinement in the solution of sparse linear systems, SIAM J. Numer. Anal., 1982, 19(2), 381–399
  • [30] Zlatev Z., Computational Methods for General Sparse Matrices, Math. Appl., 65, Kluwer, Dordrecht, 1991
  • [31] Zlatev Z., Computer Treatment of Large Air Pollution Models, Springer, Berlin, 1995
  • [32] Zlatev Z., Impact of future climatic changes on high ozone levels in European suburban areas, Climatic Change, 2010, 101, 447–483
  • [33] Zlatev Z., Havasi Á., Faragó I., Influence of climatic changes on pollution levels in Hungary and surrounding countries, Atmosphere, 2011, 2(3), 201–221
  • [34] Zlatev Z., Moseholm L., Impact of climate changes on pollution levels in Denmark, Ecological Modelling, 2008, 217(3–4), 305–319
  • [35] Sparse Matrix Market, available at
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.