Scalable Multilevel Algorithms in Computational Sciences

偏微分方程（PDE）求解器是大部分科学计算的支柱。特别是，它们是计算流体动力学（CFD）的基础，液体和气体流动的建模。该项目研究新的，有效的方法来解决偏微分方程，并在现代高性能并行计算机上实现这些方法。这些求解器是有用的领域以外，他们原来的CFD家-特别是令人惊讶的应用程序，以不同的领域，如图像恢复和超大规模集成电路布局也将被研究。技术上，这个项目将研究高效的代数多尺度算法的椭圆和非椭圆PDE和CFD问题的任意非结构化网格，适用于分布式和共享内存并行计算架构。此外，本论文亦将研究如何将这些演算法延伸至其他大规模非偏微分方程问题，包括影像复原及超大型积体电路布局问题。这些多尺度算法的三个方面将在这项工作中强调：（1）所产生的问题，使这些算法更代数（便于使用），包括各向异性的鲁棒性，跳跃和振荡系数，均匀化等（2）这些算法的扩展，从正常的椭圆设置非椭圆和更一般的非偏微分方程，基于图形的设置。(3)在现代高性能计算机体系结构上的性能，特别关注通信和高速缓存延迟。特别注意将放在适当的算法，解决离散化矩阵所产生的各种大规模的科学计算问题，如计算流体动力学的平流为主的问题，超大规模集成电路布局的图像处理。这些实际问题的非椭圆行为使得已知的多层次理论不足，并有助于激发平衡的努力，包括算法开发，理论分析和实际应用。

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.