The aim of this research project is to design fast and accurate numerical algorithms for the solution of large classes of mathematical equations that arise in engineering and science. In particular, the main concerns are the solution of integro-differential equations on complex domains and of signal and image processing problems. The approach is based on formulating the estimate of the solution of the equation at a point as the value of the smoothest solution (on average) at that point based on the given data. The resulting discrete equations can be shown to have specially structured matrices, which can be exploited to create fast solvers for these equations. The resulting methods have two main computational advantages. First, they can be designed to avoid gridding or triangulation of the complex domain. Second, these methods exhibit local convergence; that is, the rate at which the approximant converges to the solution at a point depends only on the local smoothness of the solution. These advantages enable the method to tackle equations with complicated singularity structures with relative ease.
Let Hs denote a Sobolev Hilbert space whose elements have s > 1 fractional derivatives. Suppose an unknown function f in Hs satisfies the equation L(F) = g, where L is a linear operator and g is a known function. Let Ln denote n linear functionals on Hr. Let q denote a linear functional on Hs. Then the best minmax estimate for q(f) can be computed from the minimum Sobolev norm function p in Hs that satisfies the constraints Ln(L(p)) = Ln(g). This p can be computed very rapidly since the optimal p is given by a nice set of equations that has Fast Multipole Method (FMM) structure when written in the proper representation. Also, it is possible to work with Lp Sobolev spaces with p = 1. In these cases the optimization problem is more complicated and can be reduced to linear programming problems, for which fast solvers are being developed that exploit the underlying FMM structure of the constraint matrix. The theoretical work consists of studying the convergence of the solution as n gets bigger, and also in proving the FMM structure of the resulting discrete equations. The algorithmic work consists of designing fast algorithms for constructing the FMM representation and then designing fast algorithms for the direct (non-iterative) solution of these equations. The application work consists of applying these ideas to image segmentation and multi-rate signal processing. Also, mesh free, locally convergent schemes are being developed for the solution of integral equations and elliptic partial differential equations on complex domains in two dimensions.
Our society is highly dependent on the ability of engineers to make ever more sophisticated and critical systems, whether they be large body passenger aircraft, or computer chips with billions of components, or life-saving body-imaging machinery. All of these systems are crucially dependent on our ability to simulate them on computers. This not only saves money as it shortens the design cycle, but more importantly, it saves lives, as it allows thorough simulated testing of the design. Unfortunately the mathematics that dictates the behavior of these engineered systems is highly complicated and the computer solution of the mathematics consumes too much computer time and memory to be truly accurate and feasible at the same time. The goal of our research was to greatly speed up the computer solution of certain classes of mathematical problems that are common in many engineering simulations. Mathematicians refer to these problems as elliptic partial differential equations (PDEs). Our line of attack began with a serendipitous discovery of a solution to a long-standing open problem, that is referred to as the Runge phenomenon. This problem is concerned with the fact that the standard recovery of a continuous signal from its samples can fail or be very slow and inefficient. Since this is the very basis of computer simulation, it places a big obstacle in the design of efficient simulation algorithms. We found a very simple and efficient way around this problem. We called our solution the Minimum Sobolev Norm (MSN) approach, and noticed that it would likely lead to much faster solutions of elliptic PDEs as well. In the project we applied our ideas to two standard methods for solving elliptic PDEs. One is called the finite-difference (FD) method, and the other is called the dis-continuous Galerkin finite-element (DGEFM) method. With regard to the FD method, our ideas lead to a major breakthrough, and we constructed for the first-time truly general FD schemes that are extremely efficient. However, there are certain intrinsic limitations to the FD method, and for certain classes of problems (for example, fourth order elliptic PDEs that arise in elasticity), the FD method is not competitive. A very popular alternative is the DGFEM method. We applied our ideas and this time we hit the jack-pot. We were able to devise a very simple and powerful scheme that we proved is capable of handling any type of PDE. The code has already been used to solve problems from elasticity theory (the afore mentioned fourth-order PDEs) that can be used to model highly complex materials. We have made significant breakthroughs in the solution of elliptic PDEs that are key in the engineering design of critical systems. We believe that these ideas have not been exhausted yet, and we expect even more breakthroughs to follow. We also made a significant breakthrough in the design of some fast algorithms that play a critical role in the computer solution of many engineering problems. This class of techniques is referred to as the Fast Multi-pole Method (FMM), and was invented in the late 80's, and has played a significant role in problems ranging from the large-scale simulation of galaxies to the computational discovery of molecular structures to the design of microwave antennas. Within this class of problems there are significant open problems whose resolution would have great practical significance. One of these is technically referred to as the problem of the super-fast multiplication of two FMM matrices. We solved this long-standing open problem and we anticipate that this has the potential for great practical impact.
