AF: Medium: Collaborative Research: Integral-Equation-Based Fast Algorithms and Graph-Theoretic Methods for Large-Scale Simulations

AF：中：协作研究：用于大规模仿真的基于积分方程的快速算法和图论方法

• 批准号: 0905164
• 负责人: Xiaobai Sun
• 金额: $ 40万
• 依托单位: Duke University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-07-15 至 2015-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0905164&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Integral

The phenomenal advance in computer technology in terms of processingspeed and capacity, closely described by Moore's law, in the last fourdecades has been outpaced by the explosive amount of data that are usedto describe more realistic models in scientific computing. For instance,the number of unknowns in a linear system has grown from hundreds in the past to tens of millions nowadays. Fast algorithms such as thecelebrated fast multipole method (FMM) have provided a computationaltool for narrowing the gap. At the same time, there is a great needand challenge to develop better computation techniques and utilize thepresent and emerging computers, with the gain in speed up to a couple of orders of magnitude. The goal of the proposed research is to advance computational theories and techniques, in order to meet the demand and challenge for large scale simulations of complex systems in scientific, medical and engineering studies.The research team proposed to investigate, innovate and integrate thekey simulation steps, from analytic re-formulation of system models withcomplex geometries to combinatorial optimization in mapping numericalalgorithms to computing architectures. Many traditional models areformulated in terms of linear or nonlinear partial differentialequations (PDEs) with boundary conditions on complex geometries. Bythe work of other researchers and principal investigators,integral equation (IE) formulations have lead to better numericalalgorithms in both efficiency and stability, and more importantlyenabled certain important large-scale simulations. It is proposed firstto study the reformulation of traditional PDE models into IE models, asa direct and analytical approach to innovative algorithm design. Next,preconditioning techniques will be studied as an indirect andstabilization approach. Furthermore, Graph-theoretic methods will beapplied to optimize the FMM-based algorithms on various moderncomputer architectures, especially, parallel architectures. These keycomponents will be studied in conjunction, not in isolation.The intellectual merits of the proposed work are three-fold. It sheds lights on (1) the model reformulation into IEs of the second kind as a fundamental analytic-algorithmic approach to accelerating and stabilizing numerical computation, (2) the connection between reformulation and preconditioning, and (3) on the mutual dependence of numerical algorithms and computer architectures. The proposed work will have broader impacts on various applications throughtimely dissemination with demonstration of case studies. Threeapplication areas of specific concern are electrostatics calculation in molecular dynamics simulations, computational fluid dynamics, and the study of oxygen delivery in tissues and tumors via microvascularnetworks. The proposed work involves interdisciplinary researchcollaboration and cultivation of young and new researchers withmulti-disciplinary backgrounds. Finally, the findings and algorithms will be embodied in open source high performance software to facilitate research computing by and large and to be used in classrooms.

在过去的40年里，计算机技术在处理速度和容量方面取得了惊人的进步，这与摩尔定律密切相关，但却被用于描述科学计算中更现实的模型的爆炸式数据量所超越。例如，线性系统中的未知数数量已经从过去的数百个增加到现在的数千万个。快速算法，如著名的快速多极法（FMM），为缩小这一差距提供了一个计算工具。与此同时，发展更好的计算技术和利用现有的和新兴的计算机是一个巨大的需求和挑战，在速度上的增益高达几个数量级。提出的研究目标是推进计算理论和技术，以满足科学，医学和工程研究中复杂系统的大规模模拟的需求和挑战。研究小组提出研究、创新和整合关键的仿真步骤，从具有复杂几何形状的系统模型的解析重新表述到将数值算法映射到计算架构的组合优化。许多传统的模型都是在复杂几何上用带有边界条件的线性或非线性偏微分方程（PDEs）来表述的。通过其他研究人员和主要研究人员的工作，积分方程（IE）公式在效率和稳定性方面都带来了更好的数值算法，更重要的是使某些重要的大规模模拟成为可能。首先研究将传统的PDE模型重构为IE模型，为创新算法设计提供直接的分析方法。接下来，预处理技术将作为一种间接和稳定的方法进行研究。此外，图论方法将应用于优化各种现代计算机体系结构，特别是并行体系结构上基于fmm的算法。这些关键组成部分将一起研究，而不是单独研究。这项提议的工作在智力上有三方面的价值。它阐明了(1)作为加速和稳定数值计算的基本分析算法方法的第二类模型重构为IEs，(2)重构与预处理之间的联系，以及(3)数值算法与计算机体系结构的相互依赖。建议的工作将通过及时传播并示范案例研究，对各种应用产生更广泛的影响。三个特别关注的应用领域是分子动力学模拟中的静电计算，计算流体动力学，以及通过微血管网络研究组织和肿瘤中的氧气输送。建议的工作涉及跨学科研究合作和培养具有多学科背景的年轻和新的研究人员。最后，研究结果和算法将体现在开源高性能软件中，以促进研究计算，并在课堂上使用。