Skip to main content
SpringerLink
Log in

A comparison of the Extrapolated Successive Overrelaxation and the Preconditioned Simultaneous Displacement methods for augmented linear systems

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

In this paper we study the impact of two types of preconditioning on the numerical solution of large sparse augmented linear systems. The first preconditioning matrix is the lower triangular part whereas the second is the product of the lower triangular part with the upper triangular part of the augmented system’s coefficient matrix. For the first preconditioning matrix we form the Generalized Modified Extrapolated Successive Overrelaxation (GMESOR) method, whereas the second preconditioning matrix yields the Generalized Modified Preconditioned Simultaneous Displacement (GMPSD) method, which is an extrapolated form of the Symmetric Successive Overrelaxation method. We find sufficient conditions for each aforementioned iterative method to converge. In addition, we develop a geometric approach, for determining the optimum values of their parameters and corresponding spectral radii. It is shown that both iterative methods studied (GMESOR and GMPSD) attain the same rate of convergence. Numerical results confirm our theoretical expectations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Arbogast, T., Gomez, M.S.M.: A discretization and multigrid solver for a Darcy–Stokes system of three dimentional vuggy porous media. Comput. Geosci. 13, 331–348 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  2. Arrow, K., Hurwicz, L., Uzawa, H.: Studies in Nonlinear Programming. Stanford University Press, Stanford, CA (1958)

  3. Bacuta, C., Monk, P.: Multilevel discretization of symmetric saddle point systems without the discrete LBB condition. Appl. Numer. Math. 62(6), 667–681 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  4. Bacuta, C., Shu, L.: Multilevel gradient Uzawa algorithms for symmetric saddle point problems. J. Sci. Comput. 57, 105–123 (2013)

  5. Bacuta, C.: Cascadic multilevel algorithms for saddle point systems. Math. Numer. Anal. (2013). arXiv:1305.2449v1

  6. Bai, Z.Z., Golub, G.H., Ng, M.K.: Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear sytems. SIAM J. Matrix Anal. Appl. 24(3), 603–626 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  7. Bai, Z.Z., Golub, G.H., Pan, J.-Y.: Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems. Numer. Math. 98, 1–32 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  8. Bai, Z.Z., Parlett, B.N., Wang, Z.-Q.: On generalized succesive overrelaxation methods for augmented linear systems. Numer. Math. 102, 1–38 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  9. Bai, Z.Z., Golub, G.H., Li, C.-K.: Optimal parameter in Hermitian and skew-Hermitian splitting method for certain two-by-two block matrices. SIAM J. Sci. Comput. 28(2), 583–603 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  10. Bai, Z.Z., Golub, G.H.: Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems. IMA J. Numer. Anal. 27(1), 1–23 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  11. Bai, Z.Z., Golub, G.H., Li, C.-K.: Convergence properties of preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite matrices. Math. Comput. 76(257), 287–298 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  12. Bai, Z.-Z., Wang, Z.-Q.: On parameterized inexact Uzawa methods for generalized saddle point problems. Linear Algebra Appl. 428(11–12), 2900–2932 (2008)

  13. Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1–137 (2005)

  14. Bramble, J.H., Pasciak, J.E., Vassilev, A.T.: Analysis of the inexact Uzawa algorithm for saddle point problems. SIAM J. Numer. Anal. 34(3), 1072–1092 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  15. Briggs, W.L., Henson, V.E., McCormick, S.F.: A Multigrid Tutorial, 2nd edn. SIAM (2000)

  16. Elman, H.C., Golub, G.H.: Inexact and preconditioned Uzawa algorithms for saddle point problems. SIAM J. Numer. Anal. 31(6), 1645–1661 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  17. Elman, H.C., Schultz, M.H.: Preconditioning by fast direct methods for nonself-adjoint nonseparable elliptic equations. SIAM J. Numer. Anal. 23(1), 44–57 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  18. Elman, H.C., Silvester, D.J., Wathen, A.J.: Performance and analysis of saddle point preconditioners for the discrete steady-state Navier–Stokes equations. Numer. Math. 90, 665–688 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  19. Evans, D.J., Missirlis, N.M.: The preconditioned simultaneous displacement method (PSD method) for elliptic difference equations. Math. Comput. Simul. 22(3), 256–263 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  20. Fischer, B., Ramage, R., Silvester, D.J., Wathen, A.J.: Minimum residual methods for augmented systems. BIT 38(3), 527–543 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  21. Golub, G.H., Wu, X., Yuan, J.-Y.: SOR-like methods for augmented systems. BIT 41(1), 71–85 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  22. Gaspar, F.J., Lisbona, F.J., Oosterlee, C.W., Vabishchevich, P.: An efficient multigrid solver for a reformulated version of the poroelasticity system. Comput. Methods Appl. Mech. Eng. 196(8), 1447–1457 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  23. Gordon, A., Powell, C.: On solving stochastic collocation systems with algebraic multigrid. IMA J. Numer. Anal. 32(3), 1051–1070 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  24. Griebel, M., Dornseifer, T., Neunhoffer, T.: Numerical Simulation in Fluid Dynamics, A Practical Introduction. SIAM, Philadelphia (1998)

    Book  Google Scholar 

  25. Griebel, M., Oeltz, D., Schweitzer, M.A.: An algebraic multigrid method for linear elasticity. SIAM J. Sci. Comput. 25(2), 385–407 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  26. Griebel, M., Metsch, B., Oeltz, D., Schweitzer, M.A.: Coarse grid classification: a parallel coarsening scheme for algebraic multigrid methods. Numer. Linear Algebra Appl. 13(2–3), 193–214 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  27. Griebel, M., Metsch, B., Schweitzer, M.A.: Coarse grid classification—Part II: automatic coarse grid agglomeration for parallel AMG. Preprint 271, Sonderforschungsbereich 611, Universit\(\ddot{a}\)t Bonn (2006)

  28. Griebel, M., Metsch, B., Schweitzer, M.A.: Coarse grid classification: AMG on parallel computers. In: M\(\ddot{u}\)unster, G., Wolf, D., Kremer, M. (eds.) NIC Symposium 2008. NIC Series, vol. 39, pp. 299–306 (2008)

  29. Hadjidimos, A.: Accelerated overrelaxation methods. Math. Comput. 32(141), 149–157 (1978)

  30. Hamilton, S., Benzi, M., Haber, E.: New multigrid smoothers for the Oseen problem. Numer. Linear Algebra Appl. 17(2–3), 557–576 (2010)

  31. Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49(6), 409–436 (1952)

    Article  MATH  MathSciNet  Google Scholar 

  32. Lu, C., Jiao, X., Missirlis, N.M.: A hybrid geometric + algebraic multigrid method with semi-iterative smoothers. Numer. Linear Algebra Appl. 21(2), 221–238 (2014)

    Article  MathSciNet  Google Scholar 

  33. Li, C.J., Li, Z., Evans, D.J., Zhang, T.: A note on an SOR-like method for augmented systems. IMA J. Numer. Anal. 23(4), 581–592 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  34. Louka, M.A., Missirlis, N.M., Tzaferis, F.I.: Is modified PSD equivalent to modified SOR for two-cyclic matrices? Linear Algebra Appl. 432(11), 2798–2815 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  35. Metsch, B.: Algebraic multigrid (AMG) for saddle point systems. Ph.D thesis, Mathematisch Naturwissenschaftlichen Fakultät, Universität Bonn (2013)

  36. Missirlis, N.M., Evans, D.J.: On the convergence of some generalised preconditioned iterative methods. SIAM J. Numer. Anal. 18(4), 591–596 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  37. Missirlis, N.M.: Convergence theory of extrapolated iterative methods for a certain class of non-symmetric linear systems. Numer. Math. 45, 447–458 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  38. Missirlis, N.M., Evans, D.J.: The modified preconditioned simultaneous displacement (MPSD) method. Math. Comput. Simul. 26(3), 257–262 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  39. Murphy, M.F., Golub, G.H., Wathen, A.J.: A note on preconditioning for indefinite linear systems. SIAM J. Sci. Comput. 21(6), 1969–1972 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  40. Oosterlee, C.W., Gaspar, F.J.: Multigrid relaxation methods for systems of saddle point type. Appl. Numer. Math. 58(12), 1933–1950 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  41. Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7(3), 856–869 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  42. Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003)

    Book  MATH  Google Scholar 

  43. Schulz, V., Wittum, G.: Transforming smoothers for PDE constraint optimization problems. Comput. Vis. Sci 11, 207–219 (2008)

    Article  MathSciNet  Google Scholar 

  44. Simon, R., Zulehner, W.: On Schwarz-type smoothers for saddle point problems with applications to PDE-constrained optimization problems. Numer. Math. 111, 445–468 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  45. Takacs, S., Zulehner, W.: Multigrid methods for elliptic optimal control problems with Neumann boundary conditions. In: Proceedings of ENUMATH 2009 the 8th European Conference on Numerical Mathematics and Advanced Applications, Uppsalla, pp. 855–863 (2009)

  46. Takacs, S., Zulehner, W.: Convergence analysis of multigrid methods with collective point smoothers for optimal control prolems. Comput. Vis. Sci. 14, 131–141 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  47. Trottenberg, U., Oosterlee, C.W., Schuller, A.: Multigrid. Academic Press, New York (2001)

  48. Van der Vorst, H.A.: Iterative Krylov Methods for Large Linear Systems, vol. 13. Cambridge University Press, London (2003)

  49. Varga, R.S.: Matrix Iterative Analysis. Prentice-Hall, Inc., Englewood Cliffs (1962)

    Google Scholar 

  50. Volker, J.: On the efficiency of linearization schemes and coupled multigrid methods in a simulation of a 3D flow around a cylinder. Int. J. Numer. Methods Fluids 50(7), 845–862 (2006)

    Article  MATH  Google Scholar 

  51. Wang, C.L., Bai, Z.Z.: Sufficient conditions for the convergent splittings of non-Hermitian positive definite matrices. Linear Algebra Appl. 330(1–3), 215–218 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  52. Wang, M., Chen, L.: Multigrid methods for the Stokes equations using distributive Gauss–Seidel relaxation based on the least squares commutator. J. Sci. Comput. 56, 409–431 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  53. Wathen, A.J., Silvester, D.J.: Fast iterative solution of stabilized Stokes systems. Part I: using simple diagonal preconditioners. SIAM J. Numer. Anal. 30(3), 630–649 (1993)

  54. Young, D.M.: Iterative Solution of Large Linear Systems. Academic Press, New York (1971)

    MATH  Google Scholar 

Download references

Acknowledgments

The authors would like to thank the referees for their constructive comments and suggestions which improved considerably the original form of the paper. The second author would like to thank the Department of Applied Mathematics and Statistics of State University of New York at Stony Brook for its warm hospitality while working on the paper.

Author information

Authors and Affiliations

  1. Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Panepistimiopolis, 15784, Athens, Greece

    M. A. Louka & N. M. Missirlis

Authors
  1. M. A. Louka
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. N. M. Missirlis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to N. M. Missirlis.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Louka, M.A., Missirlis, N.M. A comparison of the Extrapolated Successive Overrelaxation and the Preconditioned Simultaneous Displacement methods for augmented linear systems. Numer. Math. 131, 517–540 (2015). https://doi.org/10.1007/s00211-015-0697-6

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-015-0697-6

Mathematics Subject Classification

Search

Navigation