Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Efficient algorithms for computing the $L_2$-discrepancy

Author(s): S. Heinrich.
Journal: Math. Comp. 65 (1996), 1621-1633.
MSC (1991): Primary 65C05, 65D30
Retrieve article in: PDF
This article is available free of charge

Abstract | References | Similar articles | Additional information

Abstract: The $L_2$-discrepancy is a quantitative measure of precision for multivariate quadrature rules. It can be computed explicitly. Previously known algorithms needed $O(m^2)$ operations, where $m$ is the number of nodes. In this paper we present algorithms which require $O(m(\log m)^d)$ 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 ${L}_p$-metric, $2 \le p < \infty $,

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

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google