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 (1956), 131–135. MR 0082531
  • 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, 10.1006/jcom.1993.1019
  • 11. K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 73–79. MR 0066435
  • 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, 10.1090/S0273-0979-1991-15985-9

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