|
Efficient algorithms for computing the  -discrepancy
Author(s):
S.
Heinrich.
Journal:
Math. Comp.
65
(1996),
1621-1633.
MSC (1991):
Primary 65C05, 65D30
MathSciNet review:
1351202
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
The  -discrepancy is a quantitative measure of precision for multivariate quadrature rules. It can be computed explicitly. Previously known algorithms needed  operations, where  is the number of nodes. In this paper we present algorithms which require  operations.
References:
- 1.
- A. V. Aho, J. E. Hopcroft, and J. D. Ullman,
The design and analysis of computer algorithms, Addison-Wesley, Reading, Massachusetts, 1974. MR 54:1706 - 2.
- V. A. Bykovskii,
On the correct order of the error of optimal cubature formulas in spaces with dominant derivative, and on quadratic deviations of grids, Preprint, Computing Center Far-Eastern Scientific Center, Acad. Sci. USSR, Vladivostok, 1985. (Russian) [R. Zh. Mat. 1986, 7B 1663.] - 3.
- H. Davenport,
Note on irregularities of distribution, Mathematika, 3:131 -- 135, 1956. MR 18:566a - 4.
- D. Dobkin and D. Eppstein,
Computing the discrepancy, Proceedings of the Ninth Annual Symposium on Computational Geometry, pages 47 -- 52, 1993. - 5.
- D. Dobkin and D. Gunopulos,
Computing the rectangle discrepancy, Preprint, Princeton University, 1994. - 6.
- K. K. Frolov,
An upper estimate of the discrepancy in the  -metric,  , Dokl. Akad. Nauk SSSR, 252:805 -- 807, 1980. English transl. in Soviet Math. Dokl. 21 (1980). MR 81k:10087 - 7.
- K. Mulmuley,
Computational geometry. An introduction through randomized algorithms, Prentice Hall, Englewood Cliffs, New Jersey, 1994. - 8.
- H. Niederreiter,
Quasi-Monte Carlo methods and pseudo random numbers, Bull. Amer. Math. Soc., 84:957 -- 1041, 1978. - 9.
- H. Niederreiter,
Random number generation and quasi-Monte Carlo methods, SIAM, Philadelphia, 1992. MR 93h:65008 - 10.
- S. H. Paskov,
Average case complexity of multivariate integration for smooth functions, J. Complexity, 9:291 -- 312, 1993. MR 94f:65135 - 11.
- K. F. Roth,
On irregularities of distribution, Mathematika, 1:73 -- 79, 1954. MR 16:575c - 12.
- K. F. Roth,
On irregularities of distribution, IV, Acta Arith., 37:67 -- 75, 1980. MR 82f:10063 - 13.
- V. N. Temlyakov,
On a way of obtaining lower estimates for the errors of quadrature formulas, Mat. Sbornik, 181:1403 -- 1413, 1990. English transl.: Math. USSR Sbornik, 71, (1992), pp. 247 -- 257. MR 92a:65083 - 14.
- T. T. Warnock,
Computational investigations of low discrepancy point sets. In S. K. Zaremba, editor, Applications of Number Theory to Numerical Analysis, Academic Press, New York, 1972, pp. 319 -- 343. MR 50:3526 - 15.
- H. Wo\'{z}niakowski,
Average case complexity of multivariate integration, Bull. Amer. Math. Soc., 24:185 -- 194, 1991. MR 91i:65224
Similar Articles:
Retrieve articles in Mathematics of Computation
with
MSC (1991):
65C05, 65D30
Retrieve articles in all Journals with
MSC (1991):
65C05, 65D30
Additional Information:
S.
Heinrich
Affiliation:
Fachbereich Informatik, Universität Kaiserslautern, D-67653 Kaiserslautern, Germany
Email:
heinrich@informatik.uni-kl.de
DOI:
10.1090/S0025-5718-96-00756-9
PII:
S 0025-5718(96)00756-9
Received by editor(s):
April 5, 1995
Copyright of article:
Copyright
1996,
American Mathematical Society
|
