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

用于量子化学问题和其他应用的自适应解决方案的函数形式分离表示的新算法

• 批准号: 1320919
• 负责人: Gregory Beylkin
• 金额: $ 33万
• 依托单位: University of Colorado at Boulder
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-15 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1320919&HistoricalAwards=false
• 关键词: Novel; Algorithms; Separated; Representations; Functional

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.

该提案开发了一种基于函数形式分离表示的新颖算法来求解偏微分和积分方程的新方法。分离表示是变量分离的自然延伸，是一种将多维函数近似为可分离函数之和的非线性方法。在这种高维空间中的表示函数用少量参数来描述，使得绕过所谓的维数灾难成为可能，即避免问题的基础维度中计算成本的指数增长。 函数形式的术语是指对每个维度中分离表示的组件的处理；它们是通过非线性近似而不是通过基数表示获得的。这种方法不仅通过减少参数数量提供了更高的效率，而且扩展了当前求解方程的范式。通过自校正迭代过程寻求解决方案，新的高效算法可以在表示中保留可管理的术语数量，同时保持组件的功能形式和所需的准确性。该项目的目标是设计、测试和实现这样一种归约算法，并将其应用于解决当前方法无法解决的几个多维问题。现代科学中的许多问题都需要计算多元解决方案，而一个主要挑战是开发表示和算法来获得它们，同时避免维数灾难。所提出的工作开发了一种函数微积分，通过基于三种类型的新颖算法的组合的自校正迭代过程来解决高维问题：（1）函数形式的分离表示作为规避维数诅咒的工具； (2) 单变量函数的高效非线性逼近，以实现分离表示的分量的自适应性； (3) 随机投影，以减少分离表示中的项数，同时保持组件的函数形式和所需的精度。这些自适应算法应该产生具有保证误差范围的准确解决方案，同时需要在问题维度上线性缩放的计算时间。该提案特别强调了量子化学的一个基本问题，即精确计算分子的电子结构。 现代科学和工程中的精确建模需要使用多元函数进行计算，而使此类计算变得可行的任何进展都将显着加速现有的数值方法，或者导致许多目前无法解决的问题的解决。从所提出的算法中受益的科学领域不仅限于量子化学和材料科学，其中理解化学反应和材料特性的能力在很大程度上依赖于高效的数值算法，还包括机器人技术和多组件结构的设计，仅举几例。该提案提供了数值工具来解决许多具有挑战性的科学问题的多元性质。因此，该提案的主题预计将促进跨学科合作并成为研究生论文的一部分。