Numerical Linear Algebra for Scale-Free Graph Matrices
Due to a campus closure on 9/13/13, this talk was canceled.
Geoff Sanders, Post-Doctoral Researcher
Center for Applied Scientific Computing, Lawrence Livermore National Laboratory
Date and time:
Friday, September 13, 2013 - 3:00pm
Location:
ECCR 245
Abstract:
A scale-free graph is characterized by having vertices with a degree distribution that follows a power law. Clustering, ranking, and measuring similarity of vertices on scale-free graphs are all tasks that network scientists often perform. We describe a few network calculations that are obtained by solving linear systems, eigensystems, nonlinear constrained optimization problems, and tensor decompositions involving matrices (or tensors) whose sparsity structure is related to an underlying scale-free graph. In each of these settings, linear solves and eigensolves are often fundamental calculations performed as subroutines within the larger iterative solution process. For many large systems of interest, classical iterative solvers (such as conjugate gradient, Lanczos) converge with prohibitively slow rates, due to ill-conditioned matrices and small spectral gap ratios. Scalable preconditioners for this class of problem are of considerable research interest.
We consider constructing algebraic multigrid (AMG) preconditioners, which make use of coarse approximation of eigenspaces to accelerate convergence. We discuss several interesting properties the eigenvectors of scale-free graphs have that are not present in mesh-like graphs. As a first example, such graphs often have a large number of locally supported eigenvectors (LSEVs), eigenvectors that are each nonzero only in a small, connected region. Another common related property is that eigenvectors in a matrix’s near-nullspace are essentially local, having significant magnitude in a very small region of the graph and rapidly decaying away from this region. We discuss how these properties can be taken advantage of to coarsen with high spectral accuracy. A third property such graphs often have is a tree-like periphery, where highly aggressive coarsening routines based on Schur-complements result are successful. We give some preliminary results obtained by implementing these routines in Livne’s Lean Algebraic Multigrid (LAMG) solver.
Additionally, the properties of eigenspaces of common graph-associated matrices are important for understanding how the quality of a numerical solution relates to the quality of the data mining task, loosely analogous to the relationship between discretization error and optimal convergence tolerances in numerical solutions to partial differential equations. This motivates further research regarding eigenspaces of graph-associated matrices. We prove maximum principles and decay rates for eigenvectors associated with adjacency and modularity matrices and discuss the impact of these results.