Scalable Multilevel Algorithms in Computational Sciences

偏微分方程组(PDE)的解算器是许多科学计算的支柱。特别是，它们是计算流体动力学(CFD)的基础，CFD是液体和气体流动的建模。该项目研究了求解偏微分方程组的新的、有效的方法，并在现代高性能并行计算机上实现了这些方法。这些求解器在不同的领域都是有用的，特别是在图像恢复和VLSI布局等不同领域的令人惊讶的应用。本项目将在技术上研究适用于分布式和共享内存并行计算体系结构的任意非结构网格上椭圆和非椭圆偏微分方程组和CFD问题的高效代数多尺度算法。此外，它还将研究如何将这些算法扩展到其他大规模非偏微分方程问题，包括图像恢复和VLSI布局问题。这项工作将强调这些多尺度算法的三个方面：(1)使这些算法变得更代数(为了易于使用)所产生的问题，包括对各向异性的健壮性、系数的跳跃和振荡、均匀化等。(2)将这些算法从正常的椭圆设置扩展到非椭圆以及更一般的非偏微分方程、基于图的设置。(3)在现代高性能计算机体系结构上的性能，特别关注通信和高速缓冲存储器延迟。将特别关注适合于求解各种大规模科学计算问题的离散化矩阵的算法，例如用于对流占优问题的CFD、VLSI布局和图像处理。这些实际问题的非椭圆行为使已知的多水平理论不够充分，并有助于推动由算法开发、理论分析和实际应用组成的平衡努力。

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.