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.65150Many 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.

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.

Reviewer: Heiner Mühlig (Dresden)

##### MSC:

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 (should also be assigned at least one other classification number from Section 41-XX) |

68Q25 | Analysis of algorithms and problem complexity |