Print Email Facebook Twitter A Comparison of Two-Level Preconditioners Based on Multigrid and Deflation Title A Comparison of Two-Level Preconditioners Based on Multigrid and Deflation Author Tang, J.M. MacLachlan, S.P. Nabben, R. Vuik, C. Faculty Electrical Engineering, Mathematics and Computer Science Department Delft Institute of Applied Mathematics Date 2010-03-10 Abstract It is well known that two-level and multilevel preconditioned conjugate gradient (PCG) methods provide efficient techniques for solving large and sparse linear systems whose coefficient matrices are symmetric and positive definite. A two-level PCG method combines a traditional (one-level) preconditioner, such as incomplete Cholesky, with a projection-type preconditioner to get rid of the effect of both small and large eigenvalues of the coefficient matrix; multilevel approaches arise by recursively applying the two-level technique within the projection step. In the literature, various such preconditioners are known, coming from the fields of deflation, domain decomposition, and multigrid (MG). At first glance, these methods seem to be quite distinct; however, from an abstract point of view, they are closely related. The aim of this paper is to relate two-level PCG methods with symmetric two-grid (V(1,1)-cycle) preconditioners (derived from MG approaches), in their abstract form, to deflation methods and a two-level domain-decomposition approach inspired by the balancing Neumann–Neumann method. The MG-based preconditioner is often expected to be more effective than these other two-level preconditioners, but this is shown to be not always true. For common choices of the parameters, MG leads to larger error reductions in each iteration, but the work per iteration is more expensive, which makes this comparison unfair. We show that, for special choices of the underlying one-level preconditioners in the deflation or domain-decomposition methods, the work per iteration of these preconditioners is approximately the same as that for the MG preconditioner, and the convergence properties of the resulting two-level PCG methods will also be (approximately) the same. This means that, in this respect, the particular choice of the two-level preconditioner is less important than the choice of the parameters. Numerical experiments are presented to emphasize the theoretical results. Subject deflationdomain decompositionmultigridconjugate gradientstwo-grid schemesSPD matricestwo-level preconditioning To reference this document use: http://resolver.tudelft.nl/uuid:4d1dfdee-a481-4253-906d-78ea4d741719 DOI https://doi.org/10.1137/08072084X Publisher Society for Industrial and Applied Mathematics ISSN 0895-4798 Source SIAM Journal on Matrix Analysis and Applications, 31 (4), 2010 Part of collection Institutional Repository Document type journal article Rights © 2010 The Author(s)Society for Industrial and Applied Mathematics Files PDF Vuik2010.pdf 327.43 KB Close viewer /islandora/object/uuid:4d1dfdee-a481-4253-906d-78ea4d741719/datastream/OBJ/view