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

点击翻译按钮获取中文摘要

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.