Search for: All records

A large literature specifies conditions under which the information complexity for a se- quence of numerical problems defined for dimensions 1, 2, . . . grows at a moderate rate, i.e., the sequence of problems is tractable. Here, we focus on the situation where the space of available information consists of all linear functionals, and the problems are defined as lin- ear operator mappings between Hilbert spaces. We unify the proofs of known tractability results and generalize a number of existing results. These generalizations are expressed as five theorems that provide equivalent conditions for (strong) tractability in terms of sums of functions of the singular values of the solution operators. 

Abstract Let $$f:[0,1]^{d}\to{\mathbb{R}}$$ be a completely monotone integrand as defined by Aistleitner and Dick (2015, Acta Arithmetica, 167, 143–171) and let points $$\boldsymbol{x}_{0},\dots ,\boldsymbol{x}_{n-1}\in [0,1]^{d}$$ have a non-negative local discrepancy (NNLD) everywhere in $$[0,1]^{d}$$. We show how to use these properties to get a non-asymptotic and computable upper bound for the integral of $$f$$ over $$[0,1]^{d}$$. An analogous non-positive local discrepancy property provides a computable lower bound. It has been known since Gabai (1967, Illinois J. Math., 11, 1–12) that the two-dimensional Hammersley points in any base $$b\geqslant 2$$ have NNLD. Using the probabilistic notion of associated random variables, we generalize Gabai’s finding to digital nets in any base $$b\geqslant 2$$ and any dimension $$d\geqslant 1$$ when the generator matrices are permutation matrices. We show that permutation matrices cannot attain the best values of the digital net quality parameter when $$d\geqslant 3$$. As a consequence the computable absolutely sure bounds we provide come with less accurate estimates than the usual digital net estimates do in high dimensions. We are also able to construct high-dimensional rank one lattice rules that are NNLD. We show that those lattices do not have good discrepancy properties: any lattice rule with the NNLD property in dimension $$d\geqslant 2$$ either fails to be projection regular or has all its points on the main diagonal. Complete monotonicity is a very strict requirement that for some integrands can be mitigated via a control variate.