HAMMERSLEY_ADVANCED
The Hammersley Quasi Monte Carlo (QMC) Sequence


HAMMERSLEY_ADVANCED is a C++ library which computes the Hammersley Quasi Monte Carlo (QMC) sequence.

HAMMERSLEY_ADVANCED includes several subroutines to make it easy to manipulate this computation, to compute the next N entries, to compute a particular entry, to restart the sequence at a particular point, or to compute NDIM-dimensional versions of the sequence.

For the most straightforward use, try either

Both of these routines require explicit input values for all parameters.

For more convenience, there are two related routines with almost no input arguments:

These routines allow the user to either rely on the default values of parameters, or to change a few of them by calling appropriate routines.

Routines in this library select elements of a "leaped" subsequence of the Hammersley sequence. The subsequence elements are indexed by a quantity called STEP, which starts at 0. The STEP-th subsequence element is simply the Hammersley sequence element with index

        SEED(1:NDIM) + STEP * LEAP(1:NDIM).
      

The arguments that the user may set include:

In the standard NDIM-dimensional Hammersley sequence, it is assumed that N, the number of values to be generated, is known beforehand. The first dimension of entries in the sequence will have the form J/N for J from 1 to N. The remaining dimensions are computed using the 1-dimensional van der Corput sequence, using successive primes as bases.

In a generalized Hammersley sequence, each coordinate is allowed to be a fractional or van der Corput sequence. For any fractional sequence, the denominator is arbitrary. However, it is extremely desirable that the values in all coordinates stay between 0 and 1. This happens automatically for any van der Corput sequence, but for fractional sequences, this criterion is enforced using an appropriate modulus function. The consequence is that if you specify a small "base" for a fractional sequence, your sequence will soon wrap around and you will get repeated values.

If you drop the first dimension of the standard NDIM-dimensional Hammersley sequence, you get the standard Halton sequence of dimension NDIM-1.

The standard Hammersley sequence has slightly better dispersion properties than the standard Halton sequence. However, it suffers from the problem that you must know, beforehand, the number of points you are going to generate. Thus, if you have computed a Hammersley sequence of length N = 100, and you want to compute a Hammersley sequence of length 200, you must discard your current values and start over. By contrast, you can compute 100 points of a Halton sequence, and then 100 more, and this will be the same as computing the first 200 points of the Halton sequence in one calculation.

In low dimensions, the multidimensional Hammersley sequence quickly "fills up" the space in a well-distributed pattern. However, for higher dimensions (such as NDIM = 40) for instance, the initial elements of the Hammersley sequence can be very poorly distributed; it is only when N, the number of sequence elements, is large enough relative to the spatial dimension, that the sequence is properly behaved. Remedies for this problem were suggested by Kocis and Whiten.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

HAMMERSLEY_ADVANCED is available in a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

BOX_BEHNKEN, a C++ library which computes a Box-Behnken design, that is, a set of arguments to sample the behavior of a function of multiple parameters;

CVT, a C++ library which computes points in a Centroidal Voronoi Tessellation.

FAURE, a C++ library which computes Faure sequences.

HALTON, a C++ library which computes Halton sequences.

HAMMERSLEY_DATASET, a C++ program which computes Hammersley datasets.

HEX_GRID, a C++ library which computes sets of points in a 2D hexagonal grid.

IHS, a C++ library which computes improved Latin Hypercube datasets.

LATIN_CENTER, a C++ library which computes Latin square data choosing the center value.

LATIN_EDGE, a C++ library which computes Latin square data choosing the edge value.

LATIN_RANDOM, a C++ library which computes Latin square data choosing a random value in the square.

NIEDERREITER2, a C++ library which computes Niederreiter sequences with base 2.

SOBOL, a C++ library which computes Sobol sequences.

UNIFORM, a C++ library which computes uniform random values.

VAN_DER_CORPUT, a C++ library which computes van der Corput sequences.

Reference:

  1. John Hammersley,
    Monte Carlo methods for solving multivariable problems,
    Proceedings of the New York Academy of Science,
    Volume 86, 1960, pages 844-874.
  2. Ladislav Kocis, William Whiten,
    Computational Investigations of Low-Discrepancy Sequences,
    ACM Transactions on Mathematical Software,
    Volume 23, Number 2, 1997, pages 266-294.

Source Code:

Examples and Tests:

List of Routines:

You can go up one level to the C++ source codes.


Last revised on 20 October 2006.