Computational Investigations of Optimal Scrambled Halton Sequences
TimeTuesday, July 246:30pm - 8:30pm
DescriptionRandomized quasi-random sequences RQRNS were proposed to clear the path towards practical error estimation. Although several scrambling methods for Halton sequence were proposed, some of these sequences still suffer from the correlation problem between large dimensions. For example, the Reverse Halton sequence by Vandewoestyne and Cools(VC)(2006).
I proposed an efficient linear digit scrambling method that finds the optimal Halton sequence among a family of scrambled sequences which breaks these correlations, and its optimality are judged theoretically and empirically.
In the linear permutation, πpi (bj) = wi bj (mod pi), the multiplier wi is applied to each digit in dimension j. It is obtained by a criterion involves L2-Discrepancy. The best multipliers with the smallest bounded partial quotients and that neither divide b + 1 nor b -1, are found for dimensions up to 50.
The quality of the proposed scrambled sequence is evaluated numerically by a test integral, which is one of the most difficult cases for high-dimensional numerical integration. The Halton sequence and other known scrambling sequences in the literature are used to evaluate this integral in dimension 20 ≤ s ≤ 50, which show quite large errors for over 20 dimensions. However, the proposed optimal sequences achieve much smaller relative error after dimension 20.
QMC applications improve the convergence rate but providing a practical error estimates is hard. However, I proposed optimal Halton sequence that can be used safely for several QMC applications with trustworthy practical QMC error estimate.