File(s) under permanent embargo

Extending Hierarchical Probing for Computing the Trace of Matrix Inverses

journal contribution
posted on 2020-01-01, 00:00 authored by Jesse LaeuchliJesse Laeuchli, Andreas Stathopoulos
We present extensions to hierarchical probing, a method developed in [A. Stathopoulos, J. Laeuchli, and K. Orginos, SIAM J. Sci. Comput., 35 (2013), pp. S299--S322] to reduce the variance of the Monte Carlo estimation of the trace or the diagonal of the inverse of a large, sparse matrix. In that context, probing is a method to determine the largest-in-magnitude elements of the matrix inverse and then annihilate their contributions to the variance by solving linear systems with appropriate probing vectors. It typically involves coloring the graph of $A^n$, since this matches the sparsity structure of a polynomial approximation to $A^{-1}$. This is equivalent to distance-$n$ coloring of $A$, i.e., determining which nodes are connected to one other at distance $ leq n$. For matrices that display a Green's function decay, $n$ is small, which reduces the number of linear systems to be solved. Our hierarchical probing method was developed for matrices with a lattice structure, where distance-$n$ coloring and the generation of probing vectors can be performed far more efficiently and in a way so that earlier vectors are subsets of vectors generated later in the process, meaning that it is simple to continue probing if additional accuracy is needed. However, this method worked only on lattices with dimension lengths that were powers of two. In this paper we extend the method to work on lattices of arbitrary dimension lengths, which is theoretically more challenging. Additionally, we expand the idea to a multilevel, hierarchical probing heuristic for matrices with any undirected graph structure that matches the performance of classical probing but with tractable memory requirements.

Read More:



SIAM Journal on Scientific Computing






A1459 - A1485


Society for Industrial and Applied Mathematics


Philadelphia, Pa.







Publication classification

C1 Refereed article in a scholarly journal