Good low degree rank-1 lattice rules of high dimension

Sørevik, Tor

doi:10.1090/mcom3047

Good low degree rank-1 lattice rules of high dimension
HTML articles powered by AMS MathViewer

by Tor Sørevik PDF

Math. Comp. 85 (2016), 1821-1835 Request permission

Abstract:

In this paper we introduce a novel approach to searching for rank-1 lattice rules. The idea is to separate the search into two steps, first finding good generating vectors and then finding the corresponding optimal $N$ value. For the trigonometric degree $\delta = 5$ we establish a simple criterion on the generating vectors. By using the theory for Golomb rulers and ${\mathcal B}_2$-series we construct efficient algorithms for finding good generating vectors. Combined with our own home-brewed algorithm for finding the corresponding optimal $N$, we produce new good rank-1 lattice rules of high dimension.

References

R. C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helv. 37 (1962/63), 141–147. MR 144877, DOI 10.1007/BF02566968
Marc Bourdeau and Alain Pitre, Tables of good lattices in four and five dimensions, Numer. Math. 47 (1985), no. 1, 39–43. MR 797876, DOI 10.1007/BF01389874
Ronald Cools and Hilde Govaert, Five- and six-dimensional lattice rules generated by structured matrices, J. Complexity 19 (2003), no. 6, 715–729. Information-Based Complexity Workshop (Minneapolis, MN, 2002). MR 2039626, DOI 10.1016/j.jco.2003.08.001
Ronald Cools and James N. Lyness, Three- and four-dimensional $K$-optimal lattice rules of moderate trigonometric degree, Math. Comp. 70 (2001), no. 236, 1549–1567. MR 1836918, DOI 10.1090/S0025-5718-01-01326-6
Ronald Cools and Ian H. Sloan, Minimal cubature formulae of trigonometric degree, Math. Comp. 65 (1996), no. 216, 1583–1600. MR 1361806, DOI 10.1090/S0025-5718-96-00767-3
http://www.distributed.net/Projects
A. Dimitromanolakis, Analysis of the Golomb ruler and the Sidon set problems, and determination of large near-optimal Golomb rulers, Ph.D. thesis, Technical University of Crete (2002).
P. Erdős, On a problem of Sidon in additive number theory, Acta Sci. Math. (Szeged) 15 (1954), 255–259. MR 64799
Edmund Hlawka, Zur angenäherten Berechnung mehrfacher Integrale, Monatsh. Math. 66 (1962), 140–151 (German). MR 143329, DOI 10.1007/BF01387711
Gershon Kedem and S. K. Zaremba, A table of good lattice points in three dimensions, Numer. Math. 23 (1974), 175–180. MR 373239, DOI 10.1007/BF01459950
N. M. Korobov, Teoretiko-chislovye metody v priblizhënnom analize, 2nd ed., Moskovskiĭ Tsentr Nepreryvnogo Matematicheskogo Obrazovaniya, Moscow, 2004 (Russian). MR 2078157
Bernt Lindström, An inequality for $B_{2}$-sequences, J. Combinatorial Theory 6 (1969), 211–212. MR 236138
J. N. Lyness and T. Sørevik, A search program for finding optimal integration lattices, Computing 47 (1991), no. 2, 103–120 (English, with German summary). MR 1139431, DOI 10.1007/BF02253429
J. N. Lyness and T. Sørevik, An algorithm for finding optimal integration lattices of composite order, BIT 32 (1992), no. 4, 665–675. MR 1191020, DOI 10.1007/BF01994849
J. N. Lyness and T. Sørevik, Four-dimensional lattice rules generated by skew-circulant matrices, Math. Comp. 73 (2004), no. 245, 279–295. MR 2034122, DOI 10.1090/S0025-5718-03-01534-5
J. N. Lyness and Tor Sørevik, Five-dimensional $K$-optimal lattice rules, Math. Comp. 75 (2006), no. 255, 1467–1480. MR 2219038, DOI 10.1090/S0025-5718-06-01845-X
H. M. Möller, Kubaturformeln mit minimaler Knotenzahl, Numer. Math. 25 (1975/76), no. 2, 185–200. MR 405815, DOI 10.1007/BF01462272
Dirk Nuyens and Ronald Cools, Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces, Math. Comp. 75 (2006), no. 254, 903–920. MR 2196999, DOI 10.1090/S0025-5718-06-01785-6
Imre Z. Ruzsa, Solving a linear equation in a set of integers. I, Acta Arith. 65 (1993), no. 3, 259–282. MR 1254961, DOI 10.4064/aa-65-3-259-282
James Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938), no. 3, 377–385. MR 1501951, DOI 10.1090/S0002-9947-1938-1501951-4
Ian H. Sloan, Lattice methods for multiple integration, Proceedings of the international conference on computational and applied mathematics (Leuven, 1984), 1985, pp. 131–143. MR 793949, DOI 10.1016/0377-0427(85)90012-3
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
Ian H. Sloan and Philip J. Kachoyan, Lattice methods for multiple integration: theory, error analysis and examples, SIAM J. Numer. Anal. 24 (1987), no. 1, 116–128. MR 874739, DOI 10.1137/0724010
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