On the step-by-step construction of quasi–Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces

Sloan, I.; Kuo, F.; Joe, S.

doi:10.1090/S0025-5718-02-01420-5

On the step-by-step construction of quasi–Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces
HTML articles powered by AMS MathViewer

by I. H. Sloan, F. Y. Kuo and S. Joe PDF

Math. Comp. 71 (2002), 1609-1640 Request permission

Abstract:

We develop and justify an algorithm for the construction of quasi–Monte Carlo (QMC) rules for integration in weighted Sobolev spaces; the rules so constructed are shifted rank-1 lattice rules. The parameters characterising the shifted lattice rule are found “component-by-component”: the ($d+1$)-th component of the generator vector and the shift are obtained by successive $1$-dimensional searches, with the previous $d$ components kept unchanged. The rules constructed in this way are shown to achieve a strong tractability error bound in weighted Sobolev spaces. A search for $n$-point rules with $n$ prime and all dimensions 1 to $d$ requires a total cost of $O(n^3d^2)$ operations. This may be reduced to $O(n^3d)$ operations at the expense of $O(n^2)$ storage. Numerical values of parameters and worst-case errors are given for dimensions up to 40 and $n$ up to a few thousand. The worst-case errors for these rules are found to be much smaller than the theoretical bounds.

References

Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), no. 221, 299–322. MR 1433265, DOI 10.1090/S0025-5718-98-00894-1
Fred J. Hickernell, Lattice rules: how well do they measure up?, Random and quasi-random point sets, Lect. Notes Stat., vol. 138, Springer, New York, 1998, pp. 109–166. MR 1662841, DOI 10.1007/978-1-4612-1702-2_{3}
O. P. Iliev, M. S. Kaschiev, S. D. Margenov, Bl. H. Sendov, and P. S. Vassilevski (eds.), Recent advances in numerical methods and applications. II, World Scientific Publishing Co., Inc., River Edge, NJ, 1999. MR 1786606, DOI 10.1142/4061
Novak, E. and Woźniakowski, H. (2001), Intractability results for integration and discrepancy, J. Complexity, 17, 388–441.
Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1994. MR 1442955
Sloan, I. H. and Reztsov, A. V. (2002). Component-by-component construction of good lattice rules, Math. Comp., 17, 263–273.
Danfu Han and Xinghua Wang, Convergence on a deformed Newton method, Appl. Math. Comput. 94 (1998), no. 1, 65–72. MR 1627389, DOI 10.1016/S0096-3003(97)10066-2
Sloan, I. H. and Woźniakowski, H. (2001). Tractability of multivariate integration for weighted Korobov classes, J. Complexity, 17, 697–721.
Woźniakowski, H. (1999), Efficiency of quasi-Monte Carlo algorithms for high-dimensional integrals, Monte Carlo and Quasi-Monte Carlo Methods 1998 (H. Niederreiter and J. Spanier, eds.), Springer-Verlag, Berlin, 114–136.