Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions

详细信息    查看全文

• 作者：Dirk Nuyens ; Gowri Suryanarayana ; Markus Weimar
• 关键词：Numerical integration ; Quadrature ; Cubature ; Quasi ; Monte Carlo methods ; Rank ; 1 lattice rules ; 65D32 ; 65Y20 ; 68Q25 ; 68W40
• 刊名：Advances in Computational Mathematics
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：42
• 期：1
• 页码：55-84
• 全文大小：433 KB
• 参考文献：1.Aronszajn, N.: Theory of reproducing kernels. Trans. Amer. Math. Soc 68(3), 337–404 (1950)CrossRef MathSciNet MATH
  2.Dick, J., Kuo, F.Y., Sloan, I.H.: High dimensional integration: The quasi-Monte Carlo way. Acta Numer. 22, 133–288 (2013)CrossRef MathSciNet MATH
  3.Dick, J., Pillichshammer, F.: Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge Univ. Press, Cambridge (2010)CrossRef
  4.Hickernell, F.J., Woźniakowski, H.: Integration and approximation in arbitrary dimensions. Adv. Comput. Math 12, 25–58 (2000)CrossRef MathSciNet MATH
  5.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)
  6.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)
  7.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)
  8.Nuyens, D., Suryanarayana, G., Weimar, M.: Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions. In preparation (2015)
  9.Plaskota, L., Wasilkowski, G.W., Zhao, Y.: New averaging technique for approximating weighted integrals. J. Complexity 25, 268–291 (2009)CrossRef MathSciNet MATH
  10.Sloan, I.H., Joe, S.: Lattice Methods for Multiple Integration. Oxford Science Publ., Oxford Univ. Press, New York (1994)
  11.Sloan, I.H., Woźniakowski, H.: An intractability result for multiple integration. Math. Comp 66, 1119–1124 (1997)CrossRef MathSciNet MATH
  12.Sloan, I.H., Woźniakowski, H.: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?. J. Complexity 14, 1–33 (1998)CrossRef MathSciNet MATH
  13.Ullrich, T.: Smolyak’s algorithm, sampling on sparse grids and Sobolev spaces of dominating mixed smoothness. East J. Approx. 14(1), 1–38 (2008)MathSciNet MATH
  14.Weimar, M.: The complexity of linear tensor product problems in (anti)symmetric Hilbert spaces. J. Approx. Theory 164(10), 1345–1368 (2012)CrossRef MathSciNet MATH
  15.Weimar, M.: On lower bounds for integration of multivariate permutation-invariant functions. J. Complexity 30(1), 87–97 (2014)CrossRef MathSciNet MATH
  16.Yserentant, H.: Regularity and Approximability of Electronic Wave Functions. Lecture Notes in Mathematics. Springer-Verlag, Berlin (2010)CrossRef
  
• 作者单位：Dirk Nuyens (1)
  Gowri Suryanarayana (1)
  Markus Weimar (2)
  
  1. Department of Computer Science, KU Leuven, Celestijnenlaan 200A, 3001, Heverlee, Belgium
  2. Faculty of Mathematics and Computer Science, Workgroup Numerics and Optimization, Philipps-University Marburg, Hans-Meerwein-Straße, Lahnberge, 35032, Marburg, Germany
  
• 刊物类别：Computer Science
• 刊物主题：Numeric Computing
  Calculus of Variations and Optimal Control
  Mathematics
  Algebra
  Theory of Computation
  
• 出版者：Springer U.S.
• ISSN：1572-9044

文摘

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. Keywords Numerical integration Quadrature Cubature Quasi-Monte Carlo methods Rank-1 lattice rules