Deflation as a Method of Variance Reduction for Estimating the Trace of a Matrix Inverse

Abstract

Many fields require computing the trace of the inverse of a large, sparse matrix. The typical method used for such computations is the Hutchinson method which is a Monte Carlo (MC) averaging over matrix quadratures. To improve its convergence, several variance reductions techniques have been proposed. In this paper, we study the effects of deflating the near null singular value space. We make two main contributions. First, we analyze the variance of the Hutchinson method as a function of the deflated singular values and vectors. Although this provides good intuition in general, by assuming additionally that the singular vectors are random unitary matrices, we arrive at concise formulas for the deflated variance that include only the variance and mean of the singular values. We make the remarkable observation that deflation may increase variance for Hermitian matrices but not for non-Hermitian ones. This is a rare, if not unique, property where non-Hermitian matrices outperform Hermitian ones. The theory can be used as a model for predicting the benefits of deflation. Second, we use deflation in the context of a large scale application of "disconnected diagrams" in Lattice QCD. On lattices, Hierarchical Probing (HP) has previously provided an order of magnitude of variance reduction over MC by removing "error" from neighboring nodes of increasing distance in the lattice. Although deflation used directly on MC yields a limited improvement of 30% in our problem, when combined with HP they reduce variance by a factor of over 60 compared to MC. For this, we pre-computated 1000 smallest singular values of an ill-conditioned matrix of size 25 million. Using PRIMME and a domain-specific Algebraic Multigrid preconditioner, we perform one of the largest eigenvalue computations in Lattice QCD at a fraction of the cost of our trace computation.

21 pages, 24 figures

References in corpus (5)

• Adaptive multigrid algorithm for the lattice Wilson-Dirac operator
• Random phase vector for calculating the trace of a large matrix
• Controlling Excited-State Contamination in Nucleon Matrix Elements
• Deflated Iterative Methods for Linear Equations with Multiple Right-Hand Sides
• Integrals over SU(N)

Cited by in corpus (18)

• Lattice calculation of the short and intermediate time-distance hadronic vacuum polarization contributions to the muon magnetic moment using twisted-mass fermions
• Complete flavor decomposition of the spin and momentum fraction of the proton using lattice QCD simulations at physical pion mass
• Proton and neutron electromagnetic form factors from lattice QCD
• Nuclear matrix elements from lattice QCD for electroweak and beyond-Standard-Model processes
• Nuclear modification of scalar, axial and tensor charges from lattice QCD
• XTrace: Making the most of every sample in stochastic trace estimation
• Mixed Stochastic-Deterministic Time-Dependent Density Functional Theory: Application to Stopping Power of Warm Dense Carbon
• Collective charge excitations and the metal-insulator transition in the square lattice Hubbard-Coulomb model
• Excited states in nucleon structure calculations
• Krylov-aware stochastic trace estimation
• Multigrid deflation for Lattice QCD
• Pion Transition Form Factor from Twisted-Mass Lattice QCD and the Hadronic Light-by-Light ${\pi }^0$-pole Contribution to the Muon $g-2$
• Quark and gluon momentum fractions in the pion from $N_f=2+1+1$ lattice QCD
• Numerical computation of the equilibrium-reduced density matrix for strongly coupled open quantum systems
• Disconnected Loop Subtraction Methods in Lattice QCD
• Quark flavor decomposition of the nucleon axial form factors
• Proton and neutron electromagnetic form factors from lattice QCD in the continuum limit
• Faster randomized partial trace estimation