FAURE_NEXT

Computes a shuffled Faure sequence.

Required Arguments

STATE —  An IMSL_FAURE pointer containing the structure created by the call to FAURE_INIT.  The structure contains information about the sequence.  The structure should be freed using FAURE_FREE after it is no longer needed.   (Input/Output)

NEXT_PT  —  Vector of length NDIM containing the next point in the shuffled Faure sequence, where NDIM is the dimension of the hyper-rectangle specified in FAURE_INIT.      (Output)

Optional Arguments

IMSL_RETURN_SKIP — Returns the current point in the sequence. The sequence can be restarted by calling FAURE_INIT using this value for NSKIP, and using the same value for NDIM.   (Input)

FORTRAN 90 Interface

Generic:                              CALL FAURE_NEXT (STATE, NEXT_PT [,…])

Specific:                             The specific interface names are S_FAURE_NEXT and D_FAURE_NEXT.

Description

Discrepancy measures the deviation from uniformity of a point set.

The discrepancy of the point set , is defined

where the supremum is over all subsets of [0, 1]^d of the form

,

λ is the Lebesque measure, and is the number of the x_j contained in E.

The sequence x₁, x₂, … of points [0,1]^d is a low-discrepancy sequence if there exists a constant c(d), depending only on d, such that

for all n>1.

Generalized Faure sequences can be defined for any prime base b≥d. The lowest bound for the discrepancy is obtained for the smallest prime b≥d, so the optional argument NBASE defaults to the smallest prime greater than or equal to the dimension.

The generalized Faure sequence x₁, x₂, …, is computed as follows:

Write the positive integer n in its b-ary expansion,

where a_i(n) are integers, .

The j-th coordinate of x_n is

 

The generator matrix for the series, ,  is defined to be

and  is an element of the Pascal matrix,

It is faster to compute a shuffled Faure sequence than to compute the Faure sequence itself. It can be shown that this shuffling preserves the low-discrepancy property.

The shuffling used is the b-ary Gray code. The function G(n) maps the positive integer n into the integer given by its b-ary expansion.

The sequence computed by this function is x(G(n)), where x is the generalized Faure sequence.

Example

In this example, five points in the Faure sequence are computed. The points are in the three-dimensional unit cube.

Note that FAURE_INIT is used to create a structure that holds the state of the sequence. Each call to FAURE_NEXT returns the next point in the sequence and updates the IMSL_FAURE structure. The final call to FAURE_FREE frees data items, stored in the structure, that were allocated by FAURE_INIT.

 

        use faure_int

        implicit none

        type (s_imsl_faure), pointer  :: state

        real(kind(1e0))          :: x(3)

        integer,parameter :: ndim=3

        integer           :: k

!                                  CREATE THE STRUCTURE THAT HOLDS

!                                  THE STATE OF THE SEQUENCE.

        call faure_init(ndim, state)

!                                  GET THE NEXT POINT IN THE SEQUENCE

        do k=1,5

           call faure_next(state, x)

           write(*,'(3F15.3)') x(1), x(2) , x(3)

        enddo

!                                   FREE DATA ITEMS STORED IN

!                                   state STRUCTURE

        call faure_free(state)

                     end

Output

 

     0.334      0.493       0.064

     0.667      0.826       0.397

     0.778      0.270       0.175

     0.111      0.604       0.509

     0.445      0.937       0.842

http://www.vni.com/ PHONE: 713.784.3131 FAX:713.781.9260