Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces

Nuyens, Dirk; Cools, Ronald

doi:10.1090/S0025-5718-06-01785-6

Fast algorithms for component-by-component construction of rank-$1$ lattice rules in shift-invariant reproducing kernel Hilbert spaces
HTML articles powered by AMS MathViewer

by Dirk Nuyens and Ronald Cools PDF

Math. Comp. 75 (2006), 903-920 Request permission

Abstract:

We reformulate the original component-by-component algorithm for rank-$1$ lattices in a matrix-vector notation so as to highlight its structural properties. For function spaces similar to a weighted Korobov space, we derive a technique which has construction cost $O(s n \log (n))$, in contrast with the original algorithm which has construction cost $O(s n^2)$. Herein $s$ is the number of dimensions and $n$ the number of points (taken prime). In contrast to other approaches to speed up construction, our fast algorithm computes exactly the same quantity as the original algorithm. The presented algorithm can also be used to construct randomly shifted lattice rules in weighted Sobolev spaces.

References

Milton Abramowitz and Irene A. Stegun, Handbook of mathematical functions with formulas, graphs, and mathematical tables, National Bureau of Standards Applied Mathematics Series, No. 55, U. S. Government Printing Office, Washington, D.C., 1964. For sale by the Superintendent of Documents. MR 0167642
Josef Dick and Frances Y. Kuo, Constructing good lattice rules with millions of points, Monte Carlo and quasi-Monte Carlo methods 2002, Springer, Berlin, 2004, pp. 181–197. MR 2076933
J. Dick and F. Y. Kuo, Reducing the construction cost of the component-by-component construction of good lattice rules, Math. Comp. 73 (2004), no. 248, 1967–1988. MR 2059746, DOI 10.1090/S0025-5718-03-01610-7
Josef Dick, Ian H. Sloan, Xiaoqun Wang, and Henryk Woźniakowski, Liberating the weights, J. Complexity 20 (2004), no. 5, 593–623. MR 2086942, DOI 10.1016/j.jco.2003.06.002
Matteo Frigo and Steven G. Johnson, FFTW: An adaptive software architecture for the FFT, Proc. 1998 IEEE Intl. Conf. Acoustics Speech and Signal Processing, Vol. 3, IEEE, 1998, pp. 1381–1384.
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
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}
F. Y. Kuo, Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces, J. Complexity 19 (2003), no. 3, 301–320. Numerical integration and its complexity (Oberwolfach, 2001). MR 1984116, DOI 10.1016/S0885-064X(03)00006-2
Dirk Nuyens and Ronald Cools, Fast algorithms for component-by-component construction of rank-$1$ lattice rules in shift-invariant reproducing kernel Hilbert spaces, Report TW392, Dept. of Computer Science, K.U.Leuven, May 2004.
Charles M. Rader, Discrete Fourier transforms when the number of data samples is prime, Proc. IEEE 5 (1968), 1107–1108.
I. H. Sloan, F. Y. Kuo, and S. Joe, Constructing randomly shifted lattice rules in weighted Sobolev spaces, SIAM J. Numer. Anal. 40 (2002), no. 5, 1650–1665. MR 1950616, DOI 10.1137/S0036142901393942
I. H. Sloan and A. V. Reztsov, Component-by-component construction of good lattice rules, Math. Comp. 71 (2002), no. 237, 263–273. MR 1862999, DOI 10.1090/S0025-5718-01-01342-4
Charles Van Loan, Computational frameworks for the fast Fourier transform, Frontiers in Applied Mathematics, vol. 10, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1153025, DOI 10.1137/1.9781611970999