skip to main content
research-article

An Optimal Iterative Solver for Symmetric Indefinite Systems Stemming from Mixed Approximation

Published: 01 February 2011 Publication History

Abstract

We discuss the design and implementation of a suite of functions for solving symmetric indefinite linear systems associated with mixed approximation of systems of PDEs. The novel feature of our iterative solver is the incorporation of error control in the natural “energy” norm in combination with an a posteriori estimator for the PDE approximation error. This leads to a robust and optimally efficient stopping criterion: the iteration is terminated as soon as the algebraic error is insignificant compared to the approximation error. We describe a “proof of concept” MATLAB implementation of this algorithm, which we call EST_MINRES, and we illustrate its effectiveness when integrated into the Incompressible Flow Iterative Solution Software (IFISS) package (cf. ACM Transactions on Mathematical Software 33, Article 14, 2007).

References

[1]
Ainsworth, M. and Oden, J. 1997. A posteriori error estimates for Stokes’ and Oseen’s equations. SIAM J. Numer. Anal. 34, 228--245.
[2]
Arioli, M. and Loghin, D. 2008. Stopping criteria for mixed finite element problems. Electron. Trans. Numer. Anal. 29, 178--192.
[3]
Arioli, M., Loghin, D., and Wathen, A. 2005. Stopping criteria for iterations in finite-element methods. Numer. Math. 99, 381--410.
[4]
Arnold, D., Falk, R., and Winther, R. 1997. Preconditioning in H(div) and applications. Math. Comp. 66, 957--984.
[5]
Arnold, D., Falk, R., and Winther, R. 2000. Multigrid in H(div) and H(curl). Numer. Math. 85, 197--217.
[6]
Benzi, M., Golub, G. H., and Liesen, J. 2005. Numerical solution of saddle point problems. Acta Numerica 14, 1--137.
[7]
Brezzi, F. and Fortin, M. 1991. Mixed and Hybrid Finite Element Methods. Springer-Verlag, Berlin, Germany.
[8]
Elman, H., Silvester, D., and Wathen, A. 2005. Finite Elements and Fast Iterative Solvers with Applications in Incompressible Fluid Dynamics. Oxford University Press, Oxford, UK.
[9]
Elman, H., Ramage, A., and Silvester, D. 2007. Algorithm 866: IFISS, a Matlab toolbox for modelling incompressible flow. ACM Trans. Math. Softw. 33, 2--14.
[10]
Freund, R. W. 1992. Quasi-kernel polynomials and convergence results for quasi-minimal residual iterations. In Numerical Methods in Approximation Theory, Vol. 9, D. Braess and L. L. Schumaker Eds. Birkhäuser Verlag, Basel, Switzerland, 77--95.
[11]
Golub, G. H. and Meurant, G. A. 1997. Matrices, moments and quadrature II; how to compute the norm of the error in iterative methods. BIT 37, 687--705.
[12]
Greenbaum, A. 1997. Iterative Methods for Solving Linear Systems. SIAM, Philadelphia, PA.
[13]
Hiptmair, R. and Xu, J. 2007. Nodal auxiliary space preconditioning in H(curl) and H(div) spaces. SIAM J. Numer. Anal. 45, 2483--2509.
[14]
Jiránek, P., Strakoš, Z., and Vohralík, M. 2010. A posteriori error estimates including algebraic error and stopping criteria for iterative solvers. SIAM J. Sci. Comput. 32, 1567--1590.
[15]
Kay, D. and Silvester, D. 1999. A posteriori error estimation for stabilized mixed approximations of the Stokes equations. SIAM J. Sci. Comput. 21, 1321--1336.
[16]
Liao, Q. and Silvester, D. 2010. A simple yet effective a posteriori error estimator for classical mixed approximation of Stokes equations. Appl. Numer. Math.
[17]
Mardal, K.-A. and Winther, R. 2010. Preconditioning discretizations of systems of partial differential equations. Numer. Lin. Alg. Appl.
[18]
Meurant, G. 2005. Estimates of the l 2 norm of the error in the conjugate gradient algorithm. Numer. Alg. 40, 157--169.
[19]
Meurant, G. and Strakoš, Z. 2006. The Lanczos and conjugate gradient algorithms in finite precision arithmetic. Acta Numerica 15, 471--542.
[20]
Morgan, R. B. 1991. Computing interior eigenvalues of large matrices. Lin. Alg. Appl. 154--156, 289--309.
[21]
Paige, C., Parlett, B., and van der Vorst, H. 1995. Approximate solutions and eigenvalue bounds from Krylov subspaces. Numer. Lin. Alg. Appl. 2, 115--134.
[22]
Paige, C. and Saunders, M. 1975. Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12, 617--629.
[23]
Parlett, B. N. 1998. The Symmetric Eigenvalue Problem. SIAM, Philadelphia, PA.
[24]
Powell, C. 2005. Parameter-free H(div) preconditioning for mixed finite element formulation of diffusion problems. IMA J. Numer. Anal. 25, 783--796.
[25]
Powell, C. and Silvester, D. 2004. Optimal preconditioning for Raviart-Thomas mixed formulation of second-order elliptic problems. SIAM J. Matrix Anal. Appl. 25, 718--738.
[26]
Rusten, T. and Winther, R. 1992. A preconditioned iterative method for saddle-point problems. SIAM J. Matrix Anal. Appl. 13, 887--904.
[27]
Saad, Y. 2003. Iterative Methods for Sparse Linear Systems 2nd Ed. SIAM, Philadelphia, PA.
[28]
Silvester, D. and Powell, C. 2007. Potential (incompressible) flow and iterative solution software guide (PIFISS), version 1.0. Tech. rep. 2007.14. MIMS, Manchester, UK. http://eprints.ma.man.ac.uk/700/.
[29]
Silvester, D. and Wathen, A. 1994. Fast iterative solution of stabilised Stokes systems. Part II: Using general block preconditioners. SIAM J. Numer. Anal. 31, 1352--1367.
[30]
Strakoš, Z. and Tichý, P. 2002. On error estimation in the conjugate gradient method and why it works in finite precision computations. Elect. Trans. Numer. Anal. 13, 56--80.
[31]
Wathen, A. 2007. Preconditioning and convergence in the right norm. Int. J. Comput. Math. 84, 1199--1209.
[32]
Wathen, A. and Rees, T. 2009. Chebyshev semi-iteration in preconditioning for problems including the mass matrix. Elect. Trans. Numer. Anal. 34, 125--135.

Cited By

View all
  • (2024)Fast solution of incompressible flow problems with two-level pressure approximationNumerische Mathematik10.1007/s00211-024-01420-z156:4(1579-1602)Online publication date: 1-Aug-2024
  • (2023)A New Stopping Criterion for Krylov Solvers Applied in Interior Point MethodsSIAM Journal on Scientific Computing10.1137/22M149004145:2(A703-A728)Online publication date: 27-Apr-2023
  • (2022)Iterative Solvers for Mixed ProblemsNumerical Methods for Mixed Finite Element Problems10.1007/978-3-031-12616-1_3(19-41)Online publication date: 6-Jul-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software
ACM Transactions on Mathematical Software  Volume 37, Issue 4
February 2011
212 pages
ISSN:0098-3500
EISSN:1557-7295
DOI:10.1145/1916461
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 2011
Accepted: 01 September 2010
Revised: 01 September 2010
Received: 01 May 2010
Published in TOMS Volume 37, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. EST_MINRES
  2. Finite elements
  3. MATLAB
  4. incompressible flow
  5. iterative solvers
  6. stopping criteria

Qualifiers

  • Research-article
  • Research
  • Refereed

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)10
  • Downloads (Last 6 weeks)1
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Fast solution of incompressible flow problems with two-level pressure approximationNumerische Mathematik10.1007/s00211-024-01420-z156:4(1579-1602)Online publication date: 1-Aug-2024
  • (2023)A New Stopping Criterion for Krylov Solvers Applied in Interior Point MethodsSIAM Journal on Scientific Computing10.1137/22M149004145:2(A703-A728)Online publication date: 27-Apr-2023
  • (2022)Iterative Solvers for Mixed ProblemsNumerical Methods for Mixed Finite Element Problems10.1007/978-3-031-12616-1_3(19-41)Online publication date: 6-Jul-2022
  • (2021)Dimensionally Consistent Preconditioning for Saddle-Point ProblemsComputational Methods in Applied Mathematics10.1515/cmam-2020-003721:3(593-607)Online publication date: 18-May-2021
  • (2021)Two-Level a Posteriori Error Estimation for Adaptive Multilevel Stochastic Galerkin Finite Element MethodSIAM/ASA Journal on Uncertainty Quantification10.1137/20M13425869:3(1184-1216)Online publication date: 16-Sep-2021
  • (2021)T-IFISS: a toolbox for adaptive FEM computationComputers & Mathematics with Applications10.1016/j.camwa.2020.03.00581(373-390)Online publication date: Jan-2021
  • (2019)Low-Rank Solution Methods for Stochastic Eigenvalue ProblemsSIAM Journal on Scientific Computing10.1137/18M122100X41:4(A2657-A2680)Online publication date: 22-Aug-2019
  • (2018)Adaptive inexact iterative algorithms based on polynomial-degree-robust a posteriori estimates for the Stokes problemNumerische Mathematik10.1007/s00211-017-0925-3138:4(1027-1065)Online publication date: 1-Apr-2018
  • (2018)Estimating and localizing the algebraic and total numerical errors using flux reconstructionsNumerische Mathematik10.1007/s00211-017-0915-5138:3(681-721)Online publication date: 1-Mar-2018
  • (2017)A Modified Implementation of MINRES to Monitor Residual Subvector Norms for Block SystemsSIAM Journal on Scientific Computing10.1137/16M109302139:6(A2645-A2663)Online publication date: Jan-2017
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media