Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Computational Technology Reviews
Computational Technology Reviews
Volume 7, 2013
A Survey of the Parallelization Issues for Geometric and Algebraic Multigrid Methods based on Generic Banded Approximate Inverses
G.A. Gravvanis, C.K. Filelis-Papadopoulos and P.I. Matskanidis
Department of Electrical and Computer Engineering, School of Engineering, Democritus University of Thrace, Kimmeria, Xanthi, Greece
G.A. Gravvanis, C.K. Filelis-Papadopoulos, P.I. Matskanidis, "A Survey of the Parallelization Issues for Geometric and Algebraic Multigrid Methods based on Generic Banded Approximate Inverses", Computational Technology Reviews, vol. 7, pp. 65-98, 2013. doi:10.4203/ctr.7.4
Keywords: sparse linear systems, geometric multigrid methods, algebraic multigrid methods, coarsening techniques, incomplete LU factorization, generic approximate banded inverse smoothing, DOUR algorithm, parallel computations.
During recent decades, multigrid methods have gained substantial interest amongst the scientific community because of their efficiency and convergence behaviour . The effectiveness of multigrid methods based on generic approximate banded inverses (GenAbI) relies on parallel smoothers which utilize the GenAbI matrices, which are close approximants to the inverses of the respective coefficient matrices of each level of the multigrid method [2,3,4].
Multigrid methods require four distinct components in order to be formulated. These components are the smoother, the restriction and prolongation operators and the cycle strategy. The multigrid methods are divided into two categories: geometric and algebraic [1,5]. The geometric multigrid methods require previous knowledge of the geometric properties of the problem. However, the algebraic multigrid (AMG) method does not require such knowledge of the geometric properties, with the additional cost of a setup phase where the essential components of the multigrid method are computed [1,5]. The AMG coarsening schemes used for the purposes of this paper are CLJP and PMIS coarsening algorithms [6,7].
The generic approximate banded inverse matrix is a banded approximate inverse matrix based on incomplete LU factorization with zero fill-in and belongs to the family of explicit approximate inverses. Unlike its predecessors [2,8,9], it can handle any sparsity pattern thus rendering the scheme appropriate for use in conjunction with the algebraic multigrid method. Moreover, the GenAbI scheme preserves the parallel attributes of the explicit approximate inverses. The new proposed parallel GenAbI (PGenAbI) scheme is parallelized through the so-called "fishbone" technique for shared memory architectures (SMP) . Furthermore, the parallel geometric and parallel algebraic multigrid V-cycle method based on parallel GenAbI matrices is presented (PGenAbI-GMGV and PGenAbI-AMGV). The multigrid method is modified to incorporate a parallel preconditioned BiCGSTAB as a coarse level solver in order to enhance the parallel performance of the V-cycle strategy.
Finally, numerical results for the performance of the generic approximate banded inverse and the parallel geometric and parallel algebraic multigrid V-cycle method based on parallel GenAbI matrices is presented. Implementation issues for the new schemes are also discussed.
purchase the full-text of this paper (price £20)