One of the most computationally challenging tasks in Numerical Linear Algebra (NLA) is the estimation of the trace or the determinant of functions of matrices. The computational difficulty arises for very large matrices where the computation of the entire spectrum is infeasible. Traditionally, this problem is approached through stochastic techniques, such as Monte Carlo, where each step involves the solution of a linear system of equations. Deterministic techniques could provide approximations much faster but introduce bias in the result. This research will employ a combination of these techniques. Deterministic techniques involve novel uses of traditional NLA tools such as low rank approximations, deflation, and preconditioners, not only for speeding the solution of linear systems but also for reducing the variance of the stochastic process. The team plans to use Hadamard vectors, which are popular in coding theory, with an ordering induced by hierarchical graph-coloring, to produce a deterministic sequence of sampling vectors for Monte Carlo that exploits the structure of the matrix.
Although most of these techniques address the general NLA problem, the motivating application is lattice quantum chromodynamics (LQCD). The goal of LQCD is to calculate the properties, structure, and interactions of hadrons, the basic constituents of matter. Computation of observables in LQCD entails averaging of correlation functions over an ensemble of gauge fields. These correlation functions often require the trace of the inverse of a large sparse matrix, or the ratio of determinants of two such matrices.
It is increasingly clear that there is an opportunity for real gains by harnessing the synergy between randomized and deterministic techniques. Based on such an approach, this research will advance the current state-of-the-art in NLA, while transforming some of the standard computational practices in LQCD. It will also be useful in other disciplines, as the problem is common in many statistical applications, in data mining, in uncertainty quantification, as well as in quantum physics applications such as quantum Monte Carlo.
