Multivariate Algorithms and Quasi-Monte Carlo Methods - Research Topics

Linear algorithms for numerical integration of functions are an important tool in computational mathematics. We are particularly interested in quasi-Monte Carlo and related algorithms for particularly high-dimensional integration problems. Introductions to quasi-Monte Carlo integration can be found in several monographs as for example the books of Niederreiter [2], Dick and Pillichshammer [1], and Sloan and Joe [3].

[1] J. Dick, F. Pillichshammer. Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge, 2010.
[2] H. Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia, 1992.
[3] I.H. Sloan, S. Joe. Lattice Methods for Multiple Integration. Oxford University Press, Oxford, 1994.

There are literally thousands of articles and books on the problem of approximating a given function. In our project, we focus on approximation of multivariate functions based on quasi-Monte Carlo algorithms. The application of modern quasi-Monte Carlo algorithms to approximation problems is relatively new, for an introduction see, e.g., [1]. We are also interested in function approximation in the context of using more general linear approximation algorithms.

[1] F.Y. Kuo, I.H. Sloan, H. Wozniakowski. Lattice rules for multivariate approximation in the worst case setting. In: H. Niederreiter, D. Talay (eds.). Monte Carlo and Quasi-Monte Carlo Methods 2004, pp. 289-330. Springer, Berlin, 2006.

When dealing with multivariate algorithms and analyzing their errors, we are interested in how much information about a given problem we need to guarantee an error not exceeding a certain (small) threshold. This, roughly speaking, is the subject of the field of information-based complexity. This is particularly relevant for problems where we have to deal with a large number of variables. For introductions to this field, we refer to the books [1]-[4].

[1] E. Novak, H. Wozniakowski. Tractability of Multivariate Problems, Volume I: Linear Information. EMS, Zürich, 2008.
[2] E. Novak, H. Wozniakowski. Tractability of Multivariate Problems, Volume II: Standard Information for Functionals. EMS, Zürich, 2010.
[3] E. Novak, H. Woznaikowski. Tractability of Multivariate Problems, Volume III: Standard Information for Operators. EMS, Zürich, 2012.
[4] J.F. Traub, G.W. Wasilkowski, H. Wozniakowski. Information-Based Complexity. Academic Press, New York, 1988.

When dealing with quasi-Monte carlo and related methods, as for example integration rules, there are not always explicit methods at hand that yield a low error. This is why one frequently has to resort to algorithms for constructing a good method for a specific problem. The state of the art in this context are so-called component-by-component algorithms. These algorithms choose good parameters for a suitable method one component after the other, thereby increasing the efficiency of search algorithms. In our research we deal with methods to speed up existing constructions and finding new and computationally efficient algorithms for certain multivariate problems.