Fourier and probe variants of the vertex space domain decomposition algorithm

The vertex space algorithm of Smith is a domain decomposition method for two dimensional elliptic problems based on non-overlapping subregions, in which the reduced Schur complement system on the interface is solved using a generalized block Jacobi type preconditioner, with the blocks corresponding to the vertex space, edges and a coarse grid. In this paper, we describe several variants of this algorithm derived from using two kinds of approximations for the edge and vertex space sub-blocks, one based on Fourier approximation, and another based on an algebraic probing technique in which sparse approximations to these sub-blocks are computed. Our motivation is to improve efficiency of the algorithm without sacrificing the optimal convergence rate. Numerical and theoretical results on the performance of these algorithms are presented.