Novel Algorithms for Separated Representations in Functional Form for the Adaptive Solution of Quantum Chemistry Problems and Other Applications

University Of Colorado At Boulder, Boulder CO

Investigators

Abstract

This proposal develops a new approach for solving partial differential and integral equations based on novel algorithms for separated representations in functional form. Separated representations, a natural extension of separation of variables, is a nonlinear method to approximate multidimensional functions as sums of separable functions. In this representation functions in a high-dimensional space are described with a small number of parameters, making possible to bypass the so-called curse of dimensionality, that is, to avoid the exponential growth of computational cost in the underlying dimension of the problem. The term in functional form refers to the handling of the components of separated representations in each dimension; they are obtained via a nonlinear approximation rather than via a representation through bases. This approach not only provides a greater efficiency by reducing the number of parameters but also expands the current paradigm for solving equations. By seeking solutions via a self-correcting iterative process, a new efficient algorithm keeps a manageable number of terms in the representation while maintaining the functional form of the components and the desired accuracy. The goal of this project is to design, test and implement such a reduction algorithm and apply it to solve several multidimensional problems that cannot be addressed by current methods. Many problems in modern science require computing multivariate solutions and a major challenge is to develop representations and algorithms to obtain them while avoiding the curse of dimensionality. The proposed effort develops a functional calculus for solving high dimensional problems via a self-correcting iterative process based on a combination of three types of novel algorithms: (1) Separated representations in functional form as a tool to circumvent the curse of dimensionality; (2) Highly efficient nonlinear approximations of univariate functions to achieve adaptivity of the components of the separated representations; (3) Randomized projections to reduce the number of terms in the separated representation while maintaining the functional form of the components and the desired accuracy. These adaptive algorithms should yield accurate solutions with guaranteed error bounds while requiring a computational time that scales linearly in the dimension of the problem. A particular emphasis of this proposal is on a fundamental problem of Quantum Chemistry to accurately compute the electronic structure of molecules. Accurate modeling in modern science and engineering requires computations with multivariate functions and any progress toward making such computations feasible will either significantly accelerate existing numerical methods or lead to the solution of many problems that are currently out of reach. Scientific areas to benefit from proposed algorithms are not limited to Quantum Chemistry and material sciences where the ability to understand chemical reactions and properties of materials relies heavily on efficient numerical algorithms, but also include robotics and the design of multicomponent structures, just to name a few. This proposal provides numerical tools to address the multivariate nature of many challenging scientific problems. As a result, topics of the proposal are expected to give raise to interdisciplinary collaborations as well as become part of graduate dissertations.