W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Jessie Laeuchli, Computer Science - Ph.D. Defense
January 22, 2016
2pm - 4pm
Abstract:
Many applications such as path integral evaluation in Lattice Quantum Chromodynamics (LQCD), variance estimation of least square solutions and spline fits, and centrality measures in network analysis, require computing the diagonal of a function of a matrix, diag(f(A)) where A is sparse matrix, and f is some function. Unfortunately, when A is large, this can be computationally prohibitive. Because of this, many applications resort to Monte Carlo methods. However, Monte Carlo methods tend to 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 weight connection in f(A). To determine the distances between nodes, probing forms A^k. Coloring the graph of this matrix will group nodes together that have a high distance between them, and thus a small connection in f(A). This enables the construction of certain vectors, called probing vectors, that can capture the diagonals of f(A).
One drawback of probing is in many cases too expensive to compute and store A^k for the 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 a 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.
If we do not have knowledge of the intrinsic geometry of the matrix, we propose two new classes of methods that improve on the results of probing. One method seeks to determine structural properties of the matrix $f(A)$ by obtaining random samples of the columns of f(A). The other method leverages ideas arising from similar problems in graph partitioning, and makes use of the eigenvectors of f(A) to form effective hierarchical colorings. Our methods have thus far seen successful use in computational physics, where they have been applied to compute constants arising in LQCD. We hope that the refinements presented in this work will enable interesting applications in many other fields.
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 (LQCD), variance estimation of least square solutions and spline fits, and centrality measures in network analysis, require computing the diagonal of a function of a matrix, diag(f(A)) where A is sparse matrix, and f is some function. Unfortunately, when A is large, this can be computationally prohibitive. Because of this, many applications resort to Monte Carlo methods. However, Monte Carlo methods tend to 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 weight connection in f(A). To determine the distances between nodes, probing forms A^k. Coloring the graph of this matrix will group nodes together that have a high distance between them, and thus a small connection in f(A). This enables the construction of certain vectors, called probing vectors, that can capture the diagonals of f(A).
One drawback of probing is in many cases too expensive to compute and store A^k for the 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 a 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.
If we do not have knowledge of the intrinsic geometry of the matrix, we propose two new classes of methods that improve on the results of probing. One method seeks to determine structural properties of the matrix $f(A)$ by obtaining random samples of the columns of f(A). The other method leverages ideas arising from similar problems in graph partitioning, and makes use of the eigenvectors of f(A) to form effective hierarchical colorings. Our methods have thus far seen successful use in computational physics, where they have been applied to compute constants arising in LQCD. We hope that the refinements presented in this work will enable interesting applications in many other fields.
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.
Contact
[[vlthompsondopp]]