A robust preconditioner based on algebraic substructuring and two-level grids

A domain decomposition method is used to construct a new type of block matrix incomplete factorization method. The properties of this method are such that it can be used as an efficient (i.e. with low computational complexity) and robust, corrector on a coarse mesh. Since the cost of it is of optimal order of computational complexity there is no need to use any further levels of grids as it is in a classical multigrid method. Combined with a smoother on the fine mesh the method turns out to perform as well on difficult problems as on model type problems and with a complexity about as low as that for a classical multigrid method on the model problems. The method is well suited for vector- and parallel Computers. The smoothing-correction forms a V-cycle step which can be used as a preconditioner for a conjugate gradient method, thus guaranteeing convergence. However, the method is so efficient that there is rarely any need for convergence acceleration.