Using successive approximations for improving the convergence of GMRES method

Jan Zítko

Applications of Mathematics (1998)

  • Volume: 43, Issue: 5, page 321-350
  • ISSN: 0862-7940

Abstract

top
In this paper, our attention is concentrated on the GMRES method for the solution of the system ( I - T ) x = b of linear algebraic equations with a nonsymmetric matrix. We perform m pre-iterations y l + 1 = T y l + b before starting GMRES and put y m for the initial approximation in GMRES. We derive an upper estimate for the norm of the error vector in dependence on the m th powers of eigenvalues of the matrix T . Further we study under what eigenvalues lay-out this upper estimate is the best one. The estimate shows and numerical experiments verify that it is advisable to perform pre-iterations before starting GMRES as they require fewer arithmetic operations than GMRES. Towards the end of the paper we present a numerical experiment for a system obtained by the finite difference approximation of convection-diffusion equations.

How to cite

top

Zítko, Jan. "Using successive approximations for improving the convergence of GMRES method." Applications of Mathematics 43.5 (1998): 321-350. <http://eudml.org/doc/33014>.

@article{Zítko1998,
abstract = {In this paper, our attention is concentrated on the GMRES method for the solution of the system $(I-T)x=b$ of linear algebraic equations with a nonsymmetric matrix. We perform $m$ pre-iterations $y_\{l+1\}=Ty_l+b $ before starting GMRES and put $y_m $ for the initial approximation in GMRES. We derive an upper estimate for the norm of the error vector in dependence on the $m$th powers of eigenvalues of the matrix $T$. Further we study under what eigenvalues lay-out this upper estimate is the best one. The estimate shows and numerical experiments verify that it is advisable to perform pre-iterations before starting GMRES as they require fewer arithmetic operations than GMRES. Towards the end of the paper we present a numerical experiment for a system obtained by the finite difference approximation of convection-diffusion equations.},
author = {Zítko, Jan},
journal = {Applications of Mathematics},
keywords = {GMRES; iterative method; numerical experiments; solution of discretized equations; GMRES; iterative method; numerical experiments; solution of dicsretized equations},
language = {eng},
number = {5},
pages = {321-350},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Using successive approximations for improving the convergence of GMRES method},
url = {http://eudml.org/doc/33014},
volume = {43},
year = {1998},
}

TY - JOUR
AU - Zítko, Jan
TI - Using successive approximations for improving the convergence of GMRES method
JO - Applications of Mathematics
PY - 1998
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 43
IS - 5
SP - 321
EP - 350
AB - In this paper, our attention is concentrated on the GMRES method for the solution of the system $(I-T)x=b$ of linear algebraic equations with a nonsymmetric matrix. We perform $m$ pre-iterations $y_{l+1}=Ty_l+b $ before starting GMRES and put $y_m $ for the initial approximation in GMRES. We derive an upper estimate for the norm of the error vector in dependence on the $m$th powers of eigenvalues of the matrix $T$. Further we study under what eigenvalues lay-out this upper estimate is the best one. The estimate shows and numerical experiments verify that it is advisable to perform pre-iterations before starting GMRES as they require fewer arithmetic operations than GMRES. Towards the end of the paper we present a numerical experiment for a system obtained by the finite difference approximation of convection-diffusion equations.
LA - eng
KW - GMRES; iterative method; numerical experiments; solution of discretized equations; GMRES; iterative method; numerical experiments; solution of dicsretized equations
UR - http://eudml.org/doc/33014
ER -

References

top
  1. 10.1007/BF01396750, Numer. Math. 51 (1987), 209–227. (1987) MR0890033DOI10.1007/BF01396750
  2. Extrapolation Methods—Theory and Practice, North Holland, 1991. (1991) MR1140920
  3. Iterative Methods for Large Sparse Nonsymmetric Systems of Linear Equations, Ph. D. thesis, Computer Science Dept., Yale Univ., New Haven, CT, 1982. (1982) 
  4. Matrix Computation, The John Hopkins University Press, Baltimore, 1984. (1984) 
  5. Computational Methods of Linear Algebra, San Francisco: Freeman 1963. Zbl0755.65029MR0158519
  6. Iterative solution of linear systems, Acta Numerica (1991), 57–100. (1991) MR1165723
  7. Applied Iterative Method, New York, Academic Press, 1981. (1981) MR0630192
  8. The Theory of Matrices in Numerical Analysis, Blaisdell Publishing Company, 1964. (1964) Zbl0161.12101MR0175290
  9. 10.1016/0024-3795(80)90165-2, Linear Algebra Appl. 34 (1980), 159–194. (1980) MR0591431DOI10.1016/0024-3795(80)90165-2
  10. Iterative Methods for Large Linear Systems, Papers from a conference held Oct. 19–21, 1988 at the Center for Numerical Analysis of the University of Texas at Austin, Edited by D.R. Kincaid, L.J. Hayes (eds.), Academic Press, 1989. (1989) Zbl0703.68010MR1038083
  11. 10.6028/jres.049.006, J. Res. Nat. Bur. Stand. 49 (1952), 33–53. (1952) MR0051583DOI10.6028/jres.049.006
  12. Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, 1970. (1970) MR0273810
  13. 10.1090/S0025-5718-1981-0616364-6, Math Comput. 37 (1981), 105–126. (1981) Zbl0474.65019MR0616364DOI10.1090/S0025-5718-1981-0616364-6
  14. 10.1137/0905015, SIAM J. Sci. Stat. Comput. 5 (1984), 203–227. (1984) Zbl0539.65012MR0731892DOI10.1137/0905015
  15. 10.1137/0907058, SIAM J. Sci. Stat. Comput. 7 (1986), 856–869. (1986) MR0848568DOI10.1137/0907058
  16. 10.1137/0723013, SIAM J. Numer. Anal. 23 (1986), 178–196. (1986) MR0821914DOI10.1137/0723013
  17. 10.1137/0723014, SIAM J. Numer. Anal. 23 (1986), 197–209. (1986) Zbl0612.65001MR0821915DOI10.1137/0723014
  18. 10.1016/0377-0427(88)90289-0, J. Comput. Appl. Math. 22 (1988), 71–88. (1988) Zbl0646.65031MR0948887DOI10.1016/0377-0427(88)90289-0
  19. Solution of large linear systems of equations by conjugate gradient type methods, , Mathematical Programming—The State of the Art, A. Bachem, M. Grötschel and B. Korte (eds.), Springer (Berlin), 1983, pp. 540–565. (1983) Zbl0553.65022MR0717414
  20. Matrix Iterative Analysis, Prentice-Hall Englewood Clifs, New Jersey, 1962. (1962) MR0158502
  21. 10.1016/0377-0427(93)90028-A, J. Comput. Appl. Math. 48 (1993), 327–341. (1993) MR1252545DOI10.1016/0377-0427(93)90028-A
  22. Iterative Solution of Large Linear Systems, Academic Press, New York-London, 1971. (1971) Zbl0231.65034MR0305568
  23. Sequence Transformations and their Aapplications, Academic Press, 1981. (1981) MR0615250
  24. Improving the convergence of iterative methods, Apl. Mat. 28 (1983), 215–229. (1983) MR0701740
  25. Convergence of extrapolation coefficients, Apl. Mat. 29 (1984), 114–133. (1984) MR0738497
  26. The behaviour of the error vector using the GMRES method, Technical report No 4/94, Prague, 1994, pp. 1–27. (1994) 
  27. Combining the preconditioned conjugate gradient method and a matrix iterative method, Appl. Math. 41 (1996), 19–39. (1996) MR1365137
  28. Combining the GMRES and a matrix iterative method, ZAMM (Proceedings of ICIAM/GAMM 95) Vol. 76, 1996, pp. 595–596. (1996) 
  29. Improving the convergence of GMRES using preconditioning and pre-iterations, Proceedings of the conference “Prague Mathematical Conference 1996”, 1996, pp. 377–382. (1996) 
  30. Behaviour of GMRES iterations using preconditioning and pre-iterations, ZAMM (Proceedings of GAMM 96) Vol. 77, 1997, pp. 693–694. (1997) 

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.