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.
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
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: