Efficient algorithms for computing the L(2)-discrepancy

被引：27

作者：

Heinrich, S

机构：

[1] Fachbereich Informatik, Universität Kaiserslautern

来源：

MATHEMATICS OF COMPUTATION | 1996年 / 65卷 / 216期

关键词：

D O I：

10.1090/S0025-5718-96-00756-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：1621 / 1633

页数：13

共 15 条

[1]

Aho A.V., 1974, The Design and Analysis of Computer Algorithms

[2]

Bykovskii V.A., 1985, CORRECT ORDER ERROR

[3]

Davenport H., 1956, MATHEMATIKA, V3, P131

[4]

DOBKIN D, 1993, P 9 ANN S COMP GEOM, P47

[5]

DOBKIN D, 1994, COMPUTING RECTANGLE

[6]

FROLOV KK, 1980, DOKL AKAD NAUK SSSR+, V252, P805

[7]

Mulmuley K., 1994, Computational Geometry: an Introduction through Randomized Algorithms

[8] QUASI-MONTE CARLO METHODS AND PSEUDO-RANDOM NUMBERS [J].

NIEDERREITER, H .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1978, 84 (06) :957-1041

[9]

Niederreiter H., 1992, RANDOM NUMBER GENERA

[10]

Paskov S. H., 1993, Journal of Complexity, V9, P291, DOI 10.1006/jcom.1993.1019

← 1 2 →