Efficient algorithms for computing the $L_2$-discrepancy
HTML articles powered by AMS MathViewer
- by S. Heinrich PDF
- Math. Comp. 65 (1996), 1621-1633 Request permission
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
-
A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Massachusetts, 1974. MR 0413592
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.]
H. Davenport, Note on irregularities of distribution, Mathematika, 3:131–135, 1956. MR 18:566a
D. Dobkin and D. Eppstein, Computing the discrepancy, Proceedings of the Ninth Annual Symposium on Computational Geometry, pages 47–52, 1993.
D. Dobkin and D. Gunopulos, Computing the rectangle discrepancy, Preprint, Princeton University, 1994.
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 0580823
K. Mulmuley, Computational geometry. An introduction through randomized algorithms, Prentice Hall, Englewood Cliffs, New Jersey, 1994.
H. Niederreiter, Quasi-Monte Carlo methods and pseudo random numbers, Bull. Amer. Math. Soc., 84:957–1041, 1978.
H. Niederreiter, , SIAM, Philadelphia, 1992. MR 1172997
S. H. Paskov, Average case complexity of multivariate integration for smooth functions, J. Complexity, 9:291–312, 1993. MR 1226314
K. F. Roth, On irregularities of distribution, Mathematika, 1:73–79, 1954. MR 16:575c
K. F. Roth, On irregularities of distribution, IV, Acta Arith., 37:67–75, 1980. MR 0598865
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 1085888
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 0351035
H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc., 24:185–194, 1991. MR 1072015
Additional Information
- S. Heinrich
- Affiliation: Fachbereich Informatik, Universität Kaiserslautern, D-67653 Kaiserslautern, Germany
- Email: heinrich@informatik.uni-kl.de
- Received by editor(s): April 5, 1995
- © Copyright 1996 American Mathematical Society
- Journal: Math. Comp. 65 (1996), 1621-1633
- MSC (1991): Primary 65C05, 65D30
- DOI: https://doi.org/10.1090/S0025-5718-96-00756-9
- MathSciNet review: 1351202