A Multilevel Approach to Variance Reduction in the Stochastic Estimation of the Trace of a Matrix

DOI10.1137/21M1441894OpenAlexW3195958026MaRDI QIDQ5097607

Unnamed Author, Mostafa Nasr Khalil, Andreas Frommer

Publication date: 25 August 2022

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

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

zbMATH Keywords

tracesparse matricesalgebraic multigridvariance reductionmultilevel Monte CarloHutchinson's method

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Determinants, permanents, traces, other special matrix functions (15A15) Numerical computation of matrix exponential and similar matrix functions (65F60)

Uses Software

• PyAMG
• Hutch++

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Variance reduction with practical all-to-all lattice propagators
• Low-energy couplings of QCD from topological zero-mode wave functions
• Multigrid deflation for lattice QCD
• Improved bounds on sample size for implicit matrix trace estimators
• Towards algebraic multigrid for elliptic problems of second order
• Shifted extended global Lanczos processes for trace estimation with application to network analysis
• A multilevel approach to stochastic trace estimation
• An estimator for the diagonal of a matrix
• On randomized trace estimates for indefinite matrices with an application to determinants
• Disconnected loop subtraction methods in lattice QCD
• Approximating Spectral Densities of Large Matrices
• Hierarchical Probing for Estimating the Trace of the Matrix Inverse on Toroidal Lattices
• Multilevel Monte Carlo Methods
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• Network Properties Revealed through Matrix Functions
• Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions
• Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter
• A posteriori error estimate for computing tr(f(A)) by using the Lanczos method
• Fast Estimation of $tr(f(A))$ via Stochastic Lanczos Quadrature
• Gaussian Markov Random Fields
• A probing method for computing the diagonal of a matrix inverse
• Extending Hierarchical Probing for Computing the Trace of Matrix Inverses
• Adaptive Smoothed Aggregation ($\alpha$SA) Multigrid
• Approximating Spectral Sums of Large-Scale Matrices using Stochastic Chebyshev Approximations
• Functions of Matrices
• Gauge Invariance and Mass. II
• Deflation as a Method of Variance Reduction for Estimating the Trace of a Matrix Inverse
• A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines

This page was built for publication: A Multilevel Approach to Variance Reduction in the Stochastic Estimation of the Trace of a Matrix