Principal Investigator Malcolm Sambridge Project r58

Research School of Earth Sciences Machine VP

Applications of Computational Geometry to Large Scale Geophysical Inverse Problems

The project ran for the first few months of 1994 and concentrated on development work. The main focus of the project over the first three months has been on theoretical development of the algorithms to be considered. Therefore the main computational work has not yet really begun.

What are the basic questions addressed?

The purpose of the project is to use the concept of multi-dimensional Voronoi cells in the analysis of non-linear inverse problems. The Voronoi cell is a simple structure which allows an interpolation through a large number of irregularly spaced points in a parameter space of arbitrary dimension. At present, methods for calculating Voronoi cells are prohibitively expensive. Part of this project is aimed at finding alternative algorithms for their calculation in intermediate to high dimensional spaces. This aspect of the work is quite abstract in the sense that any useful methods that arise will be applicable to any physical problem making use of Voronoi cells. The second part of the project is putting this to use for geophysical problems.

What are the results to date and the future of the work?

Results are very preliminary at present but three main directions have been outlined which appear promising. Two of these are aimed at the calculation of multi-dimensional Voronoi diagrams and the third is in the application to non-linear inverse problems. Two computational techniques are currently under investigation.

What computational techniques are used and why is a supercomputer required?

The first is a statistical approach based on estimating the `natural neighbour' list. This is clearly the only type of list that defines the Voronoi diagram compactly in large dimension and therefore the only one that can be used. (All others would be prohibitive on memory requirements). The approach involves calculating the first and second nearest neighbour of randomly generated points in space and using this information to find an entry in the natural neighbour list. As this procedure is repeated many times information will be built up statistically on the non-zero entries in a natural neighbour list. The second method is an exact approach based on building up the same natural neighbour list incrementally. The method involves resolving a quadratic optimisation problem for every new point added in the parameter list. This is an enormous computational task. It is not clear whether this approach will prove computationally viable, although efficient methods are available for strictly convex quadratic programming problems. The third area of study is in application to inverse problems. This area relies on the outcome of the first two stages and is the subject for further work. At present the computation on the project has been in investigating various aspects of the two methods described above. A full code is the subject of ongoing work.