15. ÖMG-Kongress
Jahrestagung der Deutschen Mathematikervereinigung

16. bis 22. September 2001 in Wien

Minisymposium Zahlentheoretische Algorithmen und ihre Anwendungen
Dienstag, 18. September 2001, 17.20, Audimax der Universität Wien


Combinatorial problems arising in high dimensional integration and approximation

Art Owen, Stanford University


Integrating and approximating a function over the unit hyper-cube in dimension d, are a fundamental numerical tasks with many applications. Integration methods are widely used in valuation of financial derivatives. Approximation methods are used in the design of complex products like semiconductors and aircraft.

For small d, simple methods that evaluate the target function on a grid work very well. As the dimension d increases, such tensor product methods become computationally infeasible.

Sampling methods, such as Monte Carlo, are much less sensitive to the dimension effect, and are the practical methods of choice for large d. Better sampling methods, such as quasi-Monte Carlo sampling, use combinatorics to define the input points.

This talk surveys recent work in sampling methods for integration and approximation, and presents some challenges for combinatorial methods. One challenge is to develop point sets with some equidistribution properties of (t,m,s)-nets but for which the equidistribution is much better for relatively important dimensions. Another is to study performance bounds for equidistribution, analogous to the bounds on orthogonal array strength, for very high dimensions. A third challenge is to construct point sets in the unit cube that are better for quasi-regression approximation than are random points. A fourth challenge is to construct point sets that are better for integrating very smooth functions.

Zeitplan der Sektion   Tagesübersicht   Liste der Vortragenden