NA - Neighbourhood Algorithm
The neighbourhood algorithm is a two-stage numerical procedure for non-linear geophysical inverse problems. It also has applications as a direct search technique for global optimization.
Overview
The neighbourhood algorithm is a two-stage numerical procedure for non-linear geophysical inverse problems. It also has applications as a direct search technique for global optimization.
The first, search stage consists of a direct search method in a multidimensional parameter space. The objective is to find points (models) with acceptable (high or low) values of a user supplied objective function. It makes use of geometrical constructs known as Voronoi cells (shown above) in the search and appraisal stages. This algorithm is described in the papers below and implemented in the author's computer package `NA-sampler'. See the NA-sampler user guide for more details.
Features:
It is a direct search (derivative free) algorithm used to sample a parameter space. Can be used for global optimization but optimal models are not guaranteed ! (cf. genetic algorithms and simulated annealing etc.).
It requires the user to supply an objective function. Only the rank of models with respect to this objective function is used to drive the search.
It uses two parameters which control the behaviour of the search process.
The second, appraisal stage consists of an algorithm for using the entire ensemble of models produced in stage I, and deriving information from them in the form of Bayesian measures of resolution, covariance and marginal PDF's etc. This algorithm is described in the papers below and implemented in the author's computer package `NA-Bayes'. See the NA-Bayes user guide for more details.
Features:
It can be applied to any ensemble of input models. It does not have to be used with the search algorithm above.
It requires a posterior probability density function to be supplied and uses a Bayesian approach.
Bayesian measures can be produced for any variable or function of variables.
A plot program (`NA-plot') is supplied with the code to display the various Bayesian integrals estimated by NA-Bayes.
Contributor: Malcolm Sambridge, RSES Australian National University.
e:
Malcolm.Sambridge@anu.edu.au
Download
The computer package NA-sampler that implements the NA algorithm for the search problem, can be obtained here. More details on the direct search code (i.e. what it does, how to use it etc.) are available by looking at the NA-sampler user guide . A separate code implementing the appraisal stage NA-Bayes, is also available. See the NA-Bayes user guide for more details.
Enquires should be directed to the author. You will need to register with iEarth prior to download.
Note that, conditions are attached to use of the code and these can be found in the user guide.
When you register please include your location (latitude and longitude), or send them directly to Malcolm.Sambridge@anu.edu.au, so that you can be added to the world map of NA downloads below.
Parallelization
In April 2002 the NA sampler package was updated to include MPI (message passing interface) calls. This allows the forward modelling to be performed on different processors in parallel, e.g. on a Beowulf cluster of linux PCs.
The MPI option is activated by a switch during compilation and is transparent to the user. Tests have shown with that with MPI the forward modelling models in NA can be efficiently carried out on separate processors since minimal communication is required. With MPI and a unix cluster it should be possible to apply NA to problems where the cost of forward modelling is much higher. This is a current direction of research at RSES.
Papers
The two original papers describing the neighbourhood algorithm are:
Geophysical Inversion with a Neighbourhood Algorithm -I. Searching a parameter space, Sambridge, M., Geophys. J. Int., 138, 479-494, 1999. doi:10.1046/j.1365-246X.1999.00876.x
Geophysical Inversion with a Neighbourhood Algorithm -II. Appraising the ensemble, Sambridge, M., Geophys. J. Int., 138, 727-746, 1999. doi:10.1046/j.1365-246x.1999.00900.x
Manuals
NA-sampler user guide - the author's neighbourhood algorithm direct search package.
NA-Bayes user guide - the author's Bayesian NA appraisal algorithm package.
splot - graphics program for display of multi-dimensional ensembles.
naplot - graphics program for displaying Bayesian estimators.
summary.pdf - A short summary of NA-sampler written for the IASPEI handbook.
Other sites:
NN homepage - information on applications of Voronoi cells and natural neighbours at RSES.
RUM homepage - Voronoi cells in seismic tomography and building Earth models.