HALTON_ADVANCED
The Halton Quasi Monte Carlo (QMC) Sequence


HALTON_ADVANCED is a FORTRAN90 library which computes elements of a Halton Quasi Monte Carlo (QMC) sequence.

HALTON_ADVANCED includes routines 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.

The NDIM-dimensional Halton sequence is really NDIM separate sequences, each generated by a particular base.

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

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

The arguments that the user may set include:

The NDIM-dimensional Halton sequence is derived from the 1-dimensional van der Corput sequence. Each dimension typically uses a different prime number as the base of the calculation.

The NDIM-dimensional Halton sequence is related to the NDIM+1 dimensional Hammersley sequence of length NMAX. An NDIM+1 dimensional Hammersley sequence of length NMAX becomes an NDIM-dimensional Halton sequence by deleting the first dimension. An NDIM dimensional Halton sequence of NMAX points becomes an NDIM+1 dimensional Hammersley sequence of length NMAX by prefixing a first coordinate, and setting the value of this first coordinate to I/NMAX for the I-th entry of the sequence.

While the Hammersley sequence has better dispersion properties in technical measures such as the discrepancy, 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 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 Halton 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 Halton 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.

As an example of the use of Halton sequences, we also use them to compute "random" points on or in the unit circle in 2D, and the unit sphere in 3D.

Licensing:

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

Languages:

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

Related Data and Programs:

CVT, a FORTRAN90 library which computes elements of a Centroidal Voronoi Tessellation.

FAURE, a FORTRAN90 library which computes elements of a Faure quasirandom sequence.

HALTON, a FORTRAN90 library which computes elements of a Halton Quasi Monte Carlo (QMC) sequence, using a simple interface.

HALTON_DATASET, a FORTRAN90 program which creates a Halton sequence and writes it to a file.

HAMMERSLEY, a FORTRAN90 library which computes elements of a Hammersley quasirandom sequence.

HEX_GRID, a FORTRAN90 library which computes elements of a hexagonal grid dataset.

HEX_GRID_ANGLE, a FORTRAN90 library which computes elements of an angled hexagonal grid dataset.

IEEE_UNIFORM_SAMPLE, a FORTRAN90 library which tries to uniformly sample the discrete set of values that represent the legal IEEE real numbers;

IHS, a FORTRAN90 library which computes elements of an improved distributed Latin hypercube dataset.

LATIN_CENTER, a FORTRAN90 library which computes elements of a Latin Hypercube dataset, choosing center points.

LATIN_EDGE, a FORTRAN90 library which computes elements of a Latin Hypercube dataset, choosing edge points.

LATIN_RANDOM, a FORTRAN90 library which computes elements of a Latin Hypercube dataset, choosing points at random.

LATTICE_RULE, a FORTRAN90 library which approximates multidimensional integrals using lattice rules.

LCVT, a FORTRAN90 library which computes a latinized Centroidal Voronoi Tessellation.

NIEDERREITER2, a FORTRAN90 library which computes elements of a Niederreiter sequence using base 2.

NORMAL, a FORTRAN90 library which computes elements of a sequence of pseudorandom normally distributed values.

SOBOL, a FORTRAN90 library which computes elements of a Sobol quasirandom sequence.

TOMS647, a FORTRAN90 library which is a version of ACM TOMS algorithm 647, for evaluating Faure, Halton and Sobol quasirandom sequences.

UNIFORM, a FORTRAN90 library which computes elements of a uniform pseudorandom sequence.

VAN_DER_CORPUT, a FORTRAN90 library which computes elements of a 1D van der Corput sequence.

Reference:

  1. John Halton,
    On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals,
    Numerische Mathematik,
    Volume 2, 1960, pages 84-90.
  2. John Halton, GB Smith,
    Algorithm 247: Radical-Inverse Quasi-Random Point Sequence,
    Communications of the ACM,
    Volume 7, 1964, pages 701-702.
  3. 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 FORTRAN90 source codes.


Last revised on 27 December 2010.