Algebraic Multigrid Methods For Parallel Computing, Systems, and Graphs
Tobias Jones
Applied Mathematics, University of Colorado Boulder
Date and time:
Friday, November 8, 2013 - 2:00pm
Location:
Grandview Conference Room at 1320 Grandview Ave
Abstract:
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.
Introduced here are Algebraic MultiGrid Domain Decomposition (AMGDD)
and Algebraic MultiGrid Range Decomposition (AMG-RD) which
trade communication for computation by forming composite levels that
replace many stages of multilevel communication with local computation
using redundant information.
Another open topic in the application of AMG is in the context of
solving systems of equations. Adaptive Smoothed Aggregation was developed
as a method to address the potential difficulties with not only
generating the aggregates in this setting, but also to generate the kernel
components required to efficiently solve these problems. New variants on
this approach are introduced that aim to more effectively identify the local
and global near null spaces as well as form more robust multilevel solvers.
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. As a step in the process of targeting AMG
for these problems, eigenvectors of matrices formed from graphs are investigated.