Multilevel Methods and Their Applications

information-based complexity (IBC) that studies problems
for which the information is priced:
The cost of an algorithm is determined by the number of
function calls that are necessary to fall below an arbitrary error bound.
Given a certain function class, IBC provides algorithms that are optimal
with respect to their convergence rate.
Usually, these are multilevel methods.

After a short introduction to IBC, an optimal multilevel algorithm
for parametric integration is introduced.
It will be shown that parametric integration corresponds to many
problems in computer graphics.
One of these problems, namely subsurface scattering,
is attacked by our optimal algorithm.
A shader that computes subsurface scattering by
direct simulation of photons is presented.
It will be demonstrated that this shader can be
dramatically accelerated by the above mentioned multilevel method.