Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VII
Wavelet Methods for Stationary PDEs and PDE-Constrained
Control Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Angela Kunoth
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Problem Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 An Abstract Operator Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Elliptic Boundary Value Problems . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Saddle Point Problems Involving Boundary Conditions . . . . . . . 7
2.4 PDE-Constrained Control Problems: Distributed Control . . . . . 10
2.5 PDE-Constrained Control Problems: Dirichlet Boundary Control 12
3 Wavelets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Norm Equivalences and Riesz Maps . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3 Representation of Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4 Multiscale Decomposition of Function Spaces . . . . . . . . . . . . . . . 19
4 Problems in Wavelet Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.1 Elliptic Boundary Value Problems . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Saddle Point Problems Involving Boundary Conditions . . . . . . . 35
4.3 Control Problems: Distributed Control . . . . . . . . . . . . . . . . . . . . . 37
4.4 Control Problems: Dirichlet Boundary Control . . . . . . . . . . . . . . 42
5 Iterative Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.1 Finite Systems on Uniform Grids . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.2 Adaptive Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
On Approximation in Meshless Methods . . . . . . . . . . . . . . . . . . . . . . 65
Jens Markus Melenk
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
1.2 The Notion of Optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2 Polynomial Reproducing Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
2.2 Approximation Properties of Systems Reproducing Polynomials 70
2.3 Construction of Shape Functions with the Moving Least Squares
Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.4 Bibliographical Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3 Approximation Properties of Radial Basis Functions . . . . . . . . . . . . . . 87
3.1 Analysis of a Class of RBFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
VIII Contents
3.2 Bibliographical Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4 Partition of Unity Method and Generalized FEM . . . . . . . . . . . . . . . . 93
4.1 Approximation Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.2 Example: Polynomial Local Approximation Spaces . . . . . . . . . . . 95
5 Examples of Operator Adapted Approximation Spaces . . . . . . . . . . . . 96
5.1 A One-Dimensional Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.2 Laplace’s Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.3 Helmholtz Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.4 Linear Elasticity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.5 Further Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.6 Local Approximation Spaces Obtained Numerically . . . . . . . . . . 105
5.7 Bibliographical Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6 Augmenting Classical FEM Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.1 Singular Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.2 Crack Propagation Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.3 Further Examples: The Generalized FEM . . . . . . . . . . . . . . . . . . 111
6.4 Bibliographical Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7 Enforcement of Essential Boundary Conditions . . . . . . . . . . . . . . . . . . 111
7.1 Conforming Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
7.2 Non-Conforming Methods: Lagrange Multiplier Methods and
Collocation Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3 Non-Conforming Methods: Penalty Method . . . . . . . . . . . . . . . . . 116
7.4 Non-Conforming Methods: Nitsche’s Method . . . . . . . . . . . . . . . . 119
A Results from Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
B Properties of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
C Approximation with Adapted Function Systems . . . . . . . . . . . . . . . . . 126
C.1 The Theory of Bergman and Vekua . . . . . . . . . . . . . . . . . . . . . . . . 126
C.2 Proof of Theorems 5.3, 5.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
C.3 Two-Dimensional Elasticity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Theory and Applications of Smoothed Particle Hydrodynamics143
Joseph J. Monaghan
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
2 Integral and Summation Interpolants . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
2.1 Errors in the Integral Interpolant . . . . . . . . . . . . . . . . . . . . . . . . . . 148
2.2 Errors in the Summation Interpolant . . . . . . . . . . . . . . . . . . . . . . . 149
2.3 Errors when the Particles are Disordered . . . . . . . . . . . . . . . . . . . 152
3 Euler Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
3.1 The SPH Continuity Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
3.2 The SPH Acceleration Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
3.3 The Thermal Energy Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
3.4 Dispersion of Sound Waves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
4 Tests of the SPH Euler Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.1 The Force Law in One Dimension . . . . . . . . . . . . . . . . . . . . . . . . . 162
Contents IX
4.2 The Equations of Motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.3 Oscillations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.4 SPH Results for Small Oscillations . . . . . . . . . . . . . . . . . . . . . . . . 165
5 Lagrangian SPH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
5.1 The Lagrangian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
5.2 Conservation Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
5.3 The Lagrangian with Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 172
5.4 Resolution Varying in Space and Time . . . . . . . . . . . . . . . . . . . . . 174
6 SPH Heat Conduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
6.1 Derivatives from Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
6.2 Does the Entropy Increase? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
6.3 Discontinuous Thermal Conductivity. . . . . . . . . . . . . . . . . . . . . . . 180
6.4 Diffusion of Matter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7 Viscosity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.1 A Simple Artificial Shock Viscosity . . . . . . . . . . . . . . . . . . . . . . . . 183
7.2 Invariance Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.3 Effective Pressure and Viscosity . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
7.4 The Sign of the Dissipation Term . . . . . . . . . . . . . . . . . . . . . . . . . . 186
8 Applications to Shock and Rarefaction Problems . . . . . . . . . . . . . . . . . 187
8.1 Rarefaction Waves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
8.2 The Sod Shock Tube. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
Implementation and Parallelization of Meshfree Methods . . . . . 195
Marc Alexander Schweitzer
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
2 Partition of Unity Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
2.1 Construction of a Partition of Unity Space. . . . . . . . . . . . . . . . . . 197
2.2 Variational Formulation and Boundary Conditions . . . . . . . . . . . 204
2.3 Galerkin Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
2.4 Solution of Resulting Linear System . . . . . . . . . . . . . . . . . . . . . . . 210
3 Efficient Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
3.1 Cover Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
3.2 Numerical Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
3.3 Multilevel Solution of Linear System . . . . . . . . . . . . . . . . . . . . . . . 231
4 Parallelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
4.1 Parallel Data Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
4.2 Load Balancing with Space Filling Curves . . . . . . . . . . . . . . . . . . 248
4.3 Parallel Cover Construction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
4.4 Parallel Neighbour Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
4.5 Parallel Matrix Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
4.6 Parallel Multilevel Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
4.7 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258