Algebraic Multigrid for Parallel Computing, Systems, and Graphs... oh my!
Tobias Jones
Applied Mathematics, University of Colorado Boulder
Date and time:
Tuesday, April 30, 2013 - 12:00pm
Abstract:
The proposed research contains three main topics:
AMG-DD/RD
In modern large-scale supercomputing applications, Algebraic MultiGrid (AMG) is a leading choice for solving linear systems. However, on the newest architectures, the relatively high cost of communication versus computation is a concern for the scalability of traditional implementations. A new algorithm is introduced that replaces the traditional iterative cycle with global domain decomposition cycles. Algebraic MultiGrid Domain Decomposition (AMG-DD) and Algebraic MultiGrid Range Decomposition (AMG-RD) trade communication for computation by forming composite levels that replace many stages of multilevel communication with local computation using redundant information.
Adaptive AMG
Another open topic in the application of AMG is in the context of solving systems of equations. Multigrid methods are founded on the juxtaposition between the principles of relaxation and coarse grid corrections to reduce error. Selection of the coarse grid typically is based on the structure of the linear system that is being inverted. A question that remains to be asked, and addressed, is whether relaxation can identify not only what the correct coarse grid is, but also what form is the error that must be obtained from this grid. A new approach to the coarsening algorithm is posited that attempts to answer these questions concurrently by analyzing slow converging errors.
Graph Laplacian
Historically, AMG has been used to solve linear systems that arise from the discretization of differential equations. However, due to the O(N) scalability of the method, it seems natural to investigate it in other contexts that generate large sparse linear systems. Data mining in graph theory applications generate very large, but extremely sparse, linear systems, called Graph Laplacians. In order to mine information from graphs, often spectral clustering is applied to these Graph Laplacians based upon the eigenvectors. One set of graphs that are of specific interest are scale-free graphs, that is, graphs whose vertices have a degree distribution that follow a power law. The question to then be answered is what information can actually be obtained from the eigenvectors of different forms of Graph Laplacians. The plan is to pursue each of these topics by developing efficient methods for each and analyzing them both numerically and theoretically.