Abstract
We study multivariate integration of functions that are invariant under permutations (of subsets) of their arguments. We find an upper bound for the nth minimal worst case error and show that under certain conditions, it can be bounded independent of the number of dimensions. In particular, we study the application of unshifted and randomly shifted rank-1 lattice rules in such a problem setting. We derive conditions under which multivariate integration is polynomially or strongly polynomially tractable with the Monte Carlo rate of convergence \(\mathcal {O}(n^{-1/2})\). Furthermore, we prove that those tractability results can be achieved with shifted lattice rules and that the shifts are indeed necessary. Finally, we show the existence of rank-1 lattice rules whose worst case error on the permutation- and shift-invariant spaces converge with (almost) optimal rate. That is, we derive error bounds of the form \(\mathcal {O}(n^{-\lambda /2})\) for all 1≤λ<2α, where α denotes the smoothness of the spaces.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aronszajn, N.: Theory of reproducing kernels. Trans. Amer. Math. Soc 68(3), 337–404 (1950)
Dick, J., Kuo, F.Y., Sloan, I.H.: High dimensional integration: The quasi-Monte Carlo way. Acta Numer. 22, 133–288 (2013)
Dick, J., Pillichshammer, F.: Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge Univ. Press, Cambridge (2010)
Hickernell, F.J., Woźniakowski, H.: Integration and approximation in arbitrary dimensions. Adv. Comput. Math 12, 25–58 (2000)
Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems. Vol. I: Linear Information, EMS Tracts in Mathematics, vol. 6. European Mathematical Society (EMS), Zürich (2008)
Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems. Vol. II: Standard Information for Functionals, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich (2010)
Nuyens, D. The construction of good lattice rules and polynomial lattice rules. In: Kritzer, P., Niederreiter, H., Pillichshammer, F., Winterhof, A. (eds.) : Uniform Distribution and Quasi-Monte Carlo Methods: Discrepancy, Integration and Applications, Radon Series on Computational and Applied Mathematics, vol. 15, pp. 223–256. De Gruyter, Berlin, Boston (2014)
Nuyens, D., Suryanarayana, G., Weimar, M.: Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions. In preparation (2015)
Plaskota, L., Wasilkowski, G.W., Zhao, Y.: New averaging technique for approximating weighted integrals. J. Complexity 25, 268–291 (2009)
Sloan, I.H., Joe, S.: Lattice Methods for Multiple Integration. Oxford Science Publ., Oxford Univ. Press, New York (1994)
Sloan, I.H., Woźniakowski, H.: An intractability result for multiple integration. Math. Comp 66, 1119–1124 (1997)
Sloan, I.H., Woźniakowski, H.: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?. J. Complexity 14, 1–33 (1998)
Ullrich, T.: Smolyak’s algorithm, sampling on sparse grids and Sobolev spaces of dominating mixed smoothness. East J. Approx. 14(1), 1–38 (2008)
Weimar, M.: The complexity of linear tensor product problems in (anti)symmetric Hilbert spaces. J. Approx. Theory 164(10), 1345–1368 (2012)
Weimar, M.: On lower bounds for integration of multivariate permutation-invariant functions. J. Complexity 30(1), 87–97 (2014)
Yserentant, H.: Regularity and Approximability of Electronic Wave Functions. Lecture Notes in Mathematics. Springer-Verlag, Berlin (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: Ian H. Sloan
Rights and permissions
About this article
Cite this article
Nuyens, D., Suryanarayana, G. & Weimar, M. Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions. Adv Comput Math 42, 55–84 (2016). https://doi.org/10.1007/s10444-015-9411-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10444-015-9411-6