Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-05T12:44:12.805Z Has data issue: false hasContentIssue false
  • English
  • Français

Preconditioning

Published online by Cambridge University Press:  27 April 2015

A. J. Wathen
A. J. Wathen*
Affiliation:
Mathematical Institute, University of Oxford, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG, UK E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The computational solution of problems can be restricted by the availability of solution methods for linear(ized) systems of equations. In conjunction with iterative methods, preconditioning is often the vital component in enabling the solution of such systems when the dimension is large. We attempt a broad review of preconditioning methods.

Type
Research Article
Information
Acta Numerica , Volume 24 , 01 May 2015 , pp. 329 - 376
Copyright
© Cambridge University Press, 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES 1

Amestoy, P. R., Duff, I. S., L’Excellent, J.-Y. and Koster, J. (2000), MUMPS: A general purpose distributed memory sparse solver. In Proc. PARA2000: 5th International Workshop on Applied Parallel Computing, Springer, pp. 122–131.Google Scholar
Appleyard, J. R. and Cheshire, I. M. (1983), Nested factorization. Society of Petroleum Engineers, SPE 12264, presented at the Seventh SPE Symposium on Reservoir Simulation, San Francisco, 1983.Google Scholar
Arioli, M. (2004), ‘A stopping criterion for the conjugate gradient algorithm in a finite element method framework’, Numer. Math. 97, 1–24.CrossRefGoogle Scholar
Arioli, M., Loghin, D. and Wathen, A. J. (2005), ‘Stopping criteria for iterations in finite element methods’, Numer. Math. 99, 381–410.Google Scholar
Arnold, D. N., Falk, R. S. and Winther, R. (1997), ‘Preconditioning in $H(\text{div})$ and applications’, Math. Comp. 66, 957–984.Google Scholar
Bai, Z.-Z., Golub, G. H. and Ng, M. K. (2003), ‘Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems’, SIAM J. Matrix Anal. Appl. 24, 603–626.Google Scholar
Bakhvalov, N. S. (1966), ‘On the convergence of a relaxation method with natural constraints on the elliptic operator’, USSR Comp. Math. and Math. Phys. 6, 101–135.Google Scholar
Bebendorf, M. (2008), Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems, Vol. 63, Lecture Notes in Computational Science and Engineering, Springer.Google Scholar
Benzi, M. (2002), ‘Preconditioning techniques for large linear systems: A survey’, J. Comput. Phys. 182, 418–477.Google Scholar
Benzi, M. and Olshanskii, M. A. (2011), ‘Field-of-values convergence analysis of augmented Lagrangian preconditioners for the linearized Navier–Stokes problem’, SIAM J. Numer. Anal. 49, 770–788.CrossRefGoogle Scholar
Benzi, M. and Simoncini, V. (2006), ‘On the eigenvalues of a class of saddle point matrices’, Numer. Math. 103, 173–196.CrossRefGoogle Scholar
Benzi, M. and Tuma, M. (1998), ‘A sparse approximate inverse preconditioner for nonsymmetric linear systems’, SIAM J. Sci. Comput. 19, 968–994.CrossRefGoogle Scholar
Benzi, M. and Tuma, M. (2003), ‘A robust incomplete factorization preconditioner for positive definite matrices’, Numer. Linear Algebra Appl. 10, 385–400.Google Scholar
Benzi, M. and Wathen, A. J. (2008), Some preconditioning techniques for saddle point problems. In Model Order Reduction: Theory, Research Aspects and Applications (Schilders, W. H., van der Vorst, H. A. and Rommes, J., eds), Springer, pp. 195–211.CrossRefGoogle Scholar
Benzi, M., Cullum, J. K. and Tuma, M. (2000), ‘Robust approximate inverse preconditioning for the conjugate gradient method’, SIAM J. Sci. Comput. 22, 1318–1332.Google Scholar
Benzi, M., Golub, G. H. and Liesen, J. (2005), Numerical solution of saddle point problems. In Acta Numerica, Vol. 14, Cambridge University Press, pp. 1–137.Google Scholar
Benzi, M., Meyer, C. D. and Tuma, M. (1996), ‘A sparse approximate inverse preconditioner for the conjugate gradient method’, SIAM J. Sci. Comput. 17, 1135–1149.Google Scholar
Benzi, M., Ng, M., Niu, Q. and Wang, Z. (2011a), ‘A relaxed dimensional factorization preconditioner for the incompressible Navier–Stokes equations’, J. Comput. Phys. 230, 6185–6202.Google Scholar
Benzi, M., Olshanskii, M. A. and Wang, Z. (2011b), ‘Modified augmented Lagrangian preconditioners for the incompressible Navier–Stokes equations’, Internat. J. Numer. Meth. Fluids 66, 486–508.Google Scholar
Bergamaschi, L., Gondzio, J. and Zilli, G. (2004), ‘Preconditioning indefinite systems in interior point methods for optimization’, Comput. Optim. Appl. 28, 149–171.Google Scholar
Bern, M., Gilbert, J. R., Hendrickson, B., Nguyen, N. and Toledo, S. (2006), ‘Support-graph preconditioners’, SIAM J. Matrix Anal. Appl. 27, 930–951.Google Scholar
Björck, A. (1996), Numerical Methods for Least Squares Problems, SIAM.Google Scholar
Boyle, J. W., Mihajlovic, M. D. and Scott, J. A. (2010), ‘HSL_MI20: An efficient AMG preconditioner for finite element problems in 3D’, Internat. J. Numer. Meth. Engng 82, 64–98.CrossRefGoogle Scholar
Braess, D. and Peisker, P. (1986), ‘On the numerical solution of the biharmonic equation and the role of squaring matrices for preconditioning’, IMA J. Numer. Anal. 6, 393–404.Google Scholar
Bramble, J. and Pasciak, J. (1988), ‘A preconditioning technique for indefinite system resulting from mixed approximations of elliptic problems’, Math. Comp. 50, 1–17.Google Scholar
Bramble, J. H., Pasciak, J. E. and Xu, J. (1990), ‘Parallel multilevel preconditioners’, Math. Comp. 55, 1–22.Google Scholar
Brandt, A. (1977), ‘Multilevel adaptive solutions to boundary-value problems’, Math. Comp. 31, 333–390.Google Scholar
Brandt, A. and Ta’asan, S. (1986), Multigrid methods for nearly singular and slightly indefinite problems. In Multigrid Methods II (Hackbusch, W. and Trottenberg, U., eds), Vol. 1228 of Lecture Notes in Mathematics , Springer, pp. 99–121.Google Scholar
Bröker, O., Grote, M. J., Mayer, C. and Reusken, A. (2001), ‘Robust parallel smoothing for multigrid via sparse approximate inverses’, SIAM J. Sci Comput. 23, 1395–1416.Google Scholar
Chan, R. H.-F. and Jin, X.-Q. (2007), An Introduction to Iterative Toeplitz Solvers, SIAM.Google Scholar
Chan, T. F. and Mathew, T. P. (1994), Domain decomposition algorithms. In Acta Numerica, Vol. 3, Cambridge University Press, pp. 61–143.Google Scholar
Chandrasekaran, S., Dewilde, P., Gu, M., Pals, T., Sun, X., van der Veen, A. J. and White, D. (2005), ‘Some fast algorithms for sequentially semiseparable representation’, SIAM J. Matrix Anal. Appl. 27, 341–364.Google Scholar
Chen, K. (2005), Matrix Preconditioning Techniques and Applications, Cambridge University Press.Google Scholar
Concus, P. and Golub, G. H. (1976), A generalized conjugate gradient method for nonsymmetric systems of linear equations. In Vol. 134 of Lecture Notes in Economics and Mathematical Systems (R. Glowinski and P. L. Lions eds), Springer, pp. 56–65.Google Scholar
Cooley, J. W. and Tukey, J. W. (1965), ‘An algorithm for the machine calculation of complex Fourier series’, Math. Comp. 19, 297–301.Google Scholar
Davis, T. A. (2004), ‘Algorithm 832: UMFPACK V4.3 an unsymmetric-pattern multifrontal method’, ACM Trans. Math. Software 30, 196–199.Google Scholar
de Sterck, H., Manteuffel, T., McCormick, S. and Olson, L. (2004), ‘Least-squares finite element methods and algebraic multigrid solvers for linear hyperbolic PDEs’, SIAM J. Sci Comput. 26, 31–54.Google Scholar
Dollar, H. S. and Wathen, A. J. (2006), ‘Approximate factorization constraint preconditioners for saddle-point matrices’, SIAM J. Sci. Comput. 27, 1555–1572.Google Scholar
Dollar, H. S., Gould, N. I. M., Schilders, W. H. A. and Wathen, A. J. (2006), ‘Implicit-factorization preconditioning and iterative solvers for regularized saddle-point systems’, SIAM J. Matrix Anal. Appl. 28, 170–189.CrossRefGoogle Scholar
Dupont, T. F., Kendall, R. P. and Rachford, H. H. (1968), ‘An approximate factorization procedure for solving self-adjoint elliptic difference equations’, SIAM J. Numer. Anal. 5, 554–573.Google Scholar
Elman, H. C. and Chernesky, M. P. (1993), ‘Ordering effects on relaxation methods applied to the discrete one-dimensional convection–diffusion equation’, SIAM J. Numer. Anal. 30, 1268–1290.Google Scholar
Elman, H. C. and Schultz, M. H. (1986), ‘Preconditioning by fast direct methods for non-self-adjoint nonseparable elliptic equations’, SIAM J. Numer. Anal. 23, 44–57.Google Scholar
Elman, H. C. and Silvester, D. J. (1996), ‘Fast nonsymmetric iterations and preconditioning for the Navier–Stokes equations’, SIAM J. Sci. Comput. 17, 33–46.Google Scholar
Elman, H. C. and Zhang, X. (1995), ‘Algebraic analysis of the hierarchical basis preconditioner’, SIAM J. Matrix Anal. Appl. 16, 192–206.CrossRefGoogle Scholar
Elman, H. C., Ernst, O. G. and O’Leary, D. P. (2001), ‘A multigrid method enhanced by Krylov subspace iteration for discrete Helmholtz equations’, SIAM J. Sci. Comput. 23, 1291–1315.Google Scholar
Elman, H. C., Howle, V. E., Shadid, J. N., Shuttleworth, R. and Tuminaro, R. (2006), ‘Block preconditioners based on approximate commutators’, SIAM J. Sci. Comput. 27, 1651–1668.Google Scholar
Elman, H. C., Ramage, A. and Silvester, D. J. (2007), ‘Algorithm 886: IFISS, A Matlab toolbox for modelling incompressible flow’, ACM Trans. Math. Software 33, #14.Google Scholar
Elman, H. C., Ramage, A. and Silvester, D. J. (2014a), ‘IFISS: A computational laboratory for investigating incompressible flow problems’, SIAM Rev. 56, 261–273.Google Scholar
Elman, H. C., Silvester, D. J. and Wathen, A. J. (2014b), Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, second edition, Oxford University Press.Google Scholar
Elman, H. C., Silvester, D. J. and Wathen, A. J. (2005), Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, Oxford University Press.Google Scholar
Engquist, B. and Ying, L. (2011a), ‘Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation’, Comm. Pure Appl. Math. 64, 697–735.Google Scholar
Engquist, B. and Ying, L. (2011b), ‘Sweeping preconditioner for the Helmholtz equation: Moving perfectly matched layers’, Multiscale Model. Simul. 9, 686–710.Google Scholar
Erhel, J., Burrage, K. and Pohl, B. (1995), ‘Restarted GMRES preconditioned by deflation’, J. Comput. Appl. Math. 69, 303–318.Google Scholar
Erlangga, Y. A., Oosterlee, C. W. and Vuik, C. (2006), ‘A novel multigrid based preconditioner for heterogeneous Helmholtz problems’, SIAM J. Sci. Comput. 27, 1471–1492.CrossRefGoogle Scholar
Ernst, O. G. and Gander, M. J. (2012), Why it is difficult to solve Helmholtz problems with classical iterative methods. In Numerical Analysis of Multiscale Problems (Graham, I. G., Hou, T. Y., Lakkis, O. and Scheichl, R., eds), Springer, pp. 325–363.Google Scholar
Faber, V. and Manteuffel, T. (1984), ‘Necessary and sufficient conditions for the existence of a conjugate gradient method’, SIAM J. Numer. Anal. 21, 315–339.Google Scholar
Fedorenko, R. P. (1964), ‘The speed of convergence of one iterative process’, USSR Comp. Math. and Math. Phys. 4, 227–235.Google Scholar
Fischer, B. (2011), Polynomial Based Iteration Methods for Symmetric Linear Systems, SIAM.Google Scholar
Fischer, B., Ramage, A., Silvester, D. J. and Wathen, A. J. (1998), ‘Minimum residual methods for augmented systems’, BIT 38, 527–543.Google Scholar
Frank, J. and Vuik, C. (2001), ‘On the construction of deflation-based preconditioners’, SIAM J. Sci. Comput. 23, 442–462.Google Scholar
Freund, R. W. and Nachtigal, N. M. (1991), ‘QMR: A quasi-minimal residual method for non-Hermitian linear systems’, Numer. Math. 60, 315–339.Google Scholar
Freund, R. W. and Nachtigal, N. M. (1994), A new Krylov-subspace method for symmetric indefinite linear systems. In Proc. 14th IMACS World Congress on Computational and Applied Mathematics (Ames, W. F., ed.), IMACS, pp. 1253–1256.Google Scholar
Freund, R. W. and Ruscheweyh, S. (1986), ‘On a class of Chebyshev approximation problems which arise in connection with a conjugate gradient type method’, Numer. Math. 48, 525–542.CrossRefGoogle Scholar
Gander, M. J., Magoulès, F. and Nataf, F. (2002), ‘Optimized Schwarz methods without overlap for the Helmholtz equation’, SIAM J. Sci. Comput. 24, 38–60.Google Scholar
Gee, M. W., Siefert, C. M., Hu, J. J., Tuminaro, R. S. and Sala, M. G. (2006), ML 5.0 Smoothed Aggregation User’s Guide. Report SAND2006-2649, Sandia National Laboratories.Google Scholar
Giles, M. B. (2008), ‘Multilevel Monte Carlo path simulation’, Oper. Res. 56, 607–617.Google Scholar
Giraud, L., Gratton, S., Pinel, X. and Vasseur, X. (2010), ‘Flexible GMRES with deflated restarting’, SIAM J. Sci. Comput. 32, 1858–1878.CrossRefGoogle Scholar
Gould, N. I. M., Hribar, M. E. and Nocedal, J. (2001), ‘On the solution of equality constrained quadratic programming problems arising in optimization’, SIAM J. Sci. Comput. 23, 1376–1395.Google Scholar
Gould, N. I. M. and Simoncini, V. (2009), ‘Spectral analysis of saddle point matrices with indefinite leading blocks’, SIAM J. Matrix Anal. Appl. 31, 1152–1171.Google Scholar
Graham, I. G. and Hagger, M. J. (1999), ‘Unstructured additive Schwarz-conjugate gradient method for elliptic problems with highly discontinuous coefficients’, SIAM J. Sci. Comput. 20, 2041–2066.Google Scholar
Grasedyck, L. and Hackbusch, W. (2003), ‘Construction and arithmetics of ${\mathcal{H}}$ -matrices’, Computing 70, 295–334.Google Scholar
Greenbaum, A. (1997), Iterative Methods for Solving Linear Systems, SIAM.Google Scholar
Greengard, L. and Rokhlin, V. (1987), ‘A fast algorithm for particle simulations’, J. Comput. Phys. 73, 325–348.Google Scholar
Greif, C. and Schötzau, D. (2006), ‘Preconditioners for saddle point linear systems with highly singular (1,1) blocks’, Elect. Trans. Numer. Anal. 22, 114–121.Google Scholar
Greif, C. and Schötzau, D. (2007), ‘Preconditioners for the discretized time-harmonic Maxwell equations in mixed form’, Numer. Linear Algebra Appl. 14, 281–297.Google Scholar
Grote, M. J. and Huckle, T. (1997), ‘Parallel preconditioning with sparse approximate inverses’, SIAM J. Sci. Comput. 18, 83–853.Google Scholar
Günnel, A., Herzog, R. and Sachs, E. (2014), ‘A note on preconditioners and scalar products in Krylov subspace methods for self-adjoint problems in Hilbert space’, Elect. Trans. Numer. Anal. 41, 13–20.Google Scholar
Gustafsson, I. (1978), ‘A class of first order factorization methods’, BIT 18, 142–156.Google Scholar
Haber, E. and Ascher, U. M. (2001), ‘Preconditioned all-at-once methods for large, sparse parameter estimation problems’, Inverse Probl. 17, 1847–1864.Google Scholar
Hackbusch, W. (1994), Iterative Solution of Large Sparse Systems of Equations, Springer.Google Scholar
Hackbusch, W. (1999), ‘A sparse matrix arithmetic based on ${\mathcal{H}}$ -matrices I: Introduction to ${\mathcal{H}}$ -matrices’, Computing 62, 89–108.Google Scholar
Hackbusch, W., Khoromskij, B. K. and Sauter, S. (2000), On H2 -matrices. In Lectures on Applied Mathematics (Bungartz, H., Hoppe, R. and Zenger, C., eds), Springer, pp. 9–29.Google Scholar
Heil, M., Hazel, A. L. and Boyle, J. (2008), ‘Solvers for large-displacement fluid–structure interaction problems: Segregated versus monolithic approaches’, Comput. Mech. 43, 91–101.Google Scholar
Henson, V. E. and Yang, U. M. (2000), ‘BoomerAMG: A parallel algebraic multigrid solver and preconditioner’, Appl. Numer. Math. 41, 155–177.CrossRefGoogle Scholar
Hestenes, M. R. and Stiefel, E. (1952), ‘Methods of conjugate gradients for solving linear problems’, J. Res. Nat. Bur. Stand. 49, 409–436.Google Scholar
Hiptmair, R. and Xu, J. (2007), ‘Nodal auxiliary space preconditioning in H(curl) and H(div) spaces’, SIAM J. Numer. Anal. 45, 2483–2509.Google Scholar
Holland, R. M., Wathen, A. J. and Shaw, G. J. (2005), ‘Sparse approximate inverses and target matrices’, SIAM J. Sci. Comput. 26, 1000–1011.Google Scholar
HSL Mathematical Software Library (2013), A collection of Fortran codes for large scale scientific computation. www.hsl.rl.ac.uk Google Scholar
International Conference on Domain Decomposition Methods (2014). www.ddm.org/conferences.html Google Scholar
John, V. and Tobiska, L. (2000), ‘Numerical performance of smoothers in coupled multigrid methods for the parallel solution of the incompressible Navier–Stokes equations’, Internat. J. Numer. Meth. Fluids 33, 453–473.Google Scholar
Jonsthovel, T. B., van Gijzen, M. B., MacLachlan, S. C., Vuik, C. and Scarpas, A. (2012), ‘Comparison of the deflated preconditioned conjugate gradient method and algebraic multigrid for composite materials’, Comput. Mech. 50, 321–333.Google Scholar
Kay, D., Loghin, D. and Wathen, A. J. (2002), ‘A preconditioner for the steady-state Navier–Stokes equations’, SIAM J. Sci. Comput. 24, 237–256.Google Scholar
Keller, C., Gould, N. I. M. and Wathen, A. J. (2000), ‘Constraint preconditioning for indefinite linear systems’, SIAM J. Matrix Anal. Appl. 21, 1300–1317.Google Scholar
Klawonn, A. (1998), ‘Block-triangular preconditioners for saddle point problems with a penalty term’, SIAM J. Sci. Comput. 19, 172–184.Google Scholar
Klawonn, A. and Starke, G. (1999), ‘Block triangular preconditioners for nonsymmetric saddle point problems: Field-of-value analysis’, Numer. Math. 81, 577–594.Google Scholar
Kolotilina, L. Y. and Yeremin, A. Y. (1993), ‘Factorized sparse approximate inverse preconditioning I: Theory’, SIAM J. Matrix Anal. Appl. 14, 45–58.Google Scholar
Korzak, J. (1999), ‘Eigenvalue relations and conditions of matrices arising in linear programming’, Computing 62, 45–54.Google Scholar
Laird, A. L. and Giles, M. B. (2002), Preconditioned iterative solution of the 2D Helmholtz equation. Report NA-02/12, Oxford University Computer Laboratory.Google Scholar
Lehoucq, R. B. and Sorensen, D. C. (1996), ‘Deflation techniques for an implicitly restarted Arnoldi iteration’, SIAM J. Matrix Anal. Appl. 17, 789–821.Google Scholar
Li, X. S. (2005), ‘An overview of SuperLU: Algorithms, implementation and user interface’, ACM Trans. Math. Software 31, 302–325.Google Scholar
Liesen, J. and Strakoš, Z. (2013), Krylov Subspace Methods: Principles and Analysis, Oxford University Press.Google Scholar
Livne, O. E. and Brandt, A. (2012), ‘Lean Algebraic Multigrid (LAMG): Fast graph Laplacian linear solver’, SIAM J. Sci. Comput. 34, B499–B522.Google Scholar
Loghin, D. and Wathen, A. J. (2004), ‘Analysis of preconditioners for saddle-point problems’, SIAM J. Sci. Comput. 25, 2029–2049.Google Scholar
Magolu Monga Made, M., Beauwens, R. and Warzée, G. (2000), ‘Preconditioning of discrete Helmholtz operators perturbed by a diagonal complex matrix’, Commun. Numer. Methods Engng 16, 801–817.Google Scholar
Málek, J. and Strakoš, Z. (2014), Preconditioning and the Conjugate Gradient Method in the Context of Solving PDEs, SIAM.Google Scholar
Manservisi, S. (2006), ‘Numerical analysis of Vanka-type solvers for steady Stokes and Navier–Stokes flows’, SIAM J. Numer. Anal. 44, 2025–2056.Google Scholar
Mardal, K.-A. and Winther, R. (2011), ‘Preconditioning discretizations of systems of partial differential equations’, Numer. Linear Algebra Appl. 18, 1–40.Google Scholar
Mathew, T. P. (2008), Domain Decomposition Methods for the Numerical Solution of Partial Differential Equations, Springer.Google Scholar
Meijerink, J. A. and van der Vorst, H. A. (1977), ‘An iterative solution method for linear systems of which the coefficient matrix is a symmetric $M$ -matrix’, Math. Comp. 31, 148–162.Google Scholar
Meurant, G. A. (1999), Computer Solution of Large Linear Systems, North-Holland.Google Scholar
Murphy, M. F., Golub, G. H. and Wathen, A. J. (2000), ‘A note on preconditioning for indefinite linear systems’, SIAM J. Sci. Comput. 21, 1969–1972.Google Scholar
Neytcheva, M. (1999), talk presented at the first International Conference on Preconditioning, Minneapolis, 1999.Google Scholar
Ng, M. K. (2004), Iterative Methods for Toeplitz Systems, Oxford University Press.Google Scholar
Notay, Y. (2012), ‘Aggregation-based algebraic multigrid for convection–diffusion equations’, SIAM J. Sci. Comput. 34, A2288–A2316.Google Scholar
O’Leary, D. P. (1991), ‘Yet another polynomial preconditioner for the conjugate gradient algorithm’, Linear Algebra Appl. 154–156, 377–388.Google Scholar
Olshanskii, M. A. and Tyrtyshnikov, E. E. (2014), Iterative Methods for Linear Systems: Theory and Applications, SIAM.Google Scholar
Ong, M. E. G. (1997), ‘Hierarchical basis preconditioners in three dimensions’, SIAM J. Sci. Comput. 18, 479–498.Google Scholar
Otto, K. (1996), ‘Analysis of preconditioners for hyperbolic partial differential equations’, SIAM J. Numer. Anal. 33, 2131–2165.Google Scholar
Paige, C. C. and Saunders, M. A. (1975), ‘Solution of sparse indefinite systems of linear equations’, SIAM J. Numer. Anal. 12, 617–629.Google Scholar
Paige, C. C. and Saunders, M. A. (1982), ‘LSQR: An algorithm for sparse linear equations and sparse least squares’, ACM Trans. Math. Software 8, 43–71.Google Scholar
Parks, M. L., de Sturler, E., Mackey, G., Johnson, D. D. and Maiti, S. (2006), ‘Recycling Krylov subspaces for sequences of linear systems’, SIAM J. Sci. Comput. 28, 1651–1674.Google Scholar
Pestana, J. and Wathen, A. J. (2013a), ‘Combination preconditioning of saddle point systems for positive definiteness’, Numer. Linear Algebra Appl. 20, 785–808.Google Scholar
Pestana, J. and Wathen, A. J. (2013b), ‘On choice of preconditioner for minimum residual methods for non-Hermitian matrices’, J. Comput. Appl. Math. 249, 57–68.Google Scholar
Pestana, J. and Wathen, A. J. (2015a), ‘A preconditioned MINRES method for nonsymmetric Toeplitz matrices’, SIAM J. Matrix Anal. Appl., to appear.Google Scholar
Pestana, J. and Wathen, A. J. (2015b), ‘Natural preconditioning and iterative methods for saddle point systems’, SIAM Rev. 57, 71–91.Google Scholar
Phillips, E. G., Elman, H. C., Cyr, E. C., Shadid, J. N. and Pawlowski, R. P. (2014), A block preconditioner for an exact penalty formulation for stationary MHD. Computer Science report CS-TR-5032, University of Maryland.Google Scholar
Poulson, J., Engquist, B., Li, S. and Ying, L. (2013), ‘A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations’, SIAM J. Sci. Comput. 35, C194–C212.Google Scholar
Quarteroni, A. and Valli, A. (1999), Domain Decomposition Methods for Partial Differential Equations, Oxford University Press.CrossRefGoogle Scholar
Ramage, A. (1999), ‘A multigrid preconditioner for stabilised discretisations of advection–diffusion problems’, J. Comput. Appl. Math. 101, 187–203.Google Scholar
Rees, T., Dollar, H. S. and Wathen, A. J. (2010a), ‘Optimal solvers for PDE-constrained optimization’, SIAM J. Sci. Comput. 32, 271–298.Google Scholar
Rees, T., Stoll, M. and Wathen, A. J. (2010b), ‘All-at-once preconditioning in PDE-constrained optimization’, Kybernetika 46, 341–360.Google Scholar
Rhebergen, S., Wells, G. N., Katz, R. F. and Wathen, A. J. (2014), ‘Analysis of block-preconditioners for models of coupled magma/mantle dynamics’, SIAM J. Sci. Comput. 36, A1960–A1977.Google Scholar
Saad, Y. (1993), ‘A flexible inner-outer preconditioned GMRES algorithm’, SIAM J. Sci. Comput. 14, 461–469.Google Scholar
Saad, Y. (1996), ‘ILUM: A multi-elimination ILU preconditioner for general sparse matrices’, SIAM J. Sci. Comput. 17, 830–847.Google Scholar
Saad, Y. (2003), Iterative Methods for Sparse Linear Systems, second edition, SIAM.Google Scholar
Saad, Y. and Schultz, M. H. (1986), ‘GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems’, SIAM J. Sci. Statist. Comput. 7, 856–869.Google Scholar
Sifuentes, J. A., Embree, M. and Morgan, R. B. (2013), ‘GMRES convergence for perturbed coefficient matrices, with application to approximate deflation preconditioning’, SIAM. J. Matrix Anal. Appl. 34, 1066–1088.Google Scholar
Silvester, D. J. and Wathen, A. J. (1994), ‘Fast iterative solution of stabilised Stokes systems II: Using general block preconditioners’, SIAM J. Numer Anal. 31, 1352–1367.Google Scholar
Simoncini, V. and Szyld, D. B. (2007), ‘Recent computational developments in Krylov subspace methods for linear systems’, Numer. Linear Algebra Appl. 14, 1–59.Google Scholar
Sleijpen, G. L. G. and Fokkema, D. R. (1993), ‘BiCGstab(ell) for linear equations involving unsymmetric matrices with complex spectrum’, Elect. Trans. Numer. Anal. 1, 11–32.Google Scholar
Smith, B., Bjørstat, P. and Gropp, W. (1996), Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press.Google Scholar
Sonneveld, P. and van Gijzen, M. B. (2008), ‘IDR(s): A family of simple and fast algorithms for solving large nonsymmetric systems of linear equations’, SIAM J. Sci. Comput. 31, 1035–1062.Google Scholar
Spielman, D. A. and Teng, S.-H. (2014), ‘Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems’, SIAM J. Matrix Anal. Appl. 35, 835–885.Google Scholar
Stoll, M. and Wathen, A. J. (2008), ‘Combination preconditioning and the Bramble–Pasciak $^{+}$ preconditioner’, SIAM J. Matrix Anal. Appl. 30, 582–608.Google Scholar
Strang, G. (1986), ‘A proposal for Toeplitz matrix calculations’, Stud. Appl. Math. 74, 171–176.Google Scholar
Tang, W.-P. and Wan, W. L. (2000), ‘Sparse approximate inverse smoother for multigrid’, SIAM J. Matrix Anal. Appl. 21, 1236–1252.Google Scholar
Taussky, O. (1972), ‘The role of symmetric matrices in the study of general matrices’, Linear Algebra Appl. 5, 147–154.CrossRefGoogle Scholar
Toselli, A. and Widlund, O. (2004), Domain Decomposition Methods: Algorithms and Theory. Vol. 34 of Springer Series in Computational Mathematics , Springer.Google Scholar
Trefethen, L. N. and Embree, M. (2005), Spectra and Pseudospectra, Princeton University Press.Google Scholar
Trottenberg, U., Oosterlee, C. W. and Schüler, A. (2000), Multigrid, Academic Press.Google Scholar
Tsuji, P., Engquist, B. and Ying, L. (2012), ‘A sweeping preconditioner for time-harmonic Maxwell’s equations with finite elements’, J. Comput. Phys. 231, 3770–3783.Google Scholar
van Gijzen, M. B., Erlangga, Y. A. and Vuik, C. (2007), ‘Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian’, SIAM J. Sci. Comput. 29, 1942–1958.Google Scholar
van der Vorst, H. A. (1992), ‘Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems’, SIAM J. Sci. Statist. Comput. 13, 631–644.Google Scholar
van der Vorst, H. A. (2003), Iterative Krylov Methods for Large Linear Systems, Cambridge University Press.Google Scholar
Van Loan, C. F. (1992), Computational Frameworks for the Fast Fourier Transform, SIAM.Google Scholar
Vassilevski, P. S. (2008), Multilevel Block Factorization Preconditioners: Matrix-Based Analysis and Algorithms for Solving Finite Element Equations, Springer.Google Scholar
Verfürth, R. (1984), ‘A combined conjugate gradient-multigrid algorithm for the numerical solution of the Stokes problem’, IMA J. Numer. Anal. 4, 441–455.Google Scholar
Wathen, A. J. (1986), ‘Realistic eigenvalue bounds for the Galerkin mass matrix’, IMA J. Numer. Anal. 7, 449–457.Google Scholar
Wathen, A. J. (2007), ‘Preconditioning and convergence in the right norm’, Internat. J. Comput. Math. 84, 1199–1209.Google Scholar
Wathen, A. J. and Rees, T. (2009), ‘Chebyshev semi-iteration in preconditioning for problems including the mass matrix’, Elect. Trans. Numer. Anal. 34, 125–135.Google Scholar
Wathen, A. J., Fischer, B. and Silvester, D. J. (1995), ‘The convergence rate of the minimum residual method for the Stokes problem’, Numer. Math. 71, 121–134.Google Scholar
Wathen, M. P. (2014), Iterative solution of a mixed finite element discretisation of an incompressible magnetohydrodynamics problem. MSc dissertation, Department of Computer Science, University of British Columbia.Google Scholar
Widlund, O. (1978), ‘A Lanczos method for a class of nonsymmetric systems of linear equations’, SIAM J. Numer. Anal. 15, 801–812.Google Scholar
Worley, P. H. (1991), ‘Limits on parallelism in the numerical solution of linear partial differential equations’, SIAM J. Sci. Statist. Comput. 12, 1–35.Google Scholar
Xu, J. (1992), ‘Iterative methods by space decomposition and subspace correction’, SIAM Rev. 34, 581–613.Google Scholar
Ymbert, G., Embree, M. and Sifuentes, J. (2015), Approximate Murphy–Golub–Wathen preconditioning for saddle point problems. In preparation.Google Scholar
Yserentant, H. (1986), ‘On the multi-level splitting of finite element spaces’, Numer. Math. 49, 379–412.Google Scholar