On the Schur complement of the nearest Kronecker product preconditioner for elliptic boundary value problems

The numerical solution of elliptic partial differential equations requires the inversion of large matrices, which is computationally expensive. An elegant and efficient domain decomposition method for almost-separable elliptic PDEs is presented. Suitable preconditioners for continuous Galerkin methods are obtained through exploiting characteristics of the matrix structure. First, the elliptic operator may be well approximated at each subdomain as a sum of two Kronecker products, which may be efficiently obtained via the Lanczos SVD algorithm. The Nearest Kronecker Product (NKP) approximation represents an ideal preconditioner given the minimal computational cost required for inversion, as it can be factored in a separable fashion. Second, the Schur complement method allows the parallel solution of each subdomain by decoupling the interface degrees of freedom via block-Gaussian elimination. The explicit computation of the Schur complement for the NKP is enormously simplified, making its LU decomposition feasible to be used to invert the preconditioner in an iterative solver. Most solutions can be obtained with 30 or less GMRES iterations, disregarding the number of grid points. The method is then utilized to yield eigenmodes for the 2D Laplacian in composite domains.