Over the last several decades, the development of powerful computers and fast algorithms has dramatically increased our capability to computationally model a broad range of phenomena in science and engineering. Our newfound ability to design complex systems (cars, new materials, city infrastructures, etc.) via computer simulations rather than physical experiments has in many fields led to both cost savings and profound improvements in performance. Intense efforts are currently being made to extend these advances to biochemistry, physiology, and several other areas in the biological and medical sciences. The goal of the proposed research is to develop faster and more accurate algorithms for computing approximate solutions to a class of mathematical equations called "partial differential equations" (PDEs) that lie at the core of models of physical phenomena such as heat transport, deformation of elastic bodies, scattering of electro-magnetic waves, and many others. The task of solving such equations is frequently the most time-consuming part of computational simulations, and is the part that determines which problems can be modeled computationally, and which cannot. Technically speaking, most existing numerical algorithms for solving large PDE problems use "iterative methods," which construct a sequence of approximate solutions that gradually approach the exact solution. The proposed research seeks to develop "direct methods" for solving many PDEs. Loosely speaking, a direct method computes the unknown data from the given data in one shot. Direct methods are generally preferred to iterative ones since they are more robust, are more suitable for incorporation in general-purpose software, and work for important problems that cannot be solved with known iterative methods. The reason that they are typically not used today is that they are often prohibitively expensive. However, recent results by the PI and other researchers indicate that it is possible to construct direct methods that are competitive in terms of speed with the very fastest known iterative solvers. In fact, in several important applications, the direct methods appear to be one or two orders of magnitude faster than existing iterative methods. In addition to constructing faster algorithms, a core goal of the proposed research is to demonstrate the capabilities of the new methods by applying them to a number of technologically important problems that are not amenable to existing techniques. These problems include scattering problems at frequencies close to a resonance frequency of the scatterer, modeling of crack propagation in composite materials, and the modeling of large bio-molecules in ionic solutions. An integral part of the proposed work is the development of new educational material on computational techniques. Specific goals include: (1) The development of a textbook on so called "Fast Multipole Methods." (2) The development of a new graduate-level class on fast algorithms for solving PDEs. (3) The updating of the standard curriculum of undergraduate classes in numerical analysis to reflect new modes of thinking about numerical algorithms (specifically the development of methods that are not "convergent" in the classical sense, but that can solve specified tasks to any preset accuracy). This work is to be undertaken in close collaboration with Leslie Greengard at NYU and Vladimir Rokhlin at Yale University.
The objective of the project was to develop highly accurate and computationally efficient techniques for solving a class of mathematical equations that is central to many areas of science and engineering. These equations (so called "elliptic partial differential equations") model electrostatics, gravitation, thermostatics, deformations of solid bodies, acoustics, and much more. Existing techniques for solving such problems are by and large based on so called "iterative solvers" which proceed incrementally, building a slightly more accurate approximation to the solution at each step. In contrast, this project was aimed at developing so called "direct solvers" which in a single go construct an approximation to the solution. Or, even better, they can be used to construct an approximation to the actual solution-operator. The project succeeded in developing new solvers for a broad range of equations set in two and three dimensions. These techniques have received a large amount of attention from the numerical analysis community, as well as from engineers and practitioners. For instance, in June 2014, the PI served as the principal lecturer at a summer school at Dartmouth College that attracted about 50 participants from across the United States as well as from abroad (the UK, Canada, Japan, Saudi Arabia). Moreover, direct solvers have during the last few years become a major area of research at institutions such as NYU, Stanford University, UT-Austin, University of Michigan at Ann Arbor, Purude, LBNL, and many others. Much of the recent work in this area draws heavily on techniques developed under the aegis of the current project. Another outcome of the project with a very substantial impact is a set of new algorithms for rapidly factoring very large matrices. The problem or matrix factorization comes up not only in modeling physical phenomena, but also in data mining, signal processing, computer graphics, and many more. The PI developed a set of algorithms for this task based on randomized sampling that in key metrics outperform earlier techniques based on deterministic methods. In particular, the new algorithms excel on modern computing platforms where limiting communication and power consumption is a primary design objective. The project supported five doctoral students, three of whom have already graduated, with an additional student expected to graduate in Spring 2015. Two of the supported students were female, one of whom (Dr. Adrianna Gillman) has gone on to a tenure-track position at Rice University. A key component of the project was the development of educational material that will help disseminate and popularize the new algorithms. The PI has developed a new course on so called "fast methods" in scientific computation aimed at advanced undergraduate and beginning graduate students. The PI has also taught one spring school and one summer school for graduate students and postdoctoral researchers on the techniques developed. Tutorial style software, lecture slides, and videos of many of the lectures have been made publicly available. Moreover, the PI is currently writing up a set of lecture notes will be published by SIAM (Society for Industrial and Applied Mathematics) with a due date of June 30, 2015.
