Methods for Estimating The Diagonal of Matrix Functions
Methods for Estimating The Diagonal of Matrix Functions
复制标题
矩阵函数对角线的估计方法
DOI：
10.21220/s2cc7x
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Jesse Laeuchli
中科院分区：
文献类型：
--
作者：
Jesse Laeuchli
许多应用，如格子量子色动力学（LQCD）中的路径积分计算，最小二乘解和样条拟合的方差估计，以及网络分析中的中心性度量，都需要计算矩阵Diag（f（A））的函数的对角线，其中A是稀疏矩阵，f是某个函数。不幸的是，当A很大时，这可能在计算上是禁止的。正因为如此，许多应用程序诉诸蒙特卡罗方法。然而，蒙特卡罗方法往往收敛缓慢。处理这个缺点的一个方法是探测。探测假设A的图中具有较大距离的节点在f（A）中只有较小的权重连接。为了确定节点之间的距离，探测形式A。对这个矩阵的图着色将把它们之间具有高距离的节点分组在一起，因此f（A）中的连接很小。这使得能够构造某些向量，称为探测向量，可以捕获f（A）的对角线。探测的一个缺点是，在许多情况下，计算和存储k的A太昂贵，而k足以确定哪些节点在f（A）中具有强连接。另外，A所需的探测向量的集合不太可能是A所需的探测向量的子集。这意味着如果需要更高的估计精度，则必须丢弃所有先前计算的工作。在潜在问题源于将偏微分方程（PDE）离散到格上的情况下，我们可以利用我们对格的几何知识来快速创建A的图的分层着色。分层着色是通过分割A中共享颜色的节点组来创建A的颜色的着色。分层属性确保用于估计Diag（f（A））的探测向量是嵌套子集，因此如果结果不准确，则可以在不丢弃先前工作的情况下改进估计。如果我们没有知识的矩阵的内在几何，我们提出了两类新的方法，提高探测的结果。一种方法试图通过获得f（A）的列的随机样本来确定矩阵f（A）的结构性质。另一种方法利用了图划分中类似问题的思想，并利用f（A）的特征向量来形成有效的分层着色。到目前为止，我们的方法已经成功地应用于计算物理学，在那里它们已被应用于计算LQCD中产生的可观测量。我们希望这项工作中提出的改进能够在许多其他领域实现有趣的应用。
Many applications such as path integral evaluation in Lattice Quantum Chromodynamics (LQCD), variance estimation of least square solutions and spline fits, and centrality measures in network analysis, require computing the diagonal of a function of a matrix, Diag(f(A)) where A is sparse matrix, and f is some function. Unfortunately, when A is large, this can be computationally prohibitive. Because of this, many applications resort to Monte Carlo methods. However, Monte Carlo methods tend to converge slowly. One method for dealing with this shortcoming is probing. Probing assumes that nodes that have a large distance between them in the graph of A, have only a small weight connection in f(A). To determine the distances between nodes, probing forms A. Coloring the graph of this matrix will group nodes that have a high distance between them together, and thus a small connection in f(A). This enables the construction of certain vectors, called probing vectors, that can capture the diagonals of f(A). One drawback of probing is in many cases it is too expensive to compute and store A for the k that adequately determines which nodes have a strong connection in f(A). Additionally, it is unlikely that the set of probing vectors required for A is a subset of the probing vectors needed for A. This means that if more accuracy in the estimation is required, all previously computed work must be discarded. In the case where the underlying problem arises from a discretization of a partial differential equation (PDE) onto a lattice, we can make use of our knowledge of the geometry of the lattice to quickly create hierarchical colorings for the graph of A. A hierarchical coloring is one in which colors for A are created by splitting groups of nodes sharing a color in A. The hierarchical property ensures that the probing vectors used to estimate Diag(f(A)) are nested subsets, so if the results are inaccurate the estimate can be improved without discarding the previous work. If we do not have knowledge of the intrinsic geometry of the matrix, we propose two new classes of methods that improve on the results of probing. One method seeks to determine structural properties of the matrix f(A) by obtaining random samples of the columns of f(A). The other method leverages ideas arising from similar problems in graph partitioning, and makes use of the eigenvectors of f(A) to form effective hierarchical colorings. Our methods have thus far seen successful use in computational physics, where they have been applied to compute observables arising in LQCD. We hope that the refinements presented in this work will enable interesting applications in many other fields.