{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T09:55:42Z","timestamp":1776765342946,"version":"3.51.2"},"reference-count":15,"publisher":"American Mathematical Society (AMS)","issue":"216","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n The\n \n \n \n \n L<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n L_2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -discrepancy is a quantitative measure of precision for multivariate quadrature rules. It can be computed explicitly. Previously known algorithms needed\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n m<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O(m^2)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n operations, where\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is the number of nodes. In this paper we present algorithms which require\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n m<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n m<\/mml:mi>\n \n )<\/mml:mo>\n d<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O(m(\\log m)^d)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n operations.\n <\/p>","DOI":"10.1090\/s0025-5718-96-00756-9","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:44Z","timestamp":1027707284000},"page":"1621-1633","source":"Crossref","is-referenced-by-count":34,"title":["Efficient algorithms for computing the \ud835\udc3f\u2082-discrepancy"],"prefix":"10.1090","volume":"65","author":[{"given":"S.","family":"Heinrich","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1996]]},"reference":[{"key":"1","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Massachusetts, 1974. \\MR{0413592}"},{"key":"2","unstructured":"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.]"},{"key":"3","doi-asserted-by":"crossref","unstructured":"H. Davenport, Note on irregularities of distribution, Mathematika, 3:131\u2013135, 1956. \\MR{18:566a}","DOI":"10.1112\/S0025579300001807"},{"key":"4","doi-asserted-by":"crossref","unstructured":"D. Dobkin and D. Eppstein, Computing the discrepancy, Proceedings of the Ninth Annual Symposium on Computational Geometry, pages 47\u201352, 1993.","DOI":"10.1145\/160985.160997"},{"key":"5","doi-asserted-by":"crossref","unstructured":"D. Dobkin and D. Gunopulos, Computing the rectangle discrepancy, Preprint, Princeton University, 1994.","DOI":"10.1145\/177424.178098"},{"key":"6","unstructured":"K. K. Frolov, An upper estimate of the discrepancy in the \ud835\udc3f_{\ud835\udc5d}-metric, 2\u2264\ud835\udc5d<\u221e, Dokl. Akad. Nauk SSSR, 252:805\u2013807, 1980. English transl. in Soviet Math. Dokl. 21 (1980). \\MR{0580823}"},{"key":"7","unstructured":"K. Mulmuley, Computational geometry. An introduction through randomized algorithms, Prentice Hall, Englewood Cliffs, New Jersey, 1994."},{"key":"8","doi-asserted-by":"crossref","unstructured":"H. Niederreiter, Quasi-Monte Carlo methods and pseudo random numbers, Bull. Amer. Math. Soc., 84:957\u20131041, 1978.","DOI":"10.1090\/S0002-9904-1978-14532-7"},{"key":"9","unstructured":"H. Niederreiter, , SIAM, Philadelphia, 1992. \\MR{1172997}"},{"key":"10","doi-asserted-by":"crossref","unstructured":"S. H. Paskov, Average case complexity of multivariate integration for smooth functions, J. Complexity, 9:291\u2013312, 1993. \\MR{1226314}","DOI":"10.1006\/jcom.1993.1019"},{"key":"11","doi-asserted-by":"crossref","unstructured":"K. F. Roth, On irregularities of distribution, Mathematika, 1:73\u201379, 1954. \\MR{16:575c}","DOI":"10.1112\/S0025579300000541"},{"key":"12","doi-asserted-by":"crossref","unstructured":"K. F. Roth, On irregularities of distribution, IV, Acta Arith., 37:67\u201375, 1980. \\MR{0598865}","DOI":"10.4064\/aa-37-1-67-75"},{"key":"13","doi-asserted-by":"crossref","unstructured":"V. N. Temlyakov, On a way of obtaining lower estimates for the errors of quadrature formulas, Mat. Sbornik, 181:1403\u20131413, 1990. English transl.: Math. USSR Sbornik, 71, (1992), pp. 247\u2013257. \\MR{1085888}","DOI":"10.1070\/SM1992v071n01ABEH001396"},{"key":"14","doi-asserted-by":"crossref","unstructured":"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\u2013343. \\MR{0351035}","DOI":"10.1016\/B978-0-12-775950-0.50015-7"},{"key":"15","doi-asserted-by":"crossref","unstructured":"H. Wo\u017aniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc., 24:185\u2013194, 1991. \\MR{1072015}","DOI":"10.1090\/S0273-0979-1991-15985-9"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1996-65-216\/S0025-5718-96-00756-9\/S0025-5718-96-00756-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-216\/S0025-5718-96-00756-9\/S0025-5718-96-00756-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:17:27Z","timestamp":1776719847000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1996-65-216\/S0025-5718-96-00756-9\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"references-count":15,"journal-issue":{"issue":"216","published-print":{"date-parts":[[1996,10]]}},"alternative-id":["S0025-5718-96-00756-9"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-96-00756-9","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[1996]]}}}