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 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 and with
optimal methods one can obtain the order
. 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 . Here the constants 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).
