Solving High Dimensional Numerical Problems

Fred J. Hickernell, Department of Applied Mathematics, Illinois  
Institute of Technology

A numerical algorithm that works well in one dimension can often be  
extended to higher dimensions via a suitable product form.  For  
example, finite difference methods for ordinary differential equation  
boundary value problems have analogs for partial differential  
equation boundary value problems, univariate cubic splines may be  
extended to tensor product splines, and univariate quadrature rules  
may be extended to product cubature rules.  A potential drawback of  
this approach is that the number of points where one needs to sample  
the input function grows exponentially in the dimension.  Although  
this is not a problem for dimensions 2 or 3, it quickly becomes  
problematic as the dimension increases.  For example, in pricing  
exotic options the nominal dimension may be tens, hundred or even  
thousands.  To overcome this curse of dimensionality one may resort  
to simple Monte Carlo rules, which can solve problems with very mild  
regularity assumptions, but slow convergence rates.  This talk  
describes numerical methods for high dimensional problems that  
attempt to take advantage of any inherent regularity to obtain the  
best convergence rate possible.  The algorithms are based on evenly  
spread (low discrepancy) points for sampling.  Lower bounds on  
convergence rates are derived from the statement of the problem and  
the regularity assumptions.  In some cases one may enjoy the one- 
dimensional convergence rate even when the nominal dimension is  
arbitrarily large.  This talk will provide an overview of the  
difficulties in solving high dimensional problems, highlight the  
important strides that have been made, and describe some open problems.