Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



An intractability result for multiple integration

Authors: I. H. Sloan and H. Woźniakowski
Journal: Math. Comp. 66 (1997), 1119-1124
MSC (1991): Primary 41A55, 65D30
MathSciNet review: 1401946
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Disney, S.A.R. Error bounds for rank 1 lattice quadrature rules modulo composites. Monatshefte für Mathematik, 110, 89-100 (1990). MR 91m:65067
  • 2. Disney, S.A.R. and Sloan, I.H. Error bounds for the method of good lattice points. Mathematics of Computation, 56, 257-66 (1991). MR 91m:65068
  • 3. Disney, S.A.R. and Sloan, I.H., Lattice integration rules of maximal rank formed by copying rank 1 rules, SIAM Journal on Numerical Analysis, 29, 566-77 (1992). MR 92k:65034
  • 4. Hua, L. K. and Wang, Y., Applications of number theory to numerical analysis. Springer Verlag, Berlin (1981). MR 83g:10034
  • 5. Niederreiter, H. Random number generation and quasi-Monte Carlo methods. Society for Industrial and Applied Mathematics, Philadelphia (1992). MR 93h:65008
  • 6. 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).
  • 7. Sloan, I.H. and Joe, S. Lattice methods for multiple integration. Oxford University Press, Oxford (1994).
  • 8. Sloan, I.H. and Kachoyan, P.J. Lattice methods for multiple integration: theory, error analysis and examples. SIAM Journal on Numerical Analysis, 24, 116-28 (1987). MR 88e:65023
  • 9. Traub, J.F., Wasilkowski, G. and Wo\'{z}niakowski, H. Information-based complexity. Academic Press, Boston (1988). MR 90f:68085

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 41A55, 65D30

Retrieve articles in all journals with MSC (1991): 41A55, 65D30

Additional Information

I. H. Sloan
Affiliation: School of Mathematics, University of New South Wales, Sydney 2052, Australia

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

Keywords: Multiple integration, intractability, lattice rules
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.
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society