Table of Contents
Preface v
1 Introduction 1
1.1 Finite element method (FEM) 1
1.1.1 The elliptic model problem 1
1.1.2 Conforming discretizations 4
1.1.3 Nonconforming discretizations 5
1.1.4 Structure and properties of the stiffness matrix 8
1.2 Ill-conditioned problems 10
1.2.1 Anisotropic problems 10
1.2.2 Problems with highly varying coefficients 10
1.2.3 Elastic deformation of almost incompressible materials 11
1.2.4 High-Reynolds-number flow 12
1.3 Preliminaries on iterative methods 13
1.3.1 Stationary methods 13
1.3.2 Polynomial acceleration 15
1.4 Conjugate gradients (CG) 18
1.4.1 From steepest descent to conjugate gradients 18
1.4.2 Convergence analysis of the CG method 20
1.4.3 Preconditioned conjugate gradient (PCG) method 24
1.4.4 Generalized conjugate gradient (GCG) method 26
2 Algebraic multilevel iteration methods 29
2.1 Block-factorization: Schur complement 29
2.2 Local estimates of the CBS constant 31
2.3 Two-level preconditioning methods 34
2.3.1 Algebraic two-level methods 34
2.3.2 Two-level preconditioners for FEM systems 37
2.4 Linear AMLI methods 38
2.5 Nonlinear AMLI methods 43
2.6 Optimality conditions 48
2.7 Robustness of the AMLI methods 51
2.7.1 Local analysis of the model problem 51
2.7.2 Robust preconditioning strategy 53
2.7.3 Hierarchical error estimators 54
3 Robust AMLI algorithms: Conforming linear finite elements 57
3.1 Some basic relations 57
3.2 Uniform estimates of the constant in the strengthened CBS inequality 62
3.3 Additive preconditioning of the pivot block 66
3.4 Multiplicative preconditioning of the pivot block 69
3.5 Locally improved estimates of the AMLI parameters 72
3.6 Optimal complexity solution algorithms for systems with C11 73
3.6.1 A model problem 73
3.6.2 Additive algorithm 74
3.6.3 Multiplicative algorithm 74
4 Robust AMLI algorithms: Nonconforming linear finite elements 77
4.1 Crouzeix-Raviart finite elements 77
4.2 Two-level splittings: "First Reduce" and "Differences and Aggregates" 79
4.3 Uniform estimates of the CBS constant in case of non-nested spaces 81
4.4 Preconditioning of the pivot block 95
4.5 Numerical results 98
4.5.1 Concluding remarks 100
5 Schur complement based multilevel preconditioners 102
5.1 Hierarchical versus standard nodal-basis 102
5.2 A general two-level preconditioner 102
5.3 Incomplete factorization based on exact local factorization 107
5.4 Local Schur complements 112
5.5 Numerical results 114
6 Algebraic multigrid (AMG) 117
6.1 Two-grid and multigrid algorithms 118
6.1.1 Exact two-level method 118
6.1.2 From two-grid to multigrid 119
6.2 Main components of algebraic multigrid 120
6.2.1 Coarse-grid correction 120
6.2.2 Smoothing 121
6.2.3 Interpolation 123
6.3 A simple convergence result 125
6.4 Error propagation of AMG and AMLI methods 127
6.5 Classical AMG 131
6.5.1 Strong connections 131
6.5.2 Coarse-grid selection 131
6.5.3 Interpolation 132
6.6 Smoothed aggregation and adaptive AMG methods 132
6.7 Utilizing AMG components in AMLI 134
7 Preconditioning of Rannacher-Turek nonconforming FE systems 136
7.1 Rannacher-Turek nonconforming FE systems 136
7.1.1 The nonconforming FE problem 136
7.1.2 Rotated bilinear elements 137
7.1.3 Rotated trilinear elements 138
7.2 Hierarchical two-level splittings: 2D case 140
7.2.1 First reduce two-level splitting 140
7.2.2 Two-level splitting by differences and aggregates 143
7.2.3 Uniform estimates of the CBS constant for the 2D splittings 144
7.3 Hierarchical two-level splittings: 3D case 147
7.3.1 First reduce two-level splitting 147
7.3.2 Two-level splitting by differences and aggregates 150
7.3.3 Uniform estimates of the CBS constant for the 3D splittings 152
7.4 Multilevel preconditioning 155
7.5 Numerical tests 158
7.5.1 Additive and multiplicative AMLI preconditioners in 2D 158
7.5.2 Problems with jumping coefficients in 3D 159
8 AMLI algorithms for discontinuous Galerkin FE problems 164
8.1 Introduction to discontinuous Galerkin FEM 164
8.2 Element-based approach: bilinear DG systems 166
8.3 Face-based approach: Rotated bilinear DG systems 177
8.4 Two-level method and AMLI preconditioning of graph-Laplacians 186
9 AMLI methods for coupled problems 196
9.1 AMLI preconditioning of linear elasticity problems 196
9.1.1 Lam? system of elasticity 196
9.1.2 On the robustness of AMLI for conforming FE elasticity systems 198
9.1.3 Locking-free AMLI methods for Crouzeix-Raviart FE discretization of the pure displacement elasticity problem 205
9.2 Optimal order AMLI preconditioning of the Navier-Stokes problem 211
9.2.1 Crouzeix-Raviart FE discretization of the velocity field 211
9.2.2 AMLI preconditioning of the mixed FE system: weighted graph-Laplacian 213
10 Practical issues 219
10.1 Linear AMLI algorithm 219
10.2 Nonlinear AMLI algorithm 223
10.3 Case study: Integrating of new AMLI solvers 225
10.3.1 Crouzeix-Raviart FE discretization of 3D pure displacement elasticity problems 226
10.3.2 Composite FR algorithm 228
10.3.3 Numerical tests: Towards μFEM analysis of bone structures 232
Bibliography 237
Index 245
