FoCM 2014 conference

Workshop B5 - Information Based Complexity

December 15, 18:30 ~ 19:00 - Room B23

Automatic bounding of cross--derivatives

Hernan E. Leovey

Humboldt University of Berlin, Germany   -

Calculating optimal weights for construction of rank-1 lattice rules for high dimensional integration problems in weighted spaces requires in general knowledge of the (weighted) norm of the functions at hand. The latter norm usually needs evaluation of mixed partial derivatives w.r.t. each variable at most once (cross--derivatives) in high dimensions.\\ Consider a function $f : \Omega \rightarrow \mathbb{R}^d$ that has cross--derivatives that are continuous over some convex compact set $\Omega \subset \mathbb{R}^d$. As for $d$ up to about $20$, evaluating all $2^d$ cross--derivatives in a single point $x \in \Omega$ is still quite feasible, but for much larger dimensions this task becomes prohibitively expensive. A new method for automatic bounding of cross--derivatives at a relative cost of $O(d^2)$ is given, where $d$ is the real dimension of the problem. In the new method we are content with the computation of $2\,d +1$ product and order dependent (POD) bounding coefficients $ \Lambda_{0} , \quad \overline{\Lambda} \; := \; ( \Lambda_{1}, \dots, \Lambda_{d}) \quad \text{ and } \quad \overline{\lambda} \; := \; (\lambda_{1}, \ldots, \lambda_{d})\;, $ such that for $ \mathbf{i} \subset \{1,2,\ldots,d\}$ we have $ \left | f_\mathbf{i}(x) \right | \; \leq \; {|\mathbf{i}|!}\, \Lambda_{|\mathbf{i}|} \prod_{j \in \mathbf{i}} \lambda_j .\; \\ $ This method delivers an effective way of calculating recently introduced POD weights by minimizing a less effective integration error upper bound.

Joint work with Andreas Griewank (Humboldt University of Berlin).

View abstract PDF