Scalable Multilevel Algorithms in Computational Sciences

偏微分方程求解器（PDEs）是许多科学计算的支柱。特别是，它们是计算流体动力学（CFD）的基础，即液体和气体流动的建模。本课题研究求解偏微分方程的新方法，并在现代高性能并行计算机上实现这些方法。这些求解器在其原始CFD应用领域之外的其他领域也很有用，特别是在图像恢复和VLSI放置等不同领域的惊人应用。在技术上，本项目将研究适用于分布式和共享内存并行计算架构的椭圆型和非椭圆型PDE和CFD问题的高效代数多尺度算法。此外，它将研究如何将这些算法扩展到其他大规模的非pde问题，包括图像恢复和VLSI放置问题。这些多尺度算法将在本工作中强调三个方面：(1)使这些算法更具代数性（便于使用）所引起的问题，包括对各向异性、系数的跳跃和振荡、均匀化等的鲁棒性(2)将这些算法从正常的椭圆设置扩展到非椭圆和更普遍的非pde、基于图的设置。(3)现代高性能计算机体系结构的性能，特别关注通信和缓存存储器延迟。我们将特别关注适合于求解离散化矩阵的算法，这些离散化矩阵来自于各种大规模的科学计算问题，例如用于平流主导问题的CFD，超大规模集成电路的放置和图像处理。这些实际问题的非椭圆行为使得已知的多层理论不充分，并有助于激发由算法开发，理论分析和实际应用组成的平衡努力。

Solvers for Partial Differential Equations (PDEs) are the backbone of much of scientific computing. In particular, they are the basis of Computational Fluid Dynamics (CFD), the modeling of liquid and gas flows. This project studies new, efficient methods for solving PDEs and implements those methods on modern high-performance parallel computers. These solvers are useful in areas other than their original CFD home - in particular, surprising applications to diverse areas such as image restoration and VLSI placement will be studied as well.Technically, this project will investigate efficient algebraic multiscale algorithms for elliptic and non-elliptic PDE and CFD problems on arbitrary unstructured meshes which are suitable for distributed and shared memory parallel computing architectures. In addition, it will study how these algorithms can be extended to other large scale non-PDE problems, including image restoration and VLSI placement problems. Three aspects of these multiscale algorithms will be emphasized in this work: (1) Issues arising from making these algorithms more algebraic (for ease of use) including robustness to anisotropy, jumps and oscillations in coefficients, homogenization, etc. (2) Extension of these algorithms from their normal elliptic setting to non-elliptic and more generally non-PDE, graph-based settings. (3) Performance on modern high performance computer architectures with particular attention paid to communication and cache memory latency. Particular attention will be placed on algorithms appropriate for solving discretization matrices arising from a variety of large scale scientific computing problems such as CFD for advection dominated problems, VLSI placement an image processing. The non-elliptic behavior of these practical problems renders the known multilevel theory inadequate and serves to motivate a balanced effort consisting of algorithmic development, theoretical analysis, and practical application.