Parallel Multilevel PDE Solvers on Unstructured Grids

本项目将研究适用于分布式和共享内存并行计算体系结构的任意非结构网格上椭圆和非椭圆问题的高效多重网格(MG)和区域分解(DD)算法。本文将重点研究DD和MG的三个方面：(1)各种DD和MG算法在并行计算机上的性能，特别关注通信延迟和缓存延迟。(2)利用用户提供的可选信息，设计了椭圆型和平流型占优问题的优化DD和MG“灰盒”库。(3)适用于平流占优问题的DD和MG算法的理论分析和实用设计。将特别强调DD和MG算法，用于解决各种大规模科学计算问题所产生的离散化矩阵，例如用于对流控制问题的计算流体力学(CFD)、图像处理、光刻以及微芯片性能和制造的建模。这些实际问题的非椭圆行为使得已知的多重网格和分解理论不够充分，并有助于推动由算法开发、理论分析和实际应用组成的平衡努力。

This project will investigate efficient multigrid (MG) and domain decomposition (DD) algorithms for elliptic and non-elliptic problems on arbitrary unstructured meshes, which are suitable for distributed and shared memory parallel computing architectures. Three aspects of DD and MG will be emphasized in this work: (1) Performance of various DD and MG algorithms on parallel computers with particular attention paid to communication and cache memory latency. (2) Design of optimized DD and MG "gray box" libraries for elliptic and advection dominated problems, which exploit optional information supplied by the user. (3) Theoretical analysis and practical design of DD and MG algorithm appropriate for advection dominated problems. Particular emphasis will be placed on DD and MG algorithms for solving the discretization matrices arising from a variety of large scale scientific computing problems, such as computational fluid dynamics (CFD) for advection dominated problems, image processing, photolithography, and the modeling of microchip performance and fabrication. The non-elliptic behavior of these practical problems renders the known multigrid and decomposition theory inadequate and serves to motivate a balanced effort consisting of algorithmic development, theoretical analysis, and practical application.