Efficient algorithms for computing the 𝐿₂-discrepancy

The L 2 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 ) O(m^2) operations, where m m is the number of nodes. In this paper we present algorithms which require O ( m ( log ⁡ m ) d ) O(m(log m)^d) operations.