19th GAMM-Seminar Leipzig on
High-dimensional problems - Numerical treatment and applications

Max-Planck-Institute for Mathematics in the Sciences
Inselstr. 22-26, D-04103 [O->]Leipzig
Phone: +49.341.9959.752, Fax: +49.341.9959.999

  19th GAMM-Seminar
January, 23th-25th, 2003
  Abstracts ->
  All seminars  
  All proceedings  
  Abstract E. Novak, Thu, 15.30-15.55 Previous Contents Next  
  Solving integral equations using random bits
E. Novak (Uni Jena)

Assume that you want to compute the function value u(s) of the solution of an integral equation
on tex2html_wrap_inline17 with Lipschitz kernel k and Lipschitz right hand side f. With a standard Monte Carlo method one can compute u(s) with cost n up to error tex2html_wrap_inline27 and with optimal methods one can obtain the order tex2html_wrap_inline29. This is a result of Heinrich and Mathé from the year 1993 (Math. Comp.).

How do the constants depend on d and what kind of a result can we expect if, instead of arbitrary random numbers, we only allow the use of random bits?

By a suitable discretized version of the standard Monte Carlo method, together with an optimal coin tossing algorithm for the summation problem, one obtains an algorithm with total cost
and error tex2html_wrap_inline35. Here the constants tex2html_wrap_inline37 do not depend on d and hence the cost increases only mildly with the dimension. In particular, the problem is tractable for this kind of restricted (or random bit) Monte Carlo algorithms.

This is part of an ongoing project about questions of tractability: how does the cost of optimal algorithms depend on the dimension d? In the past we mainly studied the problem of numerical integration and different models of computation (deterministic algorithms, randomized algorithms, algorithms for the quantum computer). My current coauthors are Stefan Heinrich (Kaiserslautern), Harald Pfeiffer (Jena) and Henryk Wozniakowski (Warsaw, New York).

    Previous Contents Next  

Last updated:
30.11.2004 Impressum
Concept, Design and Realisation
[O->]Jens Burmeister (Uni Kiel), Kai Helms (MPI Leipzig)
Valid HTML 4.0!