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
Additional Information
- Tor Sørevik
- Affiliation: Department of Mathematics, University of Bergen, Bergen, Norway
- Email: tor.sorevik@math.uib.no
- Received by editor(s): February 27, 2014
- Received by editor(s) in revised form: October 29, 2014, and January 7, 2015
- Published electronically: January 7, 2016
- © Copyright 2016 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 1821-1835
- MSC (2010): Primary 65D32; Secondary 42A10
- DOI: https://doi.org/10.1090/mcom3047
- MathSciNet review: 3471109
Dedicated: In memory of James N. Lyness