An intractability result for multiple integration
HTML articles powered by AMS MathViewer
- by I. H. Sloan and H. Woźniakowski PDF
- Math. Comp. 66 (1997), 1119-1124 Request permission
Abstract:
We prove that the problem of multiple integration in the Korobov class $E_{\alpha ,d}$ is intractable since the number of function evaluations required to achieve a worst case error less than $1$ is exponential in the dimension.References
- Shaun Disney, Error bounds for rank $1$ lattice quadrature rules modulo composites, Monatsh. Math. 110 (1990), no. 2, 89–100. MR 1076324, DOI 10.1007/BF01302778
- Shaun Disney and Ian H. Sloan, Error bounds for the method of good lattice points, Math. Comp. 56 (1991), no. 193, 257–266. MR 1052090, DOI 10.1090/S0025-5718-1991-1052090-6
- Shaun Disney and Ian H. Sloan, Lattice integration rules of maximal rank formed by copying rank $1$ rules, SIAM J. Numer. Anal. 29 (1992), no. 2, 566–577. MR 1154284, DOI 10.1137/0729036
- Loo Keng Hua and Yuan Wang, Applications of number theory to numerical analysis, Springer-Verlag, Berlin-New York; Kexue Chubanshe (Science Press), Beijing, 1981. Translated from the Chinese. MR 617192, DOI 10.1007/978-3-642-67829-5
- Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
- Sharygin, I. F., A lower estimate for the error of quadrature formulas for certain classes of functions (in Russian), Zh. Vychisl. Mat. i Mat. Fiz., 3, 370-376 (1963).
- Sloan, I.H. and Joe, S. Lattice methods for multiple integration. Oxford University Press, Oxford (1994).
- 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
- J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR 958691
Additional Information
- I. H. Sloan
- Affiliation: School of Mathematics, University of New South Wales, Sydney 2052, Australia
- MR Author ID: 163675
- ORCID: 0000-0003-3769-0538
- H. Woźniakowski
- Affiliation: Department of Computer Science, Columbia University, New York, New York 10027 and Institute of Applied Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warsaw, Poland
- Received by editor(s): December 21, 1995
- Received by editor(s) in revised form: May 3, 1996
- Additional Notes: The first author was partially supported by the Australian Research Council.
The second author was partially supported by the National Science Foundation and the Air Force Office of Scientific Research. - © Copyright 1997 American Mathematical Society
- Journal: Math. Comp. 66 (1997), 1119-1124
- MSC (1991): Primary 41A55, 65D30
- DOI: https://doi.org/10.1090/S0025-5718-97-00834-X
- MathSciNet review: 1401946