【作者】 陈建军；

【导师】 郑耀；

【作者基本信息】 浙江大学 ， 计算机应用技术， 2006， 博士

【摘要】 网格生成技术是数值求解的前处理过程,也是后者应用时的主要性能瓶颈。随着大规模工程与科学计算需求的日益迫切,并行网格生成技术的研究在国际上已成为一个新的研究热点,但在国内却鲜有人关注。本文就非结构化网格生成及其并行化研究领域的若干问题进行了深入的研究。 首先,本文构建了一个健壮有效的、适用于类三角形和类四边形区域的全四边形单元型模板方案,并将其引入区域分解法的子域网格生成环节,克服了现有子域网格生成算法中子域标准定义过严和剖分规则过于繁琐的缺点,形成一个新的全四边形单元网格生成算法。随后并行了区域分解过程,并引入子域图,结合静态图划分策略,得到该算法的并行版本。所得到的并行网格生成器可以同步完成并行网格生成及划分,从而加速整个并行模拟过程。 随后,本文系统地研究了序列化Delaunay网格生成。基于Bowyer-Waston插点内核,实现了高质量的二维及三维Delaunay网格生成程序,并基于Delaunay网格生成算法的最新研究成果,就程序的时空效率、健壮性、数据结构设计及重要实现细节展开讨论。 边界恢复是Delaunay网格生成的主要困难之一,基于在约束处直接加点恢复的思路,本文完整地讨论了边界恢复中可能遇到的各种情形,给出了相应的解决方案,最终获得一个收敛的一致边界恢复算法。通过引入一系列基本概念、数据结构及基本操作,简化了一致边界恢复算法的实现过程。 为保证交界面网格的一致性,基于区域分解的并行Delaunay网格生成算法要求序列化Delaunay网格生成器具备约束边界恢复能力。最近,George、Du和Wang基于几乎同样的思路提出了相应的间接约束边界恢复算法,即先进行一致边界恢复,随后通过分解约束上辅助点的方式实施约束边界恢复。本文引入新的几何操作,简化了上述算法的具体实现,结合已实现的一致边界恢复算法,最终获得了一个新的约束边界恢复算法实现。 对于二维问题,本文引入上述四边形单元网格生成研究中获得的并行区域分解算法,利用动态子域图划分策略,构建了一个通用的并行平面网格生成框架。集成二维序列化Delaunay网格生成器后,获得二维并行网格生成器PDMG-2D,它成功地在中等规模的并行平台上生成数亿高质量的三角形单元,且所获得的分布式网格的划分质量较高。 对于三维问题,基于平面分割的方式,本文获得了一个递归区域分解框架。特别地,针对区域分解过程中出现的各种错误情形,本文讨论了相应的错误检测更多还原

【Abstract】 Mesh generation is the pre-process and one of main performance bottlenecks of numerical simulations. With ever larger problems arising in such areas as Computational Fluid Dynamics (CFD), Computational Electro-Magnetics (CEM), close attention has been paid to parallel mesh generation to overcome the bottlenecks of serial mesh generation in terms of time and memory consuming in the international research community since early 1990s. However, few researchers in China have concentrated on this field so far. For the requirement of more and more large-scale simulations emerging in the industry and research community, in this thesis we will study some practical problems of unstructured mesh generation and its parallelization in depth.Firstly, a robust and efficient pattern module scheme for fully quadrilateral elements is constructed for meshing triangular or quadrilateral domains. The scheme is then applied into the sub-domain mesh generation stage of domain decomposition methods. It overcomes two drawbacks associated with current sub-domain meshing algorithms, i.e. the sub-domain definition being too stringent and the generation rule being too complex. Consequently, a new quadrilateral mesh generation method for arbitrary planar domains is proposed. Furthermore, a parallel version of this method is proposed by parallelizing the domain decomposition process and introducing the SubDomain Graph (SDG). It could generate distributed meshes with high partitioning quality simultaneously with parallel mesh generation, therefore to accelerate the whole process of parallel simulations greatly.Secondly, serial Delaunay mesh generation algorithms are discussed, and high-quality 2D and 3D serial Delaunay mesh generators using the Bowyer-Watson point insertion kernel are coded, named DTIso2D and DTIso3D, respectively. Issues of time and memory complexities, robustness, data structures and important implementation details are explored in this thesis.Boundary recovery is one of main problems in applying Delaunay algorithms into mesh generation. All constraint missing cases are illustrated, and the corresponding recovery techniques are given as well based on the idea of adding Steiner points directly in the missing constraints. Besides, a series of concepts, data structures and operators are introduced to alleviate the coding work of the conformal boundary recovery algorithm.A constrained rather than conformal boundary recovery procedure is required for the coordination of shared data in the artificial interfaces of partitioned meshes. George and Du et al independently present two new indirect constrained boundary recovery algorithms with nearly same idea, which both strive to resolve the robustness problem of George’s early classic algorithm. Here indirect algorithms mean that a conformal boundary recovery procedure is prerequisite. We simplify some concepts of the above algorithms and present a new implementation for them.Integrated with the parallel geometry decomposition algorithm obtained from the research of above parallel quadrilateral mesh generation, a general parallel planar mesh generation framework is constructed, where a dynamic SDG partitioning module is involved. A 2D parallel Delaunay mesh generator, named PDMG-2D, is developed by combining the framework with DTIso2D, which could generate more than hundreds of millions of elements in the parallel computers with medium size resources. Moreover, considerably good partitioning quality could be achieved for the resulting distributed meshes.For 3D problems, the computational domain is decomposed into many sub-domains recursively by intersecting a plane with the domain. Robust problems arising from complex geometry computations involved in the domain decomposition procedure are investigated. A roll-back scheme of moving the separation plane is utilized to overcome unrecoverable errors in domain decomposition. DTIso3D is linked together with the recursive domain decomposition framework to form the 3D parallel Delaunay mesh generator, named PDMG-3D, which could generate partitioned meshes with more than one hundred millions of elements in the parallel computers with medium size resources.The design of data structures is important in practice for parallel mesh generators to save memory usages, to accelerate algorithms, and to simplify the mergence of sub-meshes or distributed meshes on various sub-domains or processors. We devise a three-level data structure to help fulfill such goals conveniently. It also enables the resulting mesh to be smoothed or optimized globally or in a processor level instead of in a sub-domain level.更多还原