Monday, November 11, 2013
Applied Mathematics Colloquium
Sampling Algorithms in Numerical Linear Algebra and Their Application
Yousef Saad, Computer Science and Engineering, University of Minnesota
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 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 Dyson'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.