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 s_j 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 a_1,j, a_2,j, ..., a_{s_j−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 {m_1,j, m_2,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 m_1,j, m_2,j, ..., m_{s_j,j} can be chosen freely provided that each m_k,j, 1 ≤ k ≤ s_j, is odd and less than 2k.

The so-called direction numbers {v_1,j, v_2,j, . . .} are defined by

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

Then x_i,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 i_k is the k-th binary digit of i = (. . . i₃i₂i₁)₂. Here the notation (·)₂ denotes the binary representation of numbers.

Read more about this topic: Sobol Sequence

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

“There is, I think, no point in the philosophy of progressive education which is sounder than its emphasis upon the importance of the participation of the learner in the formation of the purposes which direct his activities in the learning process, just as there is no defect in traditional education greater than its failure to secure the active cooperation of the pupil in construction of the purposes involved in his studying.”
—John Dewey (1859–1952)

“There is, I think, no point in the philosophy of progressive education which is sounder than its emphasis upon the importance of the participation of the learner in the formation of the purposes which direct his activities in the learning process, just as there is no defect in traditional education greater than its failure to secure the active cooperation of the pupil in construction of the purposes involved in his studying.”
—John Dewey (1859–1952)

“There’s no art
To find the mind’s construction in the face.”
—William Shakespeare (1564–1616)