W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Hierarchical Probing for estimating the diagonal of matrix functions
November 20, 2015
3pm
Title: Hierarchical Probing for estimating the diagonal of matrix functions
Many applications such as path integral evaluation in Lattice Quantum Chromodynamics, variance estimation of least square solutions and spline fits, and centrality measures in network analysis, require computing diag(f(A)) where A is sparse matrix, and f is some function. Unfortunately, when A is large, this can be computationally prohibitive. For example, computing diag(A^{-1}) and diag(exp(A)) directly is often impossible. Because of this, many applications resort to Monte Carlo methods to estimate these values. However, these methods converge slowly, since they do not take into account knowledge of the structure of A.
One method for dealing with this shortcoming is probing. Probing assumes that nodes which have a large distance between them in the graph of A, have only a small connection in f(A). To determine the distances between nodes, probing forms A^k. Coloring the graph of this matrix (equivalent to performing a distance-k coloring of A), will group nodes together that have a high distance between them, and thus a small connection in f(A). This enables the construction of probing vectors to capture the diagonals of f(A). One drawback of probing is in many cases it is too expensive to compute and store an A^k that adequately determines which nodes have a strong connection in f(A). Additionally, it is unlikely that the set of probing vectors required for A^k is a subset of the probing vectors needed for A^{k+1}. This means that if more accuracy in the estimation is required, all previously computed work must be discarded.
In the case where the underlying problem arises from a discretization of a PDE onto a lattice, we can make use of our knowledge of the geometry of the lattice to quickly create hierarchical colorings for the graph of A^k. A hierarchical coloring is one in which colors for A^{k+1} are created by splitting groups of nodes sharing color in A^k. The hierarchical property ensures that the probing vectors used to estimate diag(f(A)) are nested subsets, so if the results are inaccurate the estimate can be improved without discarding the previous work. This approach can be seen to have connections with methods of spectral clustering, which we plan to use to extend the idea in future work
Bio:
Jesse Laeuchli is a Ph.D. student in the Computer Science Department. He is working under the direction of Andreas Stathopoulos, in the area of numerical linear algebra. His research involves bringing together ideas from graph theory, preconditioning, and combinatorics to design new algorithms. Prior to starting his research at William & Mary, Jesse received his M.S. from Texas A&M, and his B.S. from The University of Notre Dame.
Many applications such as path integral evaluation in Lattice Quantum Chromodynamics, variance estimation of least square solutions and spline fits, and centrality measures in network analysis, require computing diag(f(A)) where A is sparse matrix, and f is some function. Unfortunately, when A is large, this can be computationally prohibitive. For example, computing diag(A^{-1}) and diag(exp(A)) directly is often impossible. Because of this, many applications resort to Monte Carlo methods to estimate these values. However, these methods converge slowly, since they do not take into account knowledge of the structure of A.
One method for dealing with this shortcoming is probing. Probing assumes that nodes which have a large distance between them in the graph of A, have only a small connection in f(A). To determine the distances between nodes, probing forms A^k. Coloring the graph of this matrix (equivalent to performing a distance-k coloring of A), will group nodes together that have a high distance between them, and thus a small connection in f(A). This enables the construction of probing vectors to capture the diagonals of f(A). One drawback of probing is in many cases it is too expensive to compute and store an A^k that adequately determines which nodes have a strong connection in f(A). Additionally, it is unlikely that the set of probing vectors required for A^k is a subset of the probing vectors needed for A^{k+1}. This means that if more accuracy in the estimation is required, all previously computed work must be discarded.
In the case where the underlying problem arises from a discretization of a PDE onto a lattice, we can make use of our knowledge of the geometry of the lattice to quickly create hierarchical colorings for the graph of A^k. A hierarchical coloring is one in which colors for A^{k+1} are created by splitting groups of nodes sharing color in A^k. The hierarchical property ensures that the probing vectors used to estimate diag(f(A)) are nested subsets, so if the results are inaccurate the estimate can be improved without discarding the previous work. This approach can be seen to have connections with methods of spectral clustering, which we plan to use to extend the idea in future work
Bio:
Jesse Laeuchli is a Ph.D. student in the Computer Science Department. He is working under the direction of Andreas Stathopoulos, in the area of numerical linear algebra. His research involves bringing together ideas from graph theory, preconditioning, and combinatorics to design new algorithms. Prior to starting his research at William & Mary, Jesse received his M.S. from Texas A&M, and his B.S. from The University of Notre Dame.