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 [1]. 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) [8]. 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.

[1]

W. Hackbusch, "Convergence of a multi-grid iteration applied to difference equations", Math. Comp., 34, 425-440, 1980. doi:10.2307/2006094

[2]

G.A. Gravvanis, "Explicit Approximate Inverse Preconditioning Techniques", Archives of Computational Methods in Engineering, 9(4), 371-402, 2002. doi:10.1007/BF03041466

[3]

G.A. Gravvanis, "The rate of convergence of explicit approximate inverse preconditioning", Inter. J. Comp. Math., 60, 77-89, 1996. doi:10.1080/00207169608804476

[4]

G.A. Gravvanis, C.K. Filelis-Papadopoulos, P.I. Matskanidis, "Algebraic multigrid methods based on Generic Approximate Matrix Techniques", TR/ECE/ASC-AMA/2012/13, submitted.

[5]

U. Trottenberg, C.W. Osterlee, A. Schuller, "Multigrid", Academic Press, 2000.

[6]

H. De Sterck, U. Yang, J. Heys, "Reducing complexity in parallel algebraic multigrid preconditioners", SIAM Journal on Matrix Analysis and Applications 27, 1019-1039, 2006. doi:10.1137/040615729

[7]

U.M. Yang, "Parallel Algebraic Multigrid Methods - High Performance Preconditioners", in A.M. Bruaset, A. Tveito, (Editors), "Numerical Solution of Partial Differential Equations on Parallel Computers", 51, 209-236, Springer-Verlag, 2006. doi:10.1007/3-540-31619-1_6

[8]

G.A. Gravvanis, "High Performance Inverse Preconditioning", Archives of Computational Methods in Engineering, 16(1), 77-108, 2009. doi:10.1007/s11831-008-9026-x

[9]

E.A. Lipitakis, D.J. Evans, "Explicit semi-direct methods based on approximate inverse matrix techniques for solving boundary-value problems on parallel processors", Math. and Computers in Simulation, 29, 1-17, 1987. doi:10.1016/0378-4754(87)90062-0

purchase the full-text of this paper (price £20)

go to the previous paper
return to the table of contents
return to Computational Technology Reviews
purchase this volume (price £80 +P&P)