W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Jesse H. Laeuchli - Dissertation Defense - Computer Science
December 16, 2014
10am - 11:45am
Many applications such as physics, statistics, and network analysis, require computing diag(f(A)) where A is sparse matrix, and f is some function.
Unfortunately, where 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 expensive Monte Carlo methods to estimate these values. Unfortunately, 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. In probing, some polynomial of the matrix A, p_n(A), is chosen, and used to estimate the structure of f(A). This structure is then colored. The elements of the matrix are reordered so that nodes that share a color are adjacent to each other. Since they have no connections (otherwise they would not share a color), a block diagonal zero structure appears, allowing for the recovery of the diagonal elements by the creation of probing vectors of all ones for elements which share a color, and zeros elsewhere. Unfortunately in many cases p_n(A) will not converge fast enough to f(A) to give a good estimate of its structure. An additional drawback is that the set of probing vectors required for p_n(A) is unlikely to be a subset of the probing vectors of p_{n+1)(A). This means that if additional 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 make use of our knowledge of the geometry of the lattice to quickly create hierarchical colorings for the graph of A. A hierarchical coloring is one in which new colors are created by splitting groups of nodes sharing a coloring into new blocks of colors. 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. Our method fully solves the case where the dimensions of the lattices are powers of 2, and we propose a method to extend this approach to arbitrary lattices.
For case of general matrices we propose a new approach, which we term inverse probing. We combine several different methods for directly estimating the structure of f(A). First, several columns of f(A) are obtained, by computing x=f(a)e_i. We can then form an approximation to the structure of f(A) by computing x*x^T. Additionally, while we are computing these columns, some portion of the spectrum of f(A) will be available as a byproduct. We also use these columns to obtain statistical information about the off-diagonals of f(A). Our experiments indicate that by combining all this information together, we can obtain significant improvements over probing.
Bio:
Jesse Laeuchli is a third year Ph.D. student in the Computer Science Department. He is working under the direction of Andreas Stathopolous, 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 and Mary, Jesse received his M.S. from Texas A&M, and his B.S. from The University of Notre Dame.
Unfortunately, where 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 expensive Monte Carlo methods to estimate these values. Unfortunately, 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. In probing, some polynomial of the matrix A, p_n(A), is chosen, and used to estimate the structure of f(A). This structure is then colored. The elements of the matrix are reordered so that nodes that share a color are adjacent to each other. Since they have no connections (otherwise they would not share a color), a block diagonal zero structure appears, allowing for the recovery of the diagonal elements by the creation of probing vectors of all ones for elements which share a color, and zeros elsewhere. Unfortunately in many cases p_n(A) will not converge fast enough to f(A) to give a good estimate of its structure. An additional drawback is that the set of probing vectors required for p_n(A) is unlikely to be a subset of the probing vectors of p_{n+1)(A). This means that if additional 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 make use of our knowledge of the geometry of the lattice to quickly create hierarchical colorings for the graph of A. A hierarchical coloring is one in which new colors are created by splitting groups of nodes sharing a coloring into new blocks of colors. 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. Our method fully solves the case where the dimensions of the lattices are powers of 2, and we propose a method to extend this approach to arbitrary lattices.
For case of general matrices we propose a new approach, which we term inverse probing. We combine several different methods for directly estimating the structure of f(A). First, several columns of f(A) are obtained, by computing x=f(a)e_i. We can then form an approximation to the structure of f(A) by computing x*x^T. Additionally, while we are computing these columns, some portion of the spectrum of f(A) will be available as a byproduct. We also use these columns to obtain statistical information about the off-diagonals of f(A). Our experiments indicate that by combining all this information together, we can obtain significant improvements over probing.
Bio:
Jesse Laeuchli is a third year Ph.D. student in the Computer Science Department. He is working under the direction of Andreas Stathopolous, 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 and Mary, Jesse received his M.S. from Texas A&M, and his B.S. from The University of Notre Dame.
Contact
[[vlthompsondopp]]