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

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

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.