This paper deals with the application of domain decomposition methods for the parallel solution of boundary value problems for partial differential equations over a domain $Omegabset R^d$, $d=2,3$. The attention is focused on the conception of efficient communication routines for the data exchange which is necessary for example in the preconditioned cg-algorithm for solving the resulting system of algebraic equations. The paper describes the data structure, different algorithms, and computational tests.

A parallel realisation of the Conjugate Gradient Method with Schur-Complement preconditioning, based on a domain decomposition approach, is described in detail. Special kinds of solvers for the resulting interiour and coupling systems are presented. A large range of numerical results is used to demonstrate the properties and behaviour of this solvers in practical situations.

Adaptive finite element methods for the solution of partial differential equations require effective methods of mesh refinement and coarsening, fast multilevel solvers for the systems of FE equations need a hierarchical structure of the grid. In the paper a technology is presented for the application of irregular hierarchical triangular meshes arising from refinement by only dividing elements into four congruent triangles. The paper describes the necessary data structures and data structure management, the principles and algorithms of refining and coarsening the mesh, and also a specific assembly technique for the FE equations system. Aspects of the parallel implementation on MIMD computers with a message passing communication are included.

In the paper, the parallelization of multi-grid methods for solving second-order elliptic boundary value problems in two-dimensional domains is discussed. The parallelization strategy is based on a non-overlapping domain decomposition data structure such that the algorithm is well-suited for an implementation on a parallel machine with MIMD architecture. For getting an algorithm with a good paral- lel performance it is necessary to have as few communication as possible between the processors. In our implementation, communication is only needed within the smoothing procedures and the coarse-grid solver. The interpolation and restriction procedures can be performed without any communication. New variants of smoothers of Gauss-Seidel type having the same communication cost as Jacobi smoothers are presented. For solving the coarse-grid systems iterative methods are proposed that are applied to the corresponding Schur complement system. Three numerical examples, namely a Poisson equation, a magnetic field problem, and a plane linear elasticity problem, demonstrate the efficiency of the parallel multi- grid algorithm.