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.