Sobol Sequence - Construction of The Sobol Sequence

Construction of The Sobol Sequence

The algorithm for generating Sobol sequences is clearly explained in Bratley and Fox, Algorithm 659

To generate the j-th component of the points in a Sobol sequence, we need to choose a primitive polynomial of some degree sj over the field GF(2)

P_{j} = x^{s_j} + a_{1,j} x^{s_{j}-1} + a_{2,j} x^{s_{j}-2} + \cdots + a_{s_{j}-1,j} x + 1,

where the coefficients a1,j, a2,j, ..., asj−1,j are either 0 or 1. The error bounds for Sobol sequences given in indicate that we should use primitive polynomials of as low a degree as possible.

A sequence of positive integers {m1,j, m2,j, ...} are defined by the recurrence relation

m_{k,j} = 2a_{1,j}m_{k-1,j} \oplus 2^2a_{2,j}m_{k-2,j} \oplus \cdots \oplus 2^{s_j-1}a_{s_j-1,j} m_{k-s_j+1,j} \oplus 2^{s_j}m_{k-s_j ,j} \oplus m_{k-s_j ,j},

where is the bit-by-bit exclusive-or operator. The initial values m1,j, m2,j, ..., msj,j can be chosen freely provided that each mk,j, 1 ≤ k ≤ sj, is odd and less than 2k.

The so-called direction numbers {v1,j, v2,j, . . .} are defined by

v_{k,j} = \frac{m_{k,j}}{2^k}.

Then xi,j, the j-th component of the i-th point in a Sobol sequence, is given by

x_{i,j}=i_{1}v_{1,j} \oplus i_{2}v_{2,j} \oplus\cdots,

where ik is the k-th binary digit of i = (. . . i3i2i1)2. Here the notation (·)2 denotes the binary representation of numbers.

Read more about this topic:  Sobol Sequence

Famous quotes containing the words construction of the, construction of, construction and/or sequence:

    “No real “vital” character in fiction is altogether a conscious construction of the author. On the contrary, it may be a sort of parasitic growth upon the author’s personality, developing by internal necessity as much as by external addition.”
    —T.S. (Thomas Stearns)

    “When the leaders choose to make themselves bidders at an auction of popularity, their talents, in the construction of the state, will be of no service. They will become flatterers instead of legislators; the instruments, not the guides, of the people.”
    —Edmund Burke (1729–1797)

    “No construction stiff working overtime takes more stress and straining than we did just to stay high.”
    —Gus Van Sant, U.S. screenwriter and director, and Dan Yost. Bob Hughes (Matt Dillon)

    “We have defined a story as a narrative of events arranged in their time-sequence. A plot is also a narrative of events, the emphasis falling on causality. “The king died and then the queen died” is a story. “The king died, and then the queen died of grief” is a plot. The time sequence is preserved, but the sense of causality overshadows it.”
    —E.M. (Edward Morgan)