Numerical methods for higher dimensional problems and the curse of the dimension.

Publication date 5 January 2000

Published in Jahresbericht der Deutschen Mathematiker-Vereinigung (DMV) (Search for Journal in Brave)

computational complexity high-dimensional problems integral equations numerical integration polynomial algorithms

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

Review text

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.

Recommendations

Cited in

(5)

This page was built for publication: Numerical methods for higher dimensional problems and the curse of the dimension.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1818934)