The main thesis of the work is to develop a formal description of a wide class of adaptive mesh-based 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 grammar-based formal description of the adaptive mesh-based 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 super-tasks. 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 inter-task communication channels. They constitute the grain for the decomposition of the parallel algorithm for the distributed memory architecture. Finally, the super-tasks correspond to a group of tasks resulting from the execution of load balancing algorithm. The graph grammar-based model will be developed for the self-adaptive hp Finite Element Method (hp-FEM), which is the most complicated adaptive mesh-based algorithm, intended for high accuracy numerical solutions of a weak form of elliptic and Maxwell Partial Differential Equations (PDE). Most other mesh-based adaptive algorithms are embedded into the self-adaptive hp-FEM, thus the developed formalism can be also applied to other algorithms of this class. The particular adaptive algorithms considered in this work employ the two-grid 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 self-adaptive hp-FEM algorithm. Many challenging engineering problems, including material science, geo-science and remote sensing, nano-lithography (micro-cheap 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 self-adaptive hp-FEM algorithm. On the other hand, the applicability of the two-grid 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 mesh-based algorithms.
Wydawnictwa nie prowadzą sprzedaży książek z serii "Rozprawy Monografie". Zainteresowanych prosimy o kontakt z ich autorami.
- Spis treści
-
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 mesh-based algorithms 41
1.3.1. Sequential algorithms for the self-adaptive hp-FEM 41
1.3.2. Parallel algorithms for non-uniform adaptive FEM 42
1.3.2.1. Non-uniform non-automatic h refinements 43
1.3.2.2. Non-uniform non-automatic 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 grammar-driven PDE solvers 55
2.1. Graph grammar model with atomic tasks for the self-adaptive 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 self-adaptive 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. Run-time 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 super-tasks for the self-adaptive 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 self-adaptive hp-FEM 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 self-adaptive hp-FEM 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 self-adaptive hp-FEM algorithm in three dimensions, with the grain defined on the level of initial mesh elements and with multi-level parallel solver 177
2.6.4. Scalability of the parallel self-adaptive hp-FEM algorithm in two and half dimensions, with the grain defined on the level of initial mesh elements and with multi-level multi-frontal direct substructuring parallel solver 182
2.6.5. Comparison of the scalability of the multi-level multi-frontal direct sub-structuring parallel solve with the MUMPS parallel solver 189
3. Applications 196
3.1. Two-dimensional applications 197
3.1.1. L-shape 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. Three-dimensional 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 Al-Si 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 non-orthogonal 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 through-casing 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 – Self-adaptive hp-FEM algorithm 242
Appendix C – Technical details on implementation 251
C.1. Parallel two-dimensional self-adaptive hp-FE code par2Dhp90 251
C.2. Parallel three-dimensional self-adaptive hp-FE code par3Dhp90 257
Appendix D – Direct solvers algorithms 265
D.1. Multiple front algorithm 265
D.2. Multi-level parallel direct solver algorithm 268
D.3. Multi-level multi-frontal direct sub-structuring parallel solver algorithm 270
References 276