A Domain Decomposition Algorithm for Hermite Collocation Problems

Gabriel Mateescu, Calvin J. Ribbens, and Layne T. Watson

Department of Computer Science
Virginia Tech
Blacksburg, VA 24061


Designing substructuring methods for high order discretization methods for solving elliptic PDEs poses several challenges. We consider linear systems of equations arising from piecewise Hermite bicubic collocation applied to general linear two-dimensional second-order elliptic PDEs with mixed boundary conditions. We construct an efficient, parallel preconditioner for the GMRES(k) method. Our initial focus is on rectangular domains decomposed in one dimension. We also consider extensions to two dimensional decompositions. The main contribution of the paper is a novel interface preconditioner derived using the Schur complement approach. The Hermite collocation framework allows us to define a local discretization for the interface subproblems based on a hybrid coarse/fine mesh. Interface equations based on this mesh depend only weakly on unknowns associated with subdomains, and hence, in the corresponding Schur complement the mutual coupling between interfaces is reduced. This suggests an approximation to the Schur complement that is both accurate and efficient: accurate in that it is a reasonable approximation to the original Schur complement, and efficient in that it is block diagonal, with one block corresponding to each interface subproblem.

We describe the motivation, construction, and implementation of our proposed preconditioner. Substructuring, in the context of collocation, requires use of a non-finite-element ordering of equations, which we briefly describe. We illustrate the performance of the proposed preconditioner with numerical experiments. Our results indicate that for a fixed number of subdomains, the number of iterations is virtually independent of the problem size, and the number of iterations is small enough that the GMRES iteration does not have to be restarted, i.e., full GMRES is practical for the problems tested. Furthermore, for a fixed problem size, the number of iterations grows very slowly, though linearly, with the number of subdomains.