Technical Report PHD-2014-12

Title: Aggregation-based Adaptive Algebraic Multigrid for Sparse Linear Systems
Authors: Eran Treister
Supervisors: Irad Yavneh
Abstract: Multigrid methods have long been recognized for their efficiency as solvers of sparse linear systems of equations, mainly such that arise from discretizations of Partial Differential Equations. A great effort was invested in recent years in extending the applicability of algebraic multigrid (AMG) methods, mainly through the development of adaptive versions.

Our first study focuses on adaptive aggregation multigrid approaches for the solution of Markov-Chains. This problem has drawn recent attention, due to its relevance in web search applications. It involves finding the principal eigenvector of column stochastic matrices. Because AMG methods require a good approximation of this vector in order to define the multigrid operators, adaptive AMG methods have been introduced, whereby the operators are gradually improved as the iterations progress. We developed several new ideas, building on the so-called ``Smoothed Aggregation'' approach, highlighted by a novel Bottom-Up aggregation technique. Another significant development involves an ``on-the-fly'' framework for simultaneously applying the adaptive multigrid components. Our framework can incorporate any existing AMG method for Markov-Chains.

Our second study focuses on non-Galerkin AMG. Traditional methods use a hierarchy of smaller and smaller problems, which are usually defined by Galerkin coarsening. There, the coarse problems are defined by projecting the original operator using the transfer operators, which control the sparsity pattern and operator complexity of the hierarchy. In many scenarios, the coarse operators tend to be denser than the fine operator as the coarsening progresses. Such behavior is especially problematic in parallel AMG computations where it imposes an expensive communication overhead. In this work we present a new technique for controlling the sparsity pattern of the operators in the hierarchy. Our method is based on the aggregation framework, and it “sparsifies” Smoothed Aggregation operators while preserving their right and left near null-spaces.

Our third study introduced the multilevel approach to the area of sparse approximation of signals, which is drawing tremendous attention in recent years. Typically, sparse solutions of underdetermined linear systems of equations are obtained by minimizing an l1 penalized least squares functional. Various iterative “shrinkage” algorithms have been developed for handling these problems. In this work, we suggest a new multilevel framework that reduces the computational cost of existing solvers. Our framework takes advantage of the typically sparse representation of the signal, and at each iteration it adaptively creates and processes a hierarchy of lower-dimensional problems. We show that this approach significantly enhances the performance of existing iterative shrinkage algorithms.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2014
To the main CS technical reports page

Computer science department, Technion