×

Preconditioning discretizations of systems of partial differential equations. (English) Zbl 1249.65246

This review paper surveys an abstract approach for construction of preconditioners for differential operators in the setting of Hilbert spaces. First, the idea is presented in the context of Krylov space methods. Then, the authors concentrate on abstract saddle point problems, parameter-dependent (singularly perturbed) problems, and on a general approach for preconditioning finite element systems. The paper contains a number of examples including the Laplace operator, a Maxwell problem, Stokes problem, reaction-diffusion problem, Reissner-Mindlin plate model and optimal control problem.

MSC:

65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65F08 Preconditioners for iterative methods
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
35Q30 Navier-Stokes equations
35Q61 Maxwell equations
35K57 Reaction-diffusion equations
74K20 Plates
65K10 Numerical optimization and variational techniques
49J15 Existence theories for optimal control problems involving ordinary differential equations
35B25 Singular perturbations in context of PDEs
65F10 Iterative numerical methods for linear systems
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Arnold, Preconditioning discrete approximations of the Reissner-Mindlin plate model, RAIRO Modélisation Mathématique et Analyse Numérique 31 (4) pp 517– (1997)
[2] Arnold, Preconditioning in H(div) and applications, Mathematics of Computation 66 pp 957– (1997) · Zbl 0870.65112
[3] Babuška, The Mathematical Foundation of the Finite Element Method with Applications to Partial Differential Equations pp 3– (1972)
[4] Babuška, Error bounds for finite element methods, Numerische Mathematik 16 pp 322– (1971) · Zbl 0214.42001
[5] Hiptmair, Operator preconditioning, Computers and Mathematics with Applications 52 (5) pp 699– (2006) · Zbl 1125.65037
[6] Elman, Numerical Mathematics and Scientific Computation (2005)
[7] Vassilevski, Multilevel Block Factorization Preconditioners (2008)
[8] Vassilevski, Wavelet Analysis and its Applications, in: Multiscale Wavelet Methods for Partial Differential Equations pp 59– (1997)
[9] Hestenes, Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards 49 pp 409– (1952) · Zbl 0048.09901
[10] Golub, Matrix Computations (1989)
[11] Hackbusch, Iterative Solution of Large Sparse Systems of Equations (1994) · Zbl 0789.65017
[12] Trefethen, Numerical Linear Algebra (1997)
[13] Axelsson, On the eigenvalue distribution of a class of preconditioning methods, Numerische Mathematik 48 pp 479– (1986) · Zbl 0564.65016
[14] Axelsson, On the rate of convergence of the preconditioned conjugate gradient method, Numerische Mathematik 48 pp 499– (1986) · Zbl 0564.65017
[15] Solution of Large Linear Systems of Equations by the Conjugate Gradient Method (1983)
[16] Chandra, Report 129 (1978)
[17] Paige, Solution of sparse indefinite systems of linear equations, SIAM Journal on Numerical Analysis 12 pp 617– (1975) · Zbl 0319.65025
[18] Rusten, A preconditioned iterative method for saddlepoint problems, SIAM Journal on Matrix Analysis and Applications 13 (3) pp 887– (1992) · Zbl 0760.65033
[19] Silvester, Fast iterative solution of stabilised Stokes systems. Part I: using simple diagonal preconditioners, SIAM Journal on Numerical Analysis 30 (3) pp 630– (1993) · Zbl 0776.76024
[20] Silvester, Fast iterative solution of stabilized Stokes systems. Part II: using block diagonal preconditioners, SIAM Journal on Numerical Analysis 31 (5) pp 1352– (1994) · Zbl 0810.76044
[21] Winther, Some superlinear convergence results for the conjugate gradient method, SIAM Journal on Numerical Analysis 17 (1) pp 14– (1980) · Zbl 0447.65021
[22] D’Yakonov, On an iterative method for the solution of finite difference equations, Doklady Akademii Nauk SSSR 138 pp 522– (1961)
[23] Gunn, The solution of difference equations by semi-explicit iterative techniques, SIAM Journal on Numerical Analysis 2 pp 24– (1965) · Zbl 0137.33301
[24] Brezzi, On the existence uniqueness and approximation of saddle-point problems arising from Lagrangian multipliers, RAIRO Analyse Numérique 8 pp 129– (1974) · Zbl 0338.90047
[25] Brezzi, Mixed and Hybrid Finite Element Methods (1991) · Zbl 0788.73002
[26] Haug, A domain embedding preconditioner for the Lagrange multiplier system, Mathematics of Computation 69 pp 65– (1999) · Zbl 0936.65131
[27] Rusten, Substructure preconditioners for elliptic saddle point problems, Mathematics of Computation 60 (201) pp 23– (1993) · Zbl 0795.65072
[28] Nečas, Equations aux dérivée partielles (1965)
[29] Bergh, Interpolation Spaces (1976)
[30] Dauge, Stationary Stokes and Navier-Stokes systems on two- or three-dimensional domains with corners. I. Linearized equations, SIAM Journal on Mathematical Analysis 20 (1) pp 74– (1989) · Zbl 0681.35071
[31] Mardal, Erratum: Uniform preconditioners for the time dependent Stokes problem [Numer. Math. 98 (2004), no. 2, 305-327], Numerische Mathematik 103 (1) pp 171– (2006) · Zbl 1094.65045
[32] Schöberl J Private communication
[33] Bramble, Iterative techniques for time dependent Stokes problems, Computers and Mathematics with Applications. An International Journal 33 (1-2) pp 13– (1997) · Zbl 1030.76506
[34] Cahouet, Some fast 3D finite element solvers for the generalized Stokes problem, International Journal for Numerical Methods in Fluids 8 (8) pp 869– (1988) · Zbl 0665.76038
[35] Elman, Preconditioners for saddle point problems arising in computational fluid dynamics, Applied Numerical Mathematics. An IMACS Journal 43 (1-2) pp 75– (2002) · Zbl 1168.76348
[36] Elman, Performance and analysis of saddle point preconditioners for the discrete steady-state Navier-Stokes equations, Numerische Mathematik 90 (4) pp 665– (2002) · Zbl 1143.76531
[37] Kobelkov, Effective preconditioning of Uzawa type schemes for generalized Stokes problem, Numerische Mathematik 86 pp 443– (2000) · Zbl 0964.65129
[38] Langtangen, Numerical methods for incompressible viscous flow, Advances in Water Resources 25 (8) pp 1125– (2002)
[39] Mardal, Uniform preconditioners for the time dependent Stokes problem, Numerische Mathematik 98 (2) pp 305– (2004) · Zbl 1058.65101
[40] Olshanskii, Uniform preconditioners for a parameter dependent saddle point problem with application to generalized Stokes interface equations, Numerische Mathematik 105 pp 159– (2006) · Zbl 1120.65059
[41] Turek, Efficient Solvers for Incompressible Flow Problems (1999) · Zbl 0930.76002
[42] Borzì, Accuracy and convergence properties of the finite difference multigrid solution of an optimal control optimality system, SIAM Journal on Control and Optimization 41 (5) pp 1477– (2003) · Zbl 1031.49029
[43] Mathew, Analysis of block matrix preconditioners for elliptic optimal control problems, Numerical Linear Algebra with Applications 14 (4) pp 257– (2007) · Zbl 1199.65218
[44] Schöberl, Symmetric indefinite preconditioners for saddle point problems with applications to PDE-constrained optimization problems, SIAM Journal on Matrix Analysis and Applications 29 (3) pp 752– (2007) · Zbl 1154.65029
[45] Falk, Error estimates for mixed methods, RAIRO Analyse Numérique 14 pp 249– (1980)
[46] Bramble, Pitman Research Notes in Mathematical Sciences, in: Multigrid Methods (1993)
[47] Briggs, A Multigrid Tutorial (2000) · Zbl 0958.65128
[48] Smith, Domain Decomposition (1996)
[49] Bramble, Computational scales of sobolev norms with application to preconditioning, Mathematics of Computation 69 pp 463– (2000) · Zbl 0941.65052
[50] Cai, Additive Schwarz algorithms for parabolic convection-diffusion equations, Numerische Mathematik 60 pp 41– (1991) · Zbl 0737.65078
[51] Cai, Multiplicative Schwarz methods for parabolic problems, SIAM Journal on Scientific Computing 15 (3) pp 587– (1994) · Zbl 0803.65096
[52] Olshanskii, On the convergence of a multigrid method for linear reaction-diffusion problems, Computing 65 (3) pp 193– (2000) · Zbl 0972.65082
[53] Cai, Multilevel iteration for mixed finite element system with penalty, SIAM Journal on Scientific Computing 14 pp 1072– (1993) · Zbl 0809.65114
[54] Arnold, Multigrid preconditioning in H(div) on non-convex polygons, Journal of Computational and Applied Mathematics 17 pp 307– (1998) · Zbl 0922.65078
[55] Arnold, Multigrid in H(div) and H(curl), Numerische Mathematik 85 pp 197– (2000) · Zbl 0974.65113
[56] Hiptmair, Multigrid method for H(div) in three dimensions, Electronic Transactions on Numerical Analysis 6 pp 133– (1997) · Zbl 0897.65046
[57] Hiptmair, Multigrid method for Maxwell’s equations, SIAM Journal on Numerical Analysis 36 (1) pp 204– (1999) · Zbl 0922.65081
[58] Vassilevski, Multilevel iterative methods for mixed finite element discretizations of elliptic problems, Numerische Mathematik 63 (4) pp 503– (1992) · Zbl 0797.65086
[59] Vassilevski, An application of the abstract multilevel theory to nonconforming finite element methods, SIAM Journal on Numerical Analysis 32 (1) pp 235– (1995) · Zbl 0828.65125
[60] Arnold, Finite element exterior calculus homological techniques, and applications, Acta Numerica 15 pp 1– (2006) · Zbl 1185.65204
[61] Hiptmair, Nodal auxiliary space preconditioning in H(curl) and H(div) spaces, SIAM Journal on Numerical Analysis 45 (6) pp 2483– (2007) · Zbl 1153.78006
[62] Benzi, Numerical solution of saddle point problems, Acta Numerica 14 pp 1– (2005) · Zbl 1115.65034
[63] Kay, A preconditioner for the steady-state Navier-Stokes equations, SIAM Journal on Scientific Computing 24 (1) pp 237– (2002) · Zbl 1013.65039
[64] Axelsson, Preconditioning methods for linear systems arising in constrained optimization problems, Numerical Linear Algebra with Applications 10 pp 3– (2003) · Zbl 1071.65527
[65] Perugia, Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations, Numerical Linear Algebra with Applications 7 pp 585– (2000) · Zbl 1051.65038
[66] Bramble, A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems, Mathematics of Computation 50 pp 117– (1988) · Zbl 0649.65061
[67] Benzi, Block preconditioning for saddle point systems with indefinite (1, 1) block, International Journal of Computer Mathematics 84 (8) pp 1117– (2007) · Zbl 1123.65028
[68] Benzi, An augmented Lagrangian-based approach to the Oseen problem, SIAM Journal on Scientific Computing 28 pp 2095– (2006) · Zbl 1126.76028
[69] Benzi M Olshanskii MA Wang Z http://www.mathcs.emory.edu/molshan/OLSH/publ.html
[70] Klawonn, Block-triangular preconditioners for saddle point problems with a penalty term, SIAM Journal on Scientific Computing 19 (1) pp 172– (1998) · Zbl 0917.73069
[71] Klawonn, Block triangular preconditioners for nonsymmetric saddle point problems: field-of-values analysis, Numerische Mathematik 81 pp 577– (1999) · Zbl 0922.65021
[72] Loghin, Analysis of preconditioners for saddle-point problems, SIAM Journal on Scientific Computing 25 pp 2029– (2004) · Zbl 1067.65048
[73] Olshanskii, Pressure Schur complement preconditioners for the discrete Oseen problem, SIAM Journal on Scientific Computing 29 pp 2686– (2007) · Zbl 1252.65070
[74] Pasciak, A multigrid preconditioner for the mixed formulation of linear plane elasticity, SIAM Journal on Numerical Analysis 44 (2) pp 478– (2006) · Zbl 1109.74049
[75] Wang, Overlapping Schwarz preconditioner for the mixed formulation of plane elasticity, Applied Numerical Mathematics. An IMACS Journal 54 (2) pp 292– (2005) · Zbl 1081.74044
[76] Arnold, Mixed finite elements for elasticity, Numerische Mathematik 92 (3) pp 401– (2002) · Zbl 1090.74051
[77] Arnold, Finite elements for symmetric tensors in three dimensions, Mathematics of Computation 77 (263) pp 1229– (2008) · Zbl 1285.74013
[78] Arnold, Mixed finite element methods for linear elasticity with weakly imposed symmetry, Mathematics of Computation 76 (260) pp 1699– (2007) · Zbl 1118.74046
[79] Hu, A saddle point approach to the computation of harmonic maps, SIAM Journal on Numerical Analysis 47 (2) pp 1500– (2009) · Zbl 1219.49030
[80] Mardal, An order optimal solver for the discretized Bidomain equations, Numerical Linear Algebra with Applications 14 (2) pp 83– (2007) · Zbl 1199.65111
[81] Sundnes, Multigrid block preconditioning for a coupled system of partial differential equations modeling the electrical activity in the heart, Computer Methods in Biomechanics and Biomedical Engineering 5 (6) pp 397– (2002)
[82] Sundnes, Computing the Electrical Activity in the Heart (2006)
[83] Lyche, Preconditioned iterative methods for scattered data interpolation, Advances in Computational Mathematics 17 (3) pp 237– (2002) · Zbl 0999.65120
[84] Mardal, Order optimal preconditioners for implicit Runge-Kutta schemes applied to parabolic PDEs, SIAM Journal on Scientific Computing 29 (1) pp 361– (2007) · Zbl 1133.65071
[85] Staff, Preconditioning of fully implicit Runge-Kutta schemes for parabolic PDEs, Modeling, Identification and Control 27 (2) pp 109– (2006)
[86] Girault, Springer Series in Computational Mathematics, in: Finite Element Methods for Navier-Stokes Equations (1986) · Zbl 0585.65077
[87] Mardal, Computational Partial Differential Equations using Diffpack-Advanced Topics (2003)
[88] Brezzi, Stabilized mixed methods for the Stokes problem, Numerische Mathematik 53 (1-2) pp 225– (1988) · Zbl 0669.76052
[89] Franca, Error analysis of some Galerkin least squares methods for the elasticity equations, SIAM Journal on Numerical Analysis 28 (6) pp 1680– (1991) · Zbl 0759.73055
[90] Hughes, A new finite element formulation for computational fluid dynamics: VII. The Stokes problem with various well-posed boundary conditions: symmetric formulations that converge for all velocity/pressure spaces, Computer Methods in Applied Mechanics and Engineering 65 pp 85– (1987) · Zbl 0635.76067
[91] Hughes, A new finite element formulation for computational fluid dynamics: V. Circumventing the Babuska-Brezzi condition: a stable Petrov-Galerkin formulation of the Stokes problem accommodating equal-order interpolations, Computer Methods in Applied Mechanics and Engineering 59 pp 85– (1986) · Zbl 0622.76077
[92] Rusten, Interior penalty preconditioners for mixed finite element approximations of elliptic problems, Mathematics of Computation 65 (214) pp 447– (1996) · Zbl 0857.65117
[93] Xu, The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids, Computing 56 pp 215– (1996) · Zbl 0857.65129
[94] Mardal, A robust finite element method for Darcy-Stokes flow, SIAM Journal on Numerical Analysis 40 pp 1605– (2002) · Zbl 1037.65120
[95] Tai, A discrete de Rham complex with enhanced smoothness, Calcolo 43 pp 287– (2006) · Zbl 1168.76311
[96] Schöberl, Multigrid methods for a parameter dependent problem in primal variables, Numerische Mathematik 84 pp 97– (1999) · Zbl 0957.74059
[97] Falk, Lecture Notes in Mathematics, in: Mixed Finite Elements Compatibility Conditions, and Applications pp 195– (1939)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.