Algebraic Multigrid Methods for Parallel Computing, Systems, and Graphs

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 (AMG-DD) 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 partial differential 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 was 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