Collaborative Research: Minimum Sobolov Norm Methods

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Collaborative Research: Minimum Sobolev Norm Methods 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.