James F. Blowey Alan W. Craig (Eds.) Frontiers of Numerical Analysis Durham 2004 ABC JamesF.Blowey AlanW.Craig DepartmentofMathematicalSciences DepartmentofMathematicalSciences UniversityofDurham UniversityofDurham SouthRoad SouthRoad DH13LEDurham DH13LEDurham UnitedKingdom UnitedKingdom E-mail:[email protected] E-mail:[email protected] MathematicsSubjectClassification:35-XX,65-XX,70-08 LibraryofCongressControlNumber:2005927222 ISBN-10 3-540-23921-9SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-23921-5SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation,broadcasting, reproductiononmicrofilmorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9, 1965,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsare liableforprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springeronline.com (cid:1)c Springer-VerlagBerlinHeidelberg2005 PrintedinTheNetherlands Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply, evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotectivelaws andregulationsandthereforefreeforgeneraluse. Typesetting:bytheauthorsandTechBooksusingaSpringerLATEXmacropackage Coverdesign:Coverdesign:design&productionGmbH,Heidelberg Printedonacid-freepaper SPIN:11357292 46/TechBooks 543210 Preface TheEleventhLMS-EPSRCComputationalMathematicsandScientificCom- puting Summer School was held at the University of Durham, UK, from the 4th of July to the 9th of July 2004. This was the third of these schools to be held in Durham, having previously been hosted by the University of Lan- caster and the University of Leicester. The purpose of the summer school was to present high quality instructional courses on topics at the forefront of computational mathematics and scientific computing research to postgradu- ate students. The main speakers were Emmanuel Candes, Markus Melenk, Joe Monaghan and Alex Schweitzer. This volume presents written contributions three of our speakers which are more comprehensive versions of the high quality lecture notes which were distributedtoparticipantsduringthemeeting.Wearealsoextremelypleased that Angela Kunoth was able to make an additional contribution from the ill-fated first week. At the time of writing it is now more than two years since we first contacted theguestspeakersandduringthatperiodtheyhavegivensignificantportions of their time to making the summer school, and this volume, a success. We wouldliketothankallofthemforthecarewhichtheytookinthepreparation and delivery of their material. Instrumentaltotheschoolwerethetwotutorswhoranaverysuccessfultuto- rialprogramme(PeterJohnson&AngelaMihai).Therewasalsoasuccessful programme of contributed talks from eleven students in the afternoons. The UKIEsectionofSIAMcontributedprizesforthebesttalksgivenbygraduate students. The invited speakers took on the bulk of the task of judging these talks. After careful and difficult consideration, and after canvassing opinion from other academics present, the prizes were awarded to Patrick Lechner (Bath University) and Richard Welford (Sussex University), see figure be- low. The general quality of the student presentations was impressively high promising a vibrant future for the subject. The audience covered a broad spectrum, thirty-seven participants ranging from research students to academics. As always, one of the most important aspects of the summer school was providing a forum for numerical analysts, both young and old, to meet for an extended period and exchange ideas. We would also like to thank the Grey College for their hospitality in hosting the participants, the Durham postgraduates who together with those who hadattendedthepreviousSummerSchoolranthesocialprogramme,Rachel Duke, Fiona Giblin and Mary Bell for their secretarial support and our fam- ilies for supporting our efforts. VI Preface We thank the LMS and the Engineering and Physical Sciences Research Council for their financial support which covered all the costs of the main speakers, tutors, plus the accommodation costs of the participants. James F. Blowey and Alan W. Craig Durham, April 2005 Patrick Lechner & Richard Welford being presented with the UKIE section of SIAM prizes for the best talks given by graduate students by Joe Monaghan. Contents 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-ConstrainedControlProblems:DirichletBoundaryControl 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 ConstructionofShapeFunctionswiththeMovingLeastSquares 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 Wavelet–Based Multiresolution Methods for Stationary PDEs and PDE-Constrained Control Problems Angela Kunoth Universit¨at Bonn, Institut fu¨r Angewandte Mathematik, Wegelerstr. 6, 53115 Bonn, Germany email: [email protected] Abstract These notes are concerned with numerical analysis issues arising in the solution of certain classes of stationary linear variational problems. The standard examples are second order elliptic boundary value problems, where particular em- phasisisplacedonthetreatmentofessentialboundaryconditions.Theseoperator equations serve as a core ingredient for control problems where in addition to the state, the solution of the PDE, a control is to be determined which together with the state minimizes a certain tracking-type objective functional. Having assured that the variational problems are well-posed, we propose numerical schemes based onwaveletsasaparticularmultiresolutiondiscretizationmethodology.Theguiding principle is to devise fast and efficient solution schemes which are optimal in the numberofarithmeticunknowns.Issuesthataredealtwithareoptimalconditioning of the system matrices, numerical stability of discrete formulations and adaptive approximation. 1 Introduction For the solution of elliptic partial differential equations (PDEs), multilevel ingredientshaveprovedtoachievemoreefficientsolutionmethodsforavari- etyofproblemsthanmethodsbasedonapproximatingonasinglescale.This is due to the fact that solutions often exhibit a multiscale behaviour which one naturally wants to exploit. Perhaps the first such schemes were multi- grid methods where a fixed discretization, with respect to some underlying uniform fine grid, leads a large ill-conditioned system of linear equations to solve. The basic idea of multigrid schemes is to successively solve smaller versionsofthelinearsystemwhichcanbeinterpretedasdiscretizationswith respect to coarser grids. Here ‘efficiency of the scheme’ means that one can solve the problem with respect to the fine grid with a number of arithmetic operations which is proportional to the number of unknowns on the finest grid. This in turn means that multigrid schemes provide an asymptotically optimal preconditioner for the original system on the finest grid. The search for such optimal preconditioners was one of the major topics in the solution of elliptic boundary value problems for many years. Another multiscale pre- conditionerwhichhasthispropertyistheBPX-preconditionerproposedfirst 2 A. Kunoth in [BPX] which was proved to be asymptotically optimal with techniques from Approximation Theory in [DK1,O]. Wavelets as a particular example of a multiscale basis were constructed with compact support in the 1980’s [Dau]. While mainly used for signal analysis andimagecompression,theywerealsodiscoveredtoprovideoptimalprecon- ditioners in the above sense for elliptic boundary value problems [DK1,J]. It was soon realized that biorthogonal spline-wavelets developed in [CDF] are better suited for the numerical solution of elliptic PDEs since they allow one to work with piecewise polynomials instead of the implicitly defined original wavelets [Dau] (in addition to the fact that orthogonality with respect to L 2 oftheDaubechieswaveletsisonlyaminoradvantageforellipticPDEs).The principalingredientthatallowsonetoproveoptimalityofthepreconditioner are certain norm equivalences between Sobolev norms and sequence norms of weighted wavelet expansion coefficients, and optimal conditioning of the resulting linear system of equations can be achieved by applying the Fast Wavelet Transform together with a weighting in terms of an appropriate di- agonal matrix. The terminology ‘wavelets’ here and in the sequel is to mean thatthesearenotnecessarilyDaubechies’wavelets,butratherclassesofsuch multiscale bases with three main properties: (R) Riesz basis property for the underlying function spaces; (L) locality of the basis functions; (CP) cancellation properties; all of which are detailed in Section 3.1. Aftertheseinitialresults,researchonusingwaveletsforsolvingellipticPDEs numerically has gone into many different directions. Since the original con- structions in [Dau,CDF] and many others are based on using the Fourier transform, these constructions provide bases for function spaces only on all of R or Rn. In order for these tools to be applicable for the solution of PDEs which naturally live on a bounded domain Ω ⊂ Rn, there arose the need for having available constructions on bounded intervals without, of course, losing the aforementioned properties (R), (L) and (CP). The first such sys- tematic construction of biorthogonal spline-wavelets on [0,1] (and, by tensor products, on [0,1]n) was provided in [DKU]. At the same time, techniques for satisfying essential boundary conditions were investigated in the context of wavelets in [K1]. Aside from the investigations to provide appropriate bases, the built-in po- tential of adaptivity for wavelets has played a prominent role when solving PDEs,onaccountofthefactthatwaveletsprovidealocallysupportedRiesz basis for a whole function space. Here the issue is to approximate the so- lution of the variational problem on an infinite-dimensional function space by the fewest number of degrees of freedom up to a certain prescribed accu- racy. Most approaches use wavelet coefficients in a heuristic way, i.e., judg- ing approximation quality by the size of the wavelet coefficients together