2003年09月18日

QMC: Halton 列

Halton 列(Halton sequence) は、 van der Corput 列を次元数分並べたベクトルになります。

たとえば、2次元の Halton 列は、(\Phi_{b1}(n), \Phi_{b2}(n)) と、2 つの van der Corput 列のベクトルになります。

2 次元以上では、サンプルがベクトル(点)になるので、Halton 点群(Halton point set) とも呼ばれるようです。

s 次元の Halton 列 は以下で定義されます。


haltonsample.gif

x_{n}^{s} は、n 番目のサンプル点です。ここで、基数 b1, b2, ... には、重ならない素数で、なるべく最小のものを割り当てます。実際には、 2, 3, 5, 7, ... と順に素数を割り当てていけばよいでしょう。

例として、b1 = 2, b2 = 3 のときの 2 次元の Halton 列を示します。


halton2table.gif
2 次元の Halton 列 (b1=2, b2=3)。

1 次元の Halton 列というのは、 van der Corput 列と同等です。

プログラム

Halton 列を求めるプログラムです。次元数は 10 以下に限定しています。


#include <stdio.h>

double vdC(int i, int base)
{
double h=0., f, factor; f=factor=1./(double)base;

while (i>0) {
h += (double)(i%base) * factor;
i /= base;
factor *= f;
}

return h;
}

void halton(double *x, int i, int dim)
{
int primes[10] = {2, 3, 5, 7, 9, 11, 13, 17, 19, 23};
int j;

if (dim >= 10) {
fprintf(stderr, "too big dimension\n");
return;
}

for (j = 0; j < dim; j++) {
x[j] = vdC(i, primes[j]);
}
}

グラフ


random2graph.gif
乱数(層別サンプリング, N=16)


halton2graph.gif
Halton 列(2 次元, N=16, b1=2, b2=3)

投稿者 syoyo : 2003年09月18日 15:18