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 Free Access

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. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR 0413592
  • 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, Upper bound of the discrepancy in metric 𝐿_{𝑝}, 2≤𝑝<∞, Dokl. Akad. Nauk SSSR 252 (1980), no. 4, 805–807 (Russian). MR 580823
  • 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. Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997
  • 10. S. H. Paskov, Average case complexity of multivariate integration for smooth functions, J. Complexity 9 (1993), no. 2, 291–312. Festschrift for Joseph F. Traub, Part II. MR 1226314,
  • 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 (1980), 67–75. MR 598865
  • 13. V. N. Temlyakov, A new way of obtaining a lower bound on errors in quadrature formulas, Mat. Sb. 181 (1990), no. 10, 1403–1413 (Russian); English transl., Math. USSR-Sb. 71 (1992), no. 1, 247–257. MR 1085888
  • 14. Tony T. Warnock, Computational investigations of low-discrepancy point sets, Applications of number theory to numerical analysis (Proc. Sympos., Univ. Montreal, Montreal, Que., 1971) Academic Press, New York, 1972, pp. 319–343. MR 0351035
  • 15. H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), no. 1, 185–194. MR 1072015,

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