טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentTreister Eran
SubjectAggregation-based Adaptive Algebraic Multigrid for
Sparse Linear Systems
DepartmentDepartment of Computer Science
Supervisor Professor Irad Yavneh
Full Thesis textFull thesis text - English Version


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 “sparsifie” 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.