AF: Small: Algorithms for computing aggregate functions of matrices with applications to Lattice QCD

AF：小型：计算矩阵聚合函数的算法及其在莱迪思 QCD 中的应用

• 批准号: 1218349
• 负责人: Andreas Stathopoulos
• 金额: $ 40万
• 依托单位: College of William and Mary
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1218349&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; computing; aggregate

One of the most computationally challenging tasks in Numerical Linear Algebra (NLA) is the estimation of the trace or the determinant of functions of matrices. The computational difficulty arises for very large matrices where the computation of the entire spectrum is infeasible. Traditionally, this problem is approached through stochastic techniques, such as Monte Carlo, where each step involves the solution of a linear system of equations. Deterministic techniques could provide approximations much faster but introduce bias in the result. This research will employ a combination of these techniques. Deterministic techniques involve novel uses of traditional NLA tools such as low rank approximations, deflation, and preconditioners, not only for speeding the solution of linear systems but also for reducing the variance of the stochastic process. The team plans to use Hadamard vectors, which are popular in coding theory, with an ordering induced by hierarchical graph-coloring, to produce a deterministic sequence of sampling vectors for Monte Carlo that exploits the structure of the matrix.Although most of these techniques address the general NLA problem, the motivating application is lattice quantum chromodynamics (LQCD). The goal of LQCD is to calculate the properties, structure, and interactions of hadrons,the basic constituents of matter. Computation of observables in LQCD entails averaging of correlation functions over an ensemble of gauge fields. These correlation functions often require the trace of the inverse of a large sparse matrix, or the ratio of determinants of two such matrices. It is increasingly clear that there is an opportunity for real gains by harnessing the synergy between randomized and deterministic techniques.Based on such an approach, this research will advance the current state-of-the-art in NLA, while transforming some of the standard computational practices in LQCD. It will also be useful in other disciplines, as the problem is common in many statistical applications, in data mining, in uncertainty quantification, as well as in quantum physics applications such as quantum Monte Carlo.

数值线性代数 (NLA) 中最具计算挑战性的任务之一是估计矩阵函数的迹或行列式。对于非常大的矩阵会出现计算困难，其中整个谱的计算是不可行的。传统上，这个问题是通过随机技术来解决的，例如蒙特卡罗，其中每个步骤都涉及线性方程组的求解。确定性技术可以更快地提供近似值，但会在结果中引入偏差。这项研究将结合使用这些技术。确定性技术涉及传统 NLA 工具的新颖用途，例如低秩近似、紧缩和预处理器，不仅可以加快线性系统的求解速度，还可以减少随机过程的方差。该团队计划使用编码理论中流行的 Hadamard 向量以及由分层图着色引起的排序，为利用矩阵结构的蒙特卡罗生成确定性的采样向量序列。虽然这些技术中的大多数都解决了一般的 NLA 问题，但激发应用的是晶格量子色动力学 (LQCD)。 LQCD 的目标是计算强子（物质的基本组成部分）的性质、结构和相互作用。 LQCD 中可观测量的计算需要对规范场集合上的相关函数进行平均。这些相关函数通常需要大型稀疏矩阵的逆矩阵的迹，或者两个此类矩阵的行列式之比。越来越明显的是，通过利用随机技术和确定性技术之间的协同作用，有机会获得真正的收益。基于这种方法，这项研究将推进 NLA 的当前最先进水平，同时改变 LQCD 中的一些标准计算实践。它在其他学科中也很有用，因为这个问题在许多统计应用、数据挖掘、不确定性量化以及量子物理应用（例如量子蒙特卡罗）中都很常见。