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

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

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.