Domain decomposition methods and deflated Krylov subspace iterations

The balancing Neumann-Neumann (BNN) and the additive coarse grid correction (BPS) preconditioner are fast and successful preconditioners within domain decomposition methods for solving partial differential equations. For certain elliptic problems these preconditioners lead to condition numbers which are independent of the mesh sizes and are independent of jumps in the coefficients (BNN). Here we give an algebraic formulation of these preconditioners. This formulation allows a comparison with another solution or preconditioning technique- the deflation technique. By giving a detailed introduction into the deflation technique we establish analogies between the balancing, the additive coarse grid correction and the deflation technique. We prove that the effective condition number of the deflated preconditioned system is always, i.e. for all deflation vectors and all restrictions and prolongations, below the condition number of the system preconditioned by the balancing preconditioner and the coarse grid correction preconditoner. This implies that the conjugate gradient method applied to the deflated preconditioned system is expected to converge always faster than the conjugate gradient method applied to the system preconditioned by the coarse grid correction or balancing. Moreover, we prove that the A-norm of the errors of the iterates built by the deflation preconditioner is always below the A-norm of the errors of the iterates built by the balancing preconditioner. Numerical results for porous media flows emphasize the theoretical results.