Jefferson Lab > CIO > IR
Privacy and Security Notice


Publication Information

Title Probing For Trace Estimation of a Permuted Matrix Inverse Corresponding to a Lattice Displacement
Authors Heather Switzer, Andreas Stathopoulos, Eloy Romero, Jesse Laeuchli, Konstantinos Orginos
JLAB number JLAB-CST-21-3500
LANL number arXiv:2106.01275
Other number DOE/OR/23177-5320
Document Type(s) (Journal Article) 
Associated with EIC: No
Supported by Jefferson Lab LDRD Funding: No
Funding Source: Other
Other Funding:SURA
Exascale Computing Project

Compiled for SIAM Journal on Scientfic Computing
Volume 44
Issue 4
Page(s) B1096-B1121
Publication Abstract: Probing is a general technique that is used to reduce the variance of the Hutchinson stochastic estimator for the trace of the inverse of a large, sparse matrix A. The variance of the estimator is the sum of the squares of the off-diagonal elements of inv(A) . Therefore, this technique computes probing vectors that when used in the estimator they annihilate the largest off-diagonal elements. For matrices that display decay of the magnitude of |A^{-1}_{ ij}| with the graph distance between nodes i and j, this is achieved through graph coloring of increasing powers A^p. Equivalently, when a matrix stems from a lattice discretization, it is computationally beneficial to find a distance-p coloring of the lattice. In [23] a hierarchical coloring was proposed so that p can be increased at runtime as needed without discarding previous work. In this work, we study probing for the more general problem of computing the trace of a permutation of inv(A), say P*inv(A) . The motivation comes from Lattice QCD where we need to construct "disconnected diagrams" to extract flavor-separated Generalized Parton functions. In Lattice QCD, where the matrix has a 4D toroidal lattice structure, these non-local operators correspond to a P*inv(A) where P is the permutation relating to some displacement k in one or more dimensions. We focus on a single dimension displacement (k) but our methods are general. We show that probing on A^p or (PA)^p do not annihilate the largest magnitude elements. To resolve this issue, our displacement-based probing works on PA^p using a new coloring scheme that works directly on appropriately displaced neighborhoods on the lattice. We prove lower bounds on the number of colors needed, and study the effect of this scheme on variance reduction, both theoretically and experimentally on a real-world Lattice QCD calculation. We achieve orders of magnitude speedup over the unprobed or the naively probed methods.
Experiment Numbers: other
Group: Scientific Computing
Document: pdf
Accepted Manuscript: 2106.01275.pdf
Supporting Documents:
Supporting Datasets: