Computational Complexity of Highly Nonlinear Approximations

The efficient numerical treatment of partial differential equations on high-dimensional spaces often requires approximation methods involving a high degree of nonlinearity, such as low-rank tensor representations or neural networks. By exploiting structural features of solutions, such approaches in many cases promise extremely efficient approximations. However, due to the corresponding greater difficulty of computing highly compressed representations, such results need to be considered in conjunction with the costs of numerical methods for constructing these approximations. A main objective of the project is to address the gap between theoretical complexity bounds and the performance of practical implementations of solvers, with particular focus on low-rank tensor representations, linear combinations of arbitrary Gaussian functions, as well as neural networks and more general compositions of functions. We also aim to understand the relative suitability of particular nonlinear approximation methods for different problem classes, such as problems with many parameters, evolution problems for probability distributions and wave functions, and eigenvalue problems in quantum chemistry. In each case, it is crucial to avoid numerical instabilities in the interaction of nonlinear approximations and differential operators and to ensure reliability of results in high dimensions by suitable computable error bounds.