The main thesis of the work is to develop a formal description of a wide class of adaptive meshbased algorithms, which will allow us to examine their concurrency, as well as to design and to implement an efficient parallel version of the algorithms. The way to achieve this goal is to develop a graph grammarbased formal description of the adaptive meshbased algorithms. The graph grammar model makes it possible to examine the concurrency of the algorithms by analysing the interdependence between the atomic tasks, tasks and supertasks. The atomic tasks correspond to the graph grammar productions, representing basic undividable parts of the algorithms. The level of atomic tasks models the concurrency for the shared memory architectures. On the other hand, the tasks correspond to the groups of atomic tasks with predefined intertask communication channels. They constitute the grain for the decomposition of the parallel algorithm for the distributed memory architecture. Finally, the supertasks correspond to a group of tasks resulting from the execution of load balancing algorithm. The graph grammarbased model will be developed for the selfadaptive hp Finite Element Method (hpFEM), which is the most complicated adaptive meshbased algorithm, intended for high accuracy numerical solutions of a weak form of elliptic and Maxwell Partial Differential Equations (PDE). Most other meshbased adaptive algorithms are embedded into the selfadaptive hpFEM, thus the developed formalism can be also applied to other algorithms of this class. The particular adaptive algorithms considered in this work employ the twogrid paradigm, with the coarse meshes and their corresponding fine meshes. The algorithms generate a sequence of coarse meshes, delivering convergence of the numerical error of a considered problem, with respect to the mesh size. They use the corresponding fine mesh to estimate the quality of the coarse mesh in order to select the optimal refinements to be performed. The creation of an efficient parallel version of the algorithm is critical for most applications, since the computational cost related to the adaptive computations is large. The particular result of this work is the parallel adaptive software system that implements the selfadaptive hpFEM algorithm. Many challenging engineering problems, including material science, geoscience and remote sensing, nanolithography (microcheap production process) and wave propagation problems, require 4, high accuracy of a numerical solution. It is impossible to find such a solution using other numerical methods. These problems will be finally solved by the developed software system, thanks to the exponential convergence of the selfadaptive hpFEM algorithm. On the other hand, the applicability of the twogrid paradigm adaptive algorithms is not limited only to the PDE engineering problems. Any problem that requires a construction of the finite dimensional approximation space based on polynomials of different orders covering finite element mesh fits into the class of adaptive meshbased algorithms.
Wydawnictwa nie prowadzą sprzedaży książek z serii "Rozprawy Monografie". Zainteresowanych prosimy o kontakt z ich autorami.
 Contents

Summary 11
Streszczenie 13
Index of symbols 15
Acknowledgements 29
1. Preface 31
1.1. Main thesis and structure of the book 31
1.2. Introduction 34
1.2.1. Introduction to the Finite Element Method 34
1.2.2. Introduction to the mesh adaptation techniques 37
1.3. State of art of adaptive meshbased algorithms 41
1.3.1. Sequential algorithms for the selfadaptive hpFEM 41
1.3.2. Parallel algorithms for nonuniform adaptive FEM 42
1.3.2.1. Nonuniform nonautomatic h refinements 43
1.3.2.2. Nonuniform nonautomatic hp refinements 45
1.3.2.3. Different parallelization methods for adaptive FE algorithms 50
1.3.3. Parallel solvers for adaptive FE algorithms 50
1.3.4. Graph grammar models 52
1.3.5. Analysis of computational and communication complexities of adaptive algorithms 52
1.4. Summary of open problems 53
1.5. Summary of my research 53
2. Graph grammardriven PDE solvers 55
2.1. Graph grammar model with atomic tasks for the selfadaptive algorithm 66
2.1.1. Algorithm of initial mesh generation 67
2.1.2. Algorithm of solution of coarse mesh problem 73
2.1.3. Algorithm of global hp refinement 86
2.1.4. Algorithm of solution of fine mesh problem 96
2.1.5. Algorithm of selection and execution of the optimal mesh refinements 111
2.1.6. The stopping condition 118
2.2. Definition of computational tasks (grains) for parallel processing model of the selfadaptive algorithm 118
2.2.1. Generation of the initial mesh 122
2.2.2. Solution of coarse mesh problem 125
2.2.3. h refinement 130
2.2.4. p refinement 132
2.2.5. Solution of fine mesh problem 133
2.2.6. Selection of the optimal refinements 134
2.3. Runtime management algorithms 136
2.3.1. Load balancing and graph partitioning algorithms 136
2.3.2. Mapping algorithm 142
2.4. Parallel processing model with supertasks for the selfadaptive algorithm 143
2.5. Theoretical analysis of the computational and communication complexities 150
2.5.1. Mesh partitioning algorithms 150
2.5.2. Mesh adaptation algorithms 152
2.5.3. Solver algorithms 153
2.5.4. Reutilization of partial LU factorizations 158
2.6. Simulational study of scalability 161
2.6.1. Scalability of the parallel selfadaptive hpFEM algorithm in two dimensions, with the grain defined on the level of initial mesh elements and with multiple front parallel solver 161
2.6.2. Scalability of the parallel selfadaptive hpFEM algorithm in three dimensions, with the grain defined on the level of initial mesh elements and with multiple front parallel solver 170
2.6.3. Scalability of the parallel selfadaptive hpFEM algorithm in three dimensions, with the grain defined on the level of initial mesh elements and with multilevel parallel solver 177
2.6.4. Scalability of the parallel selfadaptive hpFEM algorithm in two and half dimensions, with the grain defined on the level of initial mesh elements and with multilevel multifrontal direct substructuring parallel solver 182
2.6.5. Comparison of the scalability of the multilevel multifrontal direct substructuring parallel solve with the MUMPS parallel solver 189
3. Applications 196
3.1. Twodimensional applications 197
3.1.1. Lshape domain model problem 197
3.1.1.1. Strong formulation 198
3.1.1.2. Weak formulation 198
3.1.1.3. Results 199
3.1.2. Battery problem 200
3.1.2.1. Strong formulation 201
3.1.2.2. Weak formulation 202
3.1.2.3. Results 202
3.2. Threedimensional applications 204
3.2.1. Fichera model problem 204
3.2.1.1. Strong formulation 204
3.2.1.2. Weak formulation 205
3.2.1.3. Results 205
3.2.2. Resistance heating of the AlSi billet in steel die 206
3.2.2.1. Strong formulation 208
3.2.2.2. Weak formulation 208
3.2.2.3. Results 208
3.2.3. Step and Flash Imprint Lithography simulation 210
3.2.3.1. Strong formulation 212
3.2.3.2. Weak formulation 213
3.2.3.3. Results 214
3.2.4. 3D DC/AC borehole resistivity measurement simulations in deviated wells with nonorthogonal system of coordinates 215
3.2.4.1. Strong formulation 216
3.2.4.2. Weak formulation 216
3.2.4.3. Results 218
3.2.5. 3D DC/AC borehole resistivity measurement simulations with throughcasing instruments in deviated wells 220
3.2.5.1. Strong formulation 222
3.2.5.2. Weak formulation 222
3.2.5.3. Results 223
4. Conclusions and future work 226
4.1. Summary of obtained results 226
4.2. Significance of obtained results 228
4.3. Current and future work 230
Appendix A – hp finite element 234
Appendix B – Selfadaptive hpFEM algorithm 242
Appendix C – Technical details on implementation 251
C.1. Parallel twodimensional selfadaptive hpFE code par2Dhp90 251
C.2. Parallel threedimensional selfadaptive hpFE code par3Dhp90 257
Appendix D – Direct solvers algorithms 265
D.1. Multiple front algorithm 265
D.2. Multilevel parallel direct solver algorithm 268
D.3. Multilevel multifrontal direct substructuring parallel solver algorithm 270
References 276