On lower bounds for integration of multivariate permutation-invariant functions

DOI10.1016/J.JCO.2013.10.003zbMATH Open1297.65024arXiv1310.3959OpenAlexW3104732432MaRDI QIDQ2252147FDOQ2252147

Authors: Markus Weimar 

Publication date: 16 July 2014

Published in: Journal of Complexity (Search for Journal in Brave)

Abstract: In this note we study multivariate integration for permutation-invariant functions from a certain Banach space E_{d,alpha} of Korobov type in the worst case setting. We present a lower error bound which particularly implies that in dimension d every cubature rule which reduces the initial error necessarily uses at least d+1 function values. Since this holds independently of the number of permutation-invariant coordinates, this shows that the integration problem can never be strongly polynomially tractable in this setting. Our assertions generalize results due to Sloan and Wo'zniakowski. Moreover, for large smoothness parameters alpha our bound can not be improved. Finally, we extend our results to the case of permutation-invariant functions from Korobov-type spaces equipped with product weights. Keywords: Permutation-invariance, Integration, Information complexity, Tractability, Lower bounds

Full work available at URL: https://arxiv.org/abs/1310.3959

Recommendations

• Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions. Error bounds and tractability
• Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions
• Intractability results for integration and discrepancy
• Lower bounds for the integration error for multivariate functions with mixed smoothness and optimal Fibonacci cubature for functions on the square
• Tractability of multivariate integration for periodic functions

zbMATH Keywords

lower boundsintegrationtractabilityinformation complexitypermutation-invariance

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical integration (65D30)

Cites Work

• Tractability of multivariate problems. Volume I: Linear information
• Uniform weak tractability
• The complexity of linear tensor product problems in (anti)symmetric Hilbert spaces
• An intractability result for multiple integration
• Tractability of multivariate integration for weighted Korobov spaces: My 15 year partnership with Ian Sloan

Cited In (5)

• Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions. Error bounds and tractability
• Notes on \((s,t)\)-weak tractability: a refined classification of problems with (sub)exponential information complexity
• Cubature formulas for multisymmetric functions and applications to stochastic partial differential equations
• New lower bounds for the integration of periodic functions
• Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions

This page was built for publication: On lower bounds for integration of multivariate permutation-invariant functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2252147)