Skip to main content

Banery wysuwane

pomarańczowa, liternicza okładka seryjna
Graph Grammar-Driven Parallel Adaptive PDE Solvers

Product category
Nauki techniczne
Nauki techniczne » Informatyka
ISSN
0867-6631
Publication type
monografia
Format
B5
Binding
miękka
Number of pages
282
Publication date
2009
Description

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.

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 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

Price
0.00
In order to arrange international shipping details and cost please contact wydawnictwa@agh.edu.pl