Probing for the Trace Estimation of a Permuted Matrix Inverse Corresponding to a Lattice Displacement

DOI10.1137/21M1422495MaRDI QIDQ5099863zbMATH OpenOpenAlexFDO

Authors Heather M. Switzer, Andreas Stathopoulos, Eloy Romero, Jesse Laeuchli, Kostas Orginos

Publication date 26 August 2022

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.01275

zbMATH Keywords

latticesparse matrixtoruslattice QCDprobingtrace of inverse

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Computational methods for sparse matrices (65F50) Random matrices (algebraic aspects) (15B52) Graph theory (including graph drawing) in computer science (68R10) Determinants, permanents, traces, other special matrix functions (15A15) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Strong interaction, including quantum chromodynamics (81V05)

Abstract: In this work, we study probing for the more general problem of computing the trace of a permutation of $A^{-1}$, say $P{A}^{-1}$. 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{A}^{-1}$ where $P$ is the permutation relating to some displacement $vecp$ in one or more dimensions. We focus on a single dimension displacement ($p$) but our methods are general. We show that probing on $A^k$ or $(PA{)}^k$ do not annihilate the largest magnitude elements. To resolve this issue, our displacement-based probing works on $P{A}^k$ 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.

Recommendations

• Hierarchical probing for estimating the trace of the matrix inverse on toroidal lattices
• Estimating the trace of the matrix inverse by interpolating from the diagonal of an approximate inverse
• Extrapolation methods for estimating the trace of the matrix inverse
• Extending Hierarchical Probing for Computing the Trace of Matrix Inverses
• Estimation for the inverse of the tridiagonal matrices
• Estimation of the inverse elements of a certain class of tridiagonal matrices
• The pseudoinverse of the Laplacian matrix: asymptotic behavior of its trace
• The trace invariant and matrix inversion
• scientific article; zbMATH DE number 1924308
• Displacement Rank of Generalized Inverses of Persymmetric Matrices

Cites work

• scientific article; zbMATH DE number 3976197 (Why is no real title available?)
• scientific article; zbMATH DE number 1226426 (Why is no real title available?)
• A multigrid accelerated eigensolver for the Hermitian Wilson-Dirac operator in lattice QCD
• A probing method for computing the diagonal of a matrix inverse.
• A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
• An estimator for the diagonal of a matrix
• Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions
• Computing the Continuous Discretely
• Computing trace of function of matrix
• Deflation as a method of variance reduction for estimating the trace of a matrix inverse
• Effective noise reduction techniques for disconnected loops in lattice QCD
• Extending Hierarchical Probing for Computing the Trace of Matrix Inverses
• Hierarchical probing for estimating the trace of the matrix inverse on toroidal lattices
• Improved scaling for quantum Monte Carlo on insulators
• Multigrid deflation for lattice QCD
• Noise methods for flavor singlet quantities
• On Various Algorithms for Estimating the Chromatic Number of a Graph
• On computing inverse entries of a sparse matrix in an out-of-core environment
• PRIMME: preconditioned iterative multimethod eigensolver -- methods and software description
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• SelInv---An Algorithm for Selected Inversion of a Sparse Symmetric Matrix
• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives

Cited in

(3)

• Extending Hierarchical Probing for Computing the Trace of Matrix Inverses
• Deflation as a method of variance reduction for estimating the trace of a matrix inverse
• Hierarchical probing for estimating the trace of the matrix inverse on toroidal lattices

This page was built for publication: Probing for the Trace Estimation of a Permuted Matrix Inverse Corresponding to a Lattice Displacement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5099863)