An introduction to multigrid methods

COVER
......Page 1
AN IN TRODUCTlON TO MULTIGRID METHODS......Page 3
CONTENTS......Page 9
PREFACE......Page 11
Significance of multigrid methods for scientific computation......Page 12
Historical development of multigrid methods......Page 13
Notation......Page 14
One-dimensional model problem......Page 15
Fourier analysis of convergence......Page 16
The essential multigrid principle......Page 17
Fourier smoothing analysis......Page 18
Coarse grid approximation......Page 19
Linear two-grid algorithm......Page 21
Coarse grid correction......Page 22
Again: the essential principle......Page 23
3.2. An elliptic equation......Page 25
The weak formulation......Page 26
Finite difference discretization......Page 27
An interface problem......Page 28
Finite volume discretization......Page 29
Discontinuity inside a finite volume......Page 31
Vertex-centred grid......Page 32
Boundary conditions......Page 33
Finite volume discretization......Page 34
Discontinuous coefficients......Page 36
Cell-centred grid......Page 38
Finite volume discretization......Page 39
Boundary conditions......Page 40
The mesh PCclet number condition......Page 41
Upwind discretization......Page 42
Boundary conditions......Page 43
Hyperbolic system of conservation laws......Page 44
Finite volume discretization......Page 45
Basic iterative methods......Page 47
Convergence......Page 49
Regular splittings and M- and K-matrices......Page 50
Rate of convergence......Page 52
Block Gauss-Seidel.......Page 53
Diagonal ordering......Page 54
A solution method for tridiagonal systems......Page 55
Vectorized and parallel computing......Page 57
Incomplete point factorization......Page 58
Five-point ILU......Page 59
Seven-point ILU......Page 60
Nine-point ILU......Page 61
Alternating ILU......Page 62
General ILU......Page 63
Complete line LU factorization......Page 64
Nine-point IBLU......Page 65
The IBLU iterative method......Page 67
Defect correction......Page 68
Distributive iteration......Page 69
6.1. Introduction......Page 90
Explicit formula for coarse grid operator......Page 91
Calculation of coarse grid operator by computer......Page 92
Structure of coarse grid operator stencil......Page 93
Eigenstructure of RAP......Page 95
Loss of K-matrix property under RAP......Page 96
Consistency condition......Page 97
Solvability of coarse grid equation......Page 98
Making the solution unique......Page 99
The smoothing iteration matrix......Page 100
Two-grid rate of convergence; smoothing and approximation properties......Page 101
An algebraic definition of smoothness......Page 103
Smoothing factors......Page 104
6.6. A numerical illustration......Page 105
Coarse grids......Page 71
Stencil notation for operators of type U -> U......Page 73
Stencil notation for restriction operators......Page 74
The relation between the stencil of an operator and that of its adjoint......Page 75
Stencil notation for prolongation operators......Page 76
Vertex-centred prolongations......Page 77
Cell-centred prolongations......Page 79
Boundary modifications......Page 80
Restrictions......Page 81
Accuracy condition for transfer operators......Page 82
One-dimensional example......Page 84
Two-dimensional case......Page 86
The prolongation operator of de Zeeuw......Page 87
A class of smoothing methods......Page 107
The smoothing property and convergence......Page 108
The one-dimensional case......Page 109
Dirichlet boundary conditions......Page 111
The multi-dimensional case......Page 113
Dirichlet boundary conditions......Page 114
Additional remarks......Page 115
Definition of the local mode smoothing factor......Page 116
Aliasing......Page 117
Smooth and rough Fourier modes......Page 118
Semi-coarsening......Page 120
Mesh-size independent definition of smoothing factor......Page 121
Modification of smoothing factor for Dirichlet boundary conditions......Page 122
Explicit expression for the amplification factor......Page 123
Justification of Definitions (7.4.28) and (7.4.29)......Page 125
Test problems......Page 126
Numerical calculation of Fourier smoothing factor......Page 128
Anisotropic diffusion equation
Point Jacobi......Page 129
Dirichlet boundary conditions......Page 130
Line Jacobi......Page 131
Line Jacobi......Page 133
Anisotropic diffusion equation Point Gauss-Seidel......Page 134
Line Gauss-Seidel......Page 136
Point Gauss-Seidel......Page 139
Line Gauss-Seidel......Page 142
Five-point ILU......Page 143
Behaviour of elements of L, D, U away from grid boundaries......Page 144
Smoothing factor of five-point ULU......Page 145
Anisotropic diffusion equation......Page 146
Seven-point ILU......Page 147
Anisotropic diffusion equation......Page 149
Convection-diffusion equation......Page 151
Nine-point ILU......Page 152
Anisotropic diffusion equation......Page 153
Alternating seven-point ILU......Page 154
Convection-diffusion equation......Page 155
Smoothing analysis......Page 156
Anisotropic diffusion equation......Page 157
The amplification matrix......Page 159
The smoothing factor......Page 160
White-black Gauss-Seidel......Page 161
Smoothing factor of zebra Gauss-Seidel......Page 163
Smoothing factor of alternating zebra Gauss-Seidel......Page 165
Anisotropic diffusion equation......Page 166
Convection-diffusion equation......Page 167
Smoothing factor of alternating white-black Gauss-Seidel for the convection-diffusion equation......Page 168
Artificial time-derivative......Page 171
Semi-iterative methods......Page 172
The smoothing factor......Page 173
One-stage method......Page 174
A four-stage method......Page 175
A five-stage method......Page 176
Final remarks......Page 177
7.12. Concluding remarks......Page 178
Preliminaries......Page 179
Discussion......Page 180
The linear two-grid algorithm......Page 181
Choice of u^k-1and s_k-1......Page 182
The recursive non-linear multigrid algorithm......Page 183
Multigrid schedules......Page 184
Recursive algorithm for V-, F- and W-cycle......Page 185
Adaptive schedule......Page 186
Storage requirements......Page 187
Computational work......Page 188
The algorithm......Page 192
Choice of prolongation operator......Page 193
Computational cost of nested iteration......Page 194
The multigrid iteration matrix......Page 195
Rate of convergence......Page 196
Preliminaries......Page 199
Recursion for the error of nested iteration......Page 200
Accuracy of prolongation in nested iteration......Page 201
Error after nested iteration......Page 202
Less accurate prolongation......Page 203
FORTRAN implementation of while clause......Page 205
FORTRAN subroutine......Page 206
Testing of multigrid software......Page 209
8.8. Remarks on software......Page 210
8.9. Comparison with conjugate gradient methods......Page 211
Conjugate gradient acceleration of basic iterative methods......Page 212
Rate of convergence......Page 213
Conjugate gradient acceleration of multigrid......Page 214
The non-symmetric case......Page 215
Comparison of conjugate gradient and multigrid methods......Page 216
Grid generation......Page 218
Computational complexity of computational fluid dynamics......Page 219
Navier-Stokes equations......Page 221
Euler and potential equations......Page 222
Boundary conforming grids......Page 223
Some tensor analysis......Page 224
Generation of structured boundary conforming grids......Page 225
An example: generation of a grid around an airfoil......Page 227
Invariant formulation of the full potential equation......Page 228
Determination of the circulation......Page 229
Finite volume discretization......Page 230
Retarded density......Page 231
Smoothing method......Page 232
9.5. The Euler equations of gas dynamics......Page 234
Finite volume discretization......Page 235
Flux splitting......Page 236
Time discretization......Page 238
Multigrid method......Page 239
Smoothing method......Page 240
Defect correction......Page 241
Finite volume discretization......Page 242
Discretization of viscous terms......Page 243
Turbulence......Page 244
The governing equations......Page 245
The staggered grid......Page 246
Finite volume discretization......Page 247
Hybrid scheme For convective terms......Page 248
Linearization of convection terms......Page 250
Boundary conditions......Page 251
Summary of the discrete equations......Page 252
Further remarks on the discretization of the incompressible Navier-Stokes equations......Page 253
Distributive iteration......Page 254
Distributive Gauss-Seidel smoothing method......Page 256
SIMPLE method......Page 257
Symmetric coupled Gauss-Seidel method......Page 258
Coarse grid approximation......Page 261
Restriction......Page 262
Prolongation......Page 263
Application to a free convection flow......Page 264
Application of a multigrid method......Page 265
The stationary case......Page 266
Literature......Page 268
9.8. Final remarks......Page 269
REFERENCES......Page 270
INDEX......Page 285