Skip to Main content Skip to Navigation

A class of multilevel parallel preconditioning strategies

Laura Grigori 1 Pawan Kumar 1 Frédéric Nataf 2 Ke Wang 3 
1 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : In this paper, we introduce a class of recursive multilevel preconditioning strategies suited for solving large sparse linear systems of equations on modern day architectures. They are based on a reordering of the input matrix into a nested bordered block diagonal form, which allows a nested formulation of the preconditioners. The first one, which we refer to as nested SSOR (NSSOR), requires only the factorization of diagonal blocks at the innermost level of the recursive formulation. Hence, its construction is embarassingly parallel, and the memory requirements are very limited. Next two are nested versions of Modified ILU preconditioner with row sum (NMILUR) and colsum (NMILUC) property. We compare these methods in terms of iteration number, memory requirements, and overall solve time, with ILU(0) with natural ordering and nested dissection ordering, and MILU. We find that NSSOR compares favorably with ILU(0) with nested dissection ordering, while NMILUR and NMILUC outperform the other methods for certain matrices in our test set. It is proved that the NSSOR method is convergent when the input matrix is SPD. The preconditioners are designed to be suitable for parallel computing.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Laura Grigori Connect in order to contact the contributor
Submitted on : Wednesday, October 6, 2010 - 10:36:44 PM
Last modification on : Sunday, June 26, 2022 - 11:52:21 AM
Long-term archiving on: : Thursday, October 25, 2012 - 4:35:51 PM


Files produced by the author(s)


  • HAL Id : inria-00524110, version 1


Laura Grigori, Pawan Kumar, Frédéric Nataf, Ke Wang. A class of multilevel parallel preconditioning strategies. [Research Report] RR-7410, INRIA. 2010. ⟨inria-00524110⟩



Record views


Files downloads