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

DOI10.1137/21M1422495zbMATH Open1495.15006arXiv2106.01275OpenAlexW3167133044MaRDI QIDQ5099863FDOQ5099863

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

Publication date: 26 August 2022

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

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.

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

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

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)

Cites Work

• PRIMME
• SelInv---An Algorithm for Selected Inversion of a Sparse Symmetric Matrix
• Computing the Continuous Discretely
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
• Title not available (Why is that?)
• A probing method for computing the diagonal of a matrix inverse
• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
• Title not available (Why is that?)
• An estimator for the diagonal of a matrix
• Hierarchical probing for estimating the trace of the matrix inverse on toroidal lattices
• Improved Scaling for Quantum Monte Carlo on Insulators
• Title not available (Why is that?)
• On Computing Inverse Entries of a Sparse Matrix in an Out-of-Core Environment
• Effective noise reduction techniques for disconnected loops in lattice QCD
• Multigrid deflation for lattice QCD
• Deflation as a Method of Variance Reduction for Estimating the Trace of a Matrix Inverse
• Computing trace of function of matrix
• On Various Algorithms for Estimating the Chromatic Number of a Graph
• Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions
• A multigrid accelerated eigensolver for the Hermitian Wilson-Dirac operator in lattice QCD
• Extending Hierarchical Probing for Computing the Trace of Matrix Inverses

Cited In (2)

• Hierarchical probing for estimating the trace of the matrix inverse on toroidal lattices
• Extending Hierarchical Probing for Computing the Trace of Matrix Inverses

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)