Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Efficient algorithms for computing
the $L_2$-discrepancy

Author: S. Heinrich
Journal: Math. Comp. 65 (1996), 1621-1633
MSC (1991): Primary 65C05, 65D30
MathSciNet review: 1351202
Full-text PDF

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

  • 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 of the American Mathematical Society 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

Received by editor(s): April 5, 1995
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society