Scalable Multilevel Algorithms in Computational Sciences

计算科学中的可扩展多级算法

• 批准号: 0072112
• 负责人: Tony Chan
• 金额: $ 44.61万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-07-01 至 2004-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0072112&HistoricalAwards=false
• 关键词: Scalable; Multilevel; Algorithms; Computational; Sciences

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.

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