Numerical methods for higher dimensional problems and the curse of the dimension. (Numerische Verfahren für hochdimesionale Probleme und der Fluch der Dimension.) (English) Zbl 0958.65150

Many high-dimensional problems are difficult and the computational expense of their numerical solution methods increases exponentially. This is, for instance, the situation in case of numerical integration and approximation, numerical methods for many integral equations and partial differential equations, but not for convex optimization and systems of ordinary differential equations.
In the presented paper, the following problems are discussed: problems with the curse of high dimension, i.e. exponential lower bounds exist, problems without the curse of high dimension, i.e. polynomial algorithms exist, construction of polynomial algorithms and the question what is an optimal method.
The author presents some new results from the theory of optimal numerical methods and shows that there are many connections with classical questions in approximation theory, stochastics and number theory. The reader will find many suggestions for additional studies in the area of high-dimensional problems.


65Y20 Complexity and performance of numerical algorithms
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
65D32 Numerical quadrature and cubature formulas
65C05 Monte Carlo methods
11K38 Irregularities of distribution, discrepancy
41A55 Approximate quadratures
41A63 Multidimensional problems
68Q25 Analysis of algorithms and problem complexity