Sampling Algorithms in Numerical Linear Algebra and their Applications
Tuesday, November 10, 2015 - 1:25pm - 2:25pm
A well-known technique used in statistical methods is to estimate the trace of some matrix via sampling. For example, one can estimate the trace of exp(A) by computing w=exp(A)v for many vectors v, and the mean of the inner products of v and w will yield an approximation of the trace under some conditions. This basic technique has found uses in areas as diverse as quantum physics, statistics, and numerical linear algebra. We will first discuss the extension of this idea to the problem of estimating the diagonal of the inverse of a matrix which has applications in solving Dysorn's equation in Dynamical Mean Field Theory (DMFT). Then we will consider other problems including estimating eigenvalue counts in given intervals, computing spectral densities, and finally the somewhat related problem of developing low-rank approximate inverse preconditioners.