Tensor product numerical methods for high-dimensional problems in probability and quantum calculations

概率和量子计算中高维问题的张量积数值方法

• 批准号: EP/M019004/1
• 负责人: Sergey Dolgov
• 金额: $ 28.12万
• 依托单位: University of Bath
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2016
• 资助国家: 英国
• 起止时间: 2016 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FM019004%2F1
• 关键词: Tensor; product; numerical; methods; dimensional

The tremendous complexity of contemporary technological processes induces a extremely high complexity in mathematical models that describe the physical laws of nature, but nonetheless computer simulations are indispensable for accurate quantitative predictions. Innovative models accounting for quantum effects or uncertain information are high-dimensional and hugely expensive - the lifetime of the Universe would not be enough to solve them by classical means. However, many such problems exhibit structure that if exploited can significantly reduce the computational effort. This project aims to break the complexity of high-dimensional models, and open them for routine use in computer simulation. This will be accomplished by the development of new methods that reveal hidden low-dimensional structures using classic mathematical methods, such as separation of variables and singular value decomposition. I will substantially extend the power of these methods, and apply them across a variety of important physical problems.We know that our world is three-dimensional, so how do high-dimensional models arise? Imagine a bacterium in a lake. At any point in time it makes a move in an arbitrary direction. We cannot say definitely that the bacterium will reach a certain region in the lake and infect a plant growing there, but we can calculate the probability that this will happen. If we would like to consider all plants growing in a lake together we will have to store in computer memory the probability values for all plants. If we describe the behaviour of two bacteria at the same time, we will square the consumption of computer memory, since independent of the position of the first bacterium the second one still has the freedom to go anywhere. With an increasing number of bacteria, the amount of data explodes exponentially and quickly exhausts any reasonable memory. So the term "dimension" refers to the number of bacteria, and is naturally very high.However, if bacteria move independently it is enough to store probability values just for one of them: the joint probability of the overall situation in the lake is then simply the product of the marginal probabilities. In reality, the bacteria will interact to some extent with near-by bacteria and will be influenced by the ambient flow in the lake. However, it is highly unlikely that a bacterium on one side of the lake will be affected by bacteria at the other. So the volume of data that effectively approximates the whole system will be many orders of magnitude smaller than the total number of degrees of freedom. The concept of high dimension in this example is in fact ubiquitous. An airplane, experiencing a fluctuating load on its wings, quantum effects unravelled by a magnetic resonance spectrometer, circadian rhythms or virus replication - all these phenomena are described by high-dimensional models. I will design methods that set new levels of prediction accuracy in these existing models, in particular such vital problems as subsurface flows of pollutants in an uncertain medium or stochastic virus dynamics, and extend the class of problems that can be tackled.The new methods I am going to develop combine a range of mathematical techniques. The tensor product concept is a powerful data compression method, but it is in fact nothing more than an immediate generalisation of the separation of variable concept for continuous functions that can be accurately computed via the singular value decomposition. The workhorses in the tensor product framework are alternating optimisation algorithms. Their convergence can be substantially enhanced by employing ideas from classical Krylov iterative methods for matrix equations. I will extend tensor product methods further, and embody them in publicly available software with transparent user interfaces to popular scientific packages in order to encourage other researchers to try the new methodology in real-life problems.

当代技术过程的巨大复杂性导致了描述自然物理定律的数学模型的高度复杂性，但计算机模拟对于准确的定量预测是不可或缺的。解释量子效应或不确定信息的创新模型是高维的，而且非常昂贵--宇宙的寿命不足以用经典方法解决它们。然而，许多这样的问题表现出的结构，如果利用可以显着减少计算工作量。该项目旨在打破高维模型的复杂性，并将其开放用于计算机仿真中的日常使用。这将通过开发新的方法来实现，这些方法使用经典的数学方法来揭示隐藏的低维结构，例如分离变量和奇异值分解。我将大大扩展这些方法的能力，并将它们应用于各种重要的物理问题。我们知道我们的世界是三维的，那么高维模型是如何产生的呢？想象一个细菌在湖里。在任何时间点，它都向任意方向移动。我们不能肯定地说细菌会到达湖中的某个区域并感染生长在那里的植物，但我们可以计算出这种情况发生的概率。如果我们想考虑所有的植物生长在一个湖泊一起，我们将不得不存储在计算机内存中的概率值为所有植物。如果我们同时描述两种细菌的行为，我们将使计算机内存的消耗量相等，因为与第一种细菌的位置无关，第二种细菌仍然可以自由地去任何地方。随着细菌数量的增加，数据量呈指数级爆炸，并迅速耗尽任何合理的内存。因此，“维数”一词指的是细菌的数量，自然是非常高的。然而，如果细菌独立移动，那么只存储其中一个的概率值就足够了：那么湖泊中整体情况的联合概率就只是边际概率的乘积。实际上，细菌会在一定程度上与附近的细菌相互作用，并会受到湖中环境流量的影响。然而，湖的一边的细菌不太可能受到另一边细菌的影响。因此，有效地近似整个系统的数据量将比自由度的总数小许多数量级。这个例子中的高维概念实际上是无处不在的。一架飞机，在其机翼上经历波动的负载，磁共振光谱仪揭示的量子效应，昼夜节律或病毒复制-所有这些现象都由高维模型描述。我将设计一些方法，在现有的模型中设定新的预测精度水平，特别是一些重要的问题，如污染物在不确定介质中的地下流动或随机病毒动力学，并扩展可以解决的问题类别。张量积概念是一种强大的数据压缩方法，但它实际上只不过是对连续函数的变量分离概念的直接概括，可以通过奇异值分解精确计算。张量积框架中的主力是交替优化算法。他们的收敛性可以大大提高采用经典Krylov迭代方法的思想矩阵方程。我将进一步扩展张量积方法，并将其体现在公开可用的软件中，这些软件具有透明的用户界面，以鼓励其他研究人员在现实生活中尝试新的方法。

项目成果

Fast iterative solution of the Bethe-Salpeter eigenvalue problem using low-rank and QTT tensor approximation

• DOI: 10.1016/j.jcp.2016.12.047
• 发表时间: 2016-02
• 期刊: J. Comput. Phys.
• 作者: P. Benner;S. Dolgov;V. Khoromskaia;B. Khoromskij

Parallel cross interpolation for high-precision calculation of high-dimensional integrals

• DOI: 10.1016/j.cpc.2019.106869
• 发表时间: 2020-01-01
• 期刊: COMPUTER PHYSICS COMMUNICATIONS
• 影响因子: 6.3
• 作者: Dolgov, Sergey;Savostyanov, Dmitry
• 通讯作者: Savostyanov, Dmitry

Tensor Decomposition Methods for High-dimensional Hamilton--Jacobi--Bellman Equations

高维Hamilton--Jacobi--Bellman方程的张量分解方法

• DOI: 10.1137/19m1305136
• 发表时间: 2021
• 期刊: SIAM Journal on Scientific Computing
• 影响因子: 3.1
• 作者: Dolgov S

A Tensor Decomposition Algorithm for Large ODEs with Conservation Laws

• DOI: 10.1515/cmam-2018-0023
• 发表时间: 2019-01-01
• 期刊: COMPUTATIONAL METHODS IN APPLIED MATHEMATICS
• 影响因子: 1.3
• 作者: Dolgov, Sergey, V

A Hybrid Alternating Least Squares--TT-Cross Algorithm for Parametric PDEs

混合交替最小二乘法--参数偏微分方程的TT交叉算法

• DOI: 10.1137/17m1138881
• 发表时间: 2019
• 期刊: SIAM/ASA Journal on Uncertainty Quantification
• 作者: Dolgov S