Browse Prior Art Database

Generation of New Low-Discrepancy Points

IP.com Disclosure Number: IPCOM000038709D
Original Publication Date: 1987-Feb-01
Included in the Prior Art Database: 2005-Jan-31
Document File: 2 page(s) / 30K

Publishing Venue

IBM

Related People

Tezuka, S: AUTHOR

Abstract

This invention provides generation of a new set of low-discrepancy points which can be easily obtained. Low-discrepancy point sets, such as Hammersley sequences and good lattice points, are very efficient for calculating approximate values of integrals of certain classes of functions defined on the multi-dimensional unit cube[*]. However, it is time-consuming to obtain these conventional low-discrepancy point sets. The new set of low-discrepancy points of this invention are based on binary vectors over GF(2). Let v(j) be a binary vector t(j1, j2, p), where j is a p-bit integer represented by (j1, j2, ..., jp) in the binary form and t( ) is a transposed matrix. v-( ) denotes a p-bit integer j, where is a binary vector t(j1, j2, ..., jp). Then a new set of points in the k-dimensional unit cube is expressed as, for j=0, 1, ...

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 78% of the total text.

Page 1 of 2

Generation of New Low-Discrepancy Points

This invention provides generation of a new set of low-discrepancy points which can be easily obtained. Low-discrepancy point sets, such as Hammersley sequences and good lattice points, are very efficient for calculating approximate values of integrals of certain classes of functions defined on the multi-dimensional unit cube[*]. However, it is time-consuming to obtain these conventional low-discrepancy point sets. The new set of low-discrepancy points of this invention are based on binary vectors over GF(2). Let v(j) be a binary vector t(j1, j2, p), where j is a p-bit integer represented by (j1, j2, ..., jp) in the binary form and t( ) is a transposed matrix. v-( ) denotes a p-bit integer j, where is a binary vector t(j1, j2, ..., jp). Then a new set of points in the k-dimensional unit cube is expressed as, for j=0, 1, ..., N-1, (1/N) (v-1(T1 v(j)), v-1(T2 v(j)), ..., v-1(Tk v(j)) where Ti (i=1, 2, ..., k) is a pxp binary matrix and N=2p . The k-dimensional discrepancy of the set is bounded from above by the order of (log
N)k/N, where N is the number of the points. An example for a set of 128 points is shown below. The points of the set are given as, for j=0, 1, ..., 127, (1/128) (v-1(T1 v(j)), v-1(T2 v(j)), v-1(T3 v(j)), where T1 = 1000100 T2 = 1110100 T3 = 0010111 0001011 0110111 1001101

1010111 1110101 1001110

1100010 1110001 1100101

1001100 0011010 1110110

0101111 1010010 1010001

0110011 1110011 0100101 The generation...