Hierarchical probing for estimating the trace of the matrix inverse on toroidal lattices

DOI10.1137/120881452zbMATH Open1281.65072arXiv1302.4018OpenAlexW2964321151WikidataQ60153249 ScholiaQ60153249MaRDI QIDQ2870692FDOQ2870692

Authors: Andreas Stathopoulos, Jesse Laeuchli, Kostas Orginos 

Publication date: 21 January 2014

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

Abstract: The standard approach for computing the trace of the inverse of a very large, sparse matrix $A$ is to view the trace as the mean value of matrix quadratures, and use the Monte Carlo algorithm to estimate it. This approach is heavily used in our motivating application of Lattice QCD. Often, the elements of $A^{-1}$ display certain decay properties away from the non zero structure of $A$, but random vectors cannot exploit this induced structure of $A^{-1}$. Probing is a technique that, given a sparsity pattern of $A$, discovers elements of $A$ through matrix-vector multiplications with specially designed vectors. In the case of $A^{-1}$, the pattern is obtained by distance-$k$ coloring of the graph of $A$. For sufficiently large $k$, the method produces accurate trace estimates but the cost of producing the colorings becomes prohibitively expensive. More importantly, it is difficult to search for an optimal $k$ value, since none of the work for prior choices of $k$ can be reused.

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

Recommendations

• Extending Hierarchical Probing for Computing the Trace of Matrix Inverses
• Probing for the Trace Estimation of a Permuted Matrix Inverse Corresponding to a Lattice Displacement
• Extrapolation methods for estimating the trace of the matrix inverse
• Estimating the trace of the matrix inverse by interpolating from the diagonal of an approximate inverse
• Estimating the norms of random circulant and Toeplitz matrices and their inverses
• Estimation for the inverse of the tridiagonal matrices
• Estimation of the inverse elements of a certain class of tridiagonal matrices
• A Hierarchical Representation of the Inverse for Sparse Matrices
• Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions
• scientific article; zbMATH DE number 1924308

zbMATH Keywords

numerical examplesparallel algorithmsparse matrixtoruslattice QCDmatrix-vector multiplicationcomparison of methodsFourier basisMonte Carlo algorithmprobingHadamard vectorstrace of the inverse

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Strong interaction, including quantum chromodynamics (81V05)

Cited In (18)

• Title not available (Why is that?)
• Interpolating log-determinant and trace of the powers of matrix \(\mathbf{A}+ t\mathbf{B}\)
• A Multilevel Approach to Variance Reduction in the Stochastic Estimation of the Trace of a Matrix
• Multigrid deflation for lattice QCD
• Nuclear matrix elements from lattice QCD for electroweak and beyond-standard-model processes
• Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations
• Probing for the Trace Estimation of a Permuted Matrix Inverse Corresponding to a Lattice Displacement
• Extending Hierarchical Probing for Computing the Trace of Matrix Inverses
• Variance reduction with practical all-to-all lattice propagators
• A probing method for computing the diagonal of a matrix inverse.
• Disconnected loop subtraction methods in lattice QCD
• Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions
• Analysis of stochastic probing methods for estimating the trace of functions of sparse symmetric matrices
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• Stochastic estimates for the trace of functions of matrices via Hadamard matrices
• Estimating the trace of the matrix inverse by interpolating from the diagonal of an approximate inverse
• Deflation as a method of variance reduction for estimating the trace of a matrix inverse
• How accurately should I compute implicit matrix-vector products when applying the Hutchinson trace estimator?

Uses Software

• SelInv

This page was built for publication: Hierarchical probing for estimating the trace of the matrix inverse on toroidal lattices

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