Robust Algebraic Multilevel Methods and Algorithms

by Johannes Kraus, Svetozar Margenov

Overview

This book deals with algorithms for the solution of linear systems of algebraic equations with large-scale sparse matrices, with a focus on problems that are obtained after discretization of partial differential equations using finite element methods. The authors provide a systematic presentation of the recent advances in robust algebraic multilevel methods and algorithms, e.g., the preconditioned conjugate gradient method, algebraic multilevel iteration (AMLI) preconditioners, the classical algebraic multigrid (AMG) method and its recent modifications, namely AMG using element interpolation (AMGe) and AMG based on smoothed aggregation.

The first six chapters can serve as a short introductory course on the theory of AMLI methods and algorithms. The next part of the monograph is devoted to more advanced topics, including the description of new generation AMG methods, AMLI methods for discontinuous Galerkin systems, looking-free algorithms for coupled problems etc., ending with important practical issues of implementation and challenging applications. This second part is addressed to some more experienced students and practitioners and can be used to complete a more advanced course on robust AMLI and AMG methods and their efficient application.

This book is intended for mathematicians, engineers, natural scientists etc.

Product Details

ISBN-13:	9783110193657
Publisher:	De Gruyter
Publication date:	09/16/2009
Series:	Radon Series on Computational and Applied Mathematics , #5
Pages:	256
Product dimensions:	6.90(w) x 9.60(h) x 0.70(d)
Age Range:	18 Years

About the Author

Johannes Kraus, Radon Institute for Computational and Applied Mathematics, Linz, Austria;
Svetozar Margenov, Institute for Parallel Processing, Sofia, Bulgaria.

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 C₁₁ 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

Editorial Reviews

"The book will nd its readers in the people who are interested in (algebraic) multigrid."
Dietrich Braess in Zentralblatt MATH 1/2010

From the Publisher