SCHWARZ METHODS OF NEUMANN-NEUMANN TYPE FOR 3-DIMENSIONAL ELLIPTIC FINITE-ELEMENT PROBLEMS

Several domain decomposition methods of Neumann-Neumann type are consi dered for solving the large linear systems of algebraic equations that arise from discretizations of elliptic problems by finite elements. W e will only consider problems in three dimensions. Several new variant s of the basic algorithm are introduced in a Schwarz method framework that provides tools which have already proven very useful in the desig n and analysis of other domain decomposition and multi-level methods. The Neumann-Neumann algorithms have several advantages over other doma in decomposition methods. The subregions, which define the subproblems , only share the boundary degrees of freedom with their neighbors. The subregions can also be of quite arbitrary shape and many of the major components of the preconditioner can be constructed from subprograms available in standard finite element program libraries. In its origina l form, however, the algorithm lacks a mechanism for global transporta tion of information and its performance therefore suffers when the num ber of subregions increases. In the new variants of the algorithms, co nsidered in this paper, the preconditioners include global components, of low rank, to overcome this difficulty. Bounds are established for the condition number of the iteration operator, which are independent of the number of subregions, and depend only polylogarithmically on th e number of degrees of freedom of individual local subproblems. Result s are also given for problems with arbitrarily large jumps in the coef ficients across the interfaces separating the subregions. (C) 1995 Joh n Wiley & Sons, Inc.