ANU online

 

 

 

 

RSES Home Page


  Overview

  Papers

  Download

  Manuals


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


  Top

  Features

  Papers

  Download

  Enquires


      

-----

NA home page

Voronoi cells about 10 points Voronoi cells about 100 points Voronoi cells about 1000 points

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.

-----

Have a look at the world Map of people who have used the NA codes since 1st Sept. 2004.

.
Locations of visitors to this page

Look at the locations of people who have visited this page since 7th Sept. 2007.

-----

Latest news

  • Nov 2005 - Parallelization of NA-bayes code using MPI. Also code altered to allow option of standard Bayesian sampling with full forward modelling. For many applications this will be much slower than the combination of NA-sampler and NA-bayes (see papers), but code may now be used for multi-dimensional numerical integration of PDFs using a Gibbs sampler. See manual for full details.

  • October 2004 - All parts of the algorithm are now parallelized using the `continuous version' of the NA-sampler algorithm. (Algorithm is also tolerant of hardware faults in a distributed environment - but the MPI standard is not !) For details on the NA continuous version and why it is faster for some applications see forthcoming publication by Rickwood and Sambridge (2006). Check out Publications to see if it is there yet.

  • April 2003 - Construction of the TerraWulf linux cluster begins.
    (See TerraWulf homepage for the latest information.)

  • April 2003 - Paper appears in Science using the NA in inversion for inner core seismic anisotropy.
    (See list of papers for details.)
  • November 2002 - Australian Research Council - LIEF grant obtained to build a 128 node Beowulf cluster at the Research School of Earth Sciences, ANU. This machine will be dedicated to solving large scale inverse problems and optimization using the neighbourhood algorithm with MPI as the primary platform.

  • April 2002 - Message passing interface (MPI) calls added to the multi-dimensional search code NA-sampler to allow it to run in parallel across a multi-processor system, e.g. a Beowulf cluster.

    -----

    Overview

    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.

    NA sampling in a 5-d space. Red = acceptable data fit
(Science, vol 299, p529

    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.

    -----

    Download

    The author's computer package NA-sampler that implements the NA algorithm for the search problem, can be obtained from the author upon request. 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. If requesting the code then please state your name, institution and a short description of the type of problem you are considering applying it to. Note that, conditions are attached to use of the code and these can be found in the user guide.

    -----

    Parallelization

    Beowulf cluster running MPI

    In April 2002 the NA sampler package was updated to include In 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

    A list of all published papers using the NA (that I'm aware of) can be found here. Many can be downloaded.

    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.

    Geophysical Inversion with a Neighbourhood Algorithm -II. Appraising the ensemble,
    Sambridge, M., Geophys. J. Int., 138 ,727-746, 1999.

    Please let me know if you publish a paper using the NA and I'll add it to the list.


    -----

    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.

    Links dealing with other applications of the Neighbourhood Algorithm:

    Other sites:

    -----

    Number of hits on this page

    since September 2002.

    -----

    Last modified: December 2003.

    Enquiries to : malcolm@rses.anu.edu.au