|
An intractability result for multiple integration
Author(s):
I.
H.
Sloan;
H.
Wozniakowski.
Journal:
Math. Comp.
66
(1997),
1119-1124.
MSC (1991):
Primary 41A55, 65D30
Retrieve article in:
PDF DVI PostScript
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We prove that the problem of multiple integration in the Korobov class  is intractable since the number of function evaluations required to achieve a worst case error less than  is exponential in the dimension.
References:
- 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
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.
Wozniakowski
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
DOI:
10.1090/S0025-5718-97-00834-X
PII:
S 0025-5718(97)00834-X
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.
Copyright of article:
Copyright
1997,
American Mathematical Society
|
Comments: webmaster@ams.org