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 processing

speed and capacity, closely described by Moore's law, in the last four

decades has been outpaced by the explosive amount of data that are used

to 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 the

celebrated fast multipole method (FMM) have provided a computational

tool for narrowing the gap. At the same time, there is a great need

and challenge to develop better computation techniques and utilize the

present 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 the

key simulation steps, from analytic re-formulation of system models with

complex geometries to combinatorial optimization in mapping numerical

algorithms to computing architectures. Many traditional models are

formulated in terms of linear or nonlinear partial differential

equations (PDEs) with boundary conditions on complex geometries. By

the work of other researchers and principal investigators,

integral equation (IE) formulations have lead to better numerical

algorithms in both efficiency and stability, and more importantly

enabled certain important large-scale simulations. It is proposed first

to study the reformulation of traditional PDE models into IE models, as

a direct and analytical approach to innovative algorithm design. Next,

preconditioning techniques will be studied as an indirect and

stabilization approach. Furthermore, Graph-theoretic methods will be

applied to optimize the FMM-based algorithms on various modern

computer architectures, especially, parallel architectures. These key

components 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 through

timely dissemination with demonstration of case studies. Three

application 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 microvascular

networks. The proposed work involves interdisciplinary research

collaboration and cultivation of young and new researchers with

multi-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.