On the H^{1/2} norm based Schur complement preconditioners

\underline{Béla Kiss}

Departement of Mathematics Széchenyi István College Hédervári u. 3., H-9026 Győr Hungary email: bkiss@d7.szif.hu

Anna Krebsz

Department of Numerical Analysis Lóránd Eötvös University Múzeum krt. 6-8., H-1008 Budapest Hungary

ABSTRACT

The preconditioned conjugate gradient (PCG) algorithm based domain decomposition methods are efficient parallel algorithms for the numerical solution of elliptic problems. In these papers a matrix representation of the H^{1/2} norm are used mostly as a basic tool for the construction of the Schur complement preconditioner.

This type of preconditioning was introduced by M. Dryja (see [2]). Such kind of approach is explained for example by J.H. Bramble, J.E. Pasciak and A.H. Schatz in [1], by O.Widlund in [4] and by G. Molnárka and B. Kiss in [3].

We consider here some new matrix representations of the H^{1/2} norm in the space of linear finite elements defined on the boundary Γ of a bounded domain Ω ⊂ R^{2}. These norm representations can be used as a Schur complement preconditioner to discrete harmonic problems arising from the discretization of second order elliptic problems on Ω via finite element method. By use of the proposed new norm representations a matrixvector multiplication has the complexity of O(nlog(n)), where n is the number of rows. The implementation of the PCG method using these matrices is simpler than in the case of earlier matrix representations was, where this complexity can be achived only by using the FFT algorithms.

MAIN REFERENCES

[1] Bramble, J.H., Pasciak, J.E., Schatz, A.H. (1986-1989): The Construction of Preconditioners for Elliptic Problems by Substructuring I-IV. Math. of Comp. 47(175), 103-134, 49(184), 1-16, 51(184), 415-430, 53(187), 1-24

[2] Dryja, M. (1984): A Finite Element Capacitance Method For Elliptic Problems on Region Partitioned into Subregions. Numer. Math. 44, 153-168

[3] Kiss, B., Molnárka, G. (1990): A preconditioned Domain Decomposition Algorithm for the Solution of the Elliptic Neumann Problem. In: W. Hackbush ed., Parallel Algorithm for PDE, Proceeding of 6th GAMM Seminar, Kiel, 119-129

[4] Widlund, O. (1987): Iterative Substructuring Methods: Algorithm and theory for Elliptic Problems in the Plane. Technical Report 287, Dept. of Computer Science, Courant Institute