Department of Applied Mathematics, Division for Scientific Computing and Numerical Simulation

Wegelerstr. 6, D-53115 Bonn, Germany

Tel.: +49-228-73-3427, FAX: +49-228-73-7527

griebel@iam.uni-bonn.de schweitz@iam.uni-bonn.de

Abstract

In this paper we present a multilevel solver for Galerkin discretizations of elliptic PDEs
using so-called meshless methods (MM) [2, 3, 5, 6, 7, 8].
Meshless methods are promising approaches to overcome the problem of mesh generation which still is
the most time-consuming part of any finite element (FE) simulation. Meshless methods are based only on
a (finite) collection of independent points within the domain of interest, i.e. there are no fixed
connections between any two points like in a conventional mesh.

In the design of our multilevel solver, we utilize a hierarchical cover construction
algorithm [2] for
Partition of Unity Methods (PUM)
which induces a hierarchy of nonnested PUM function spaces and
a variational approach to the approximation problem arising in the construction
of interlevel transfer operators.
The shape functions of our PUM are piecewise rational functions and non-interpolatory,
due to the meshless construction which uses only a set of irregularly spaced points
with no fixed connection between them (unlike in a mesh).
Hence, the usual interpolation approach to the construction
of interlevel transfer operators is not applicable. One way of tackling
this problem is the use of L2-projections as interlevel transfer operators.
The linear systems arising from a PUM discretization are sparse block systems,
due to the fact that the PUM shape functions are products of a partition of
unity function (h-component) and a higher order approximation function (p-component).
Therefore, we can choose the second main ingredient of our multilevel solver,
the smoothing operators, to utilize this block structure.
Here, we choose block smoothers which operate on p-component
blocks of the PUM function space and therefore
eliminate the p-dependence of the convergence rate.

Since the meshless construction leads to a sequence of
nonnested function spaces, the variational assumption

The overall computational costs C of our multilevel algorithm is bounded by the number of points and the costs for the p-block inversion, i.e. its worst case complexity in d dimensions is

[1] | M. Griebel and M. A. Schweitzer. A Particle-Partition of Unity Method: Part III Parallelization, in preparation. |

[2] | M. Griebel and M. A. Schweitzer. A Particle-Partition of Unity Method: Part II Efficient Cover Construction and Reliable Integration, in preparation. |

[3] | M. Griebel and M. A. Schweitzer.
A Particle-Partition of Unity Method for the solution of
Elliptic, Parabolic and Hyperbolic PDE.
SIAM J. Sci. Comp., 22(3):853-890, 2000.
also as SFB Preprint 600, SFB 256, Institut für Angewandte
Mathematik, Universität Bonn.BibTeX entry, Compressed PS, Abstract |

[4] | A. Caglar, M. Griebel, M. A. Schweitzer, and G. Zumbusch.
Dynamic load-balancing of hierarchical tree algorithms on a cluster
of multiprocessor PCs and on the Cray T3E.
In H. W. Meuer, editor, Proceedings 14th Supercomputer
Conference, Mannheim, ISBN 3-932178-08-4, Mannheim, Germany, 1999. Mateo.
SuParCup '99 Award Winning Paper, also as SFB 256 report 27.BibTeX entry, Compressed PS, PDF, Abstract |

[5] | M. A. Schweitzer.
Ein Partikel-Galerkin-Verfahren mit Ansatzfunktionen der
Partition of Unity Method.
Diplomarbeit, Institut für Angewandte Mathematik, Universität
Bonn, 1997. BibTeX entry, Compressed PS |

[6] | I. Babuska and J. M. Melenk. The Partition of Unity Finite Element Method: Basic Theory and Applications, Comput. Meths. Appl. Mech. Engrg., Special Issue on Meshless Methods 1996, Vol. 139,pp. 289-314. |

[7] | C. A. M. Duarte and J. T. Oden. Hp clouds - A Meshless Method to solve Boundary Value Problems, Num Meth. for PDE, 12 (1996), pp. 673-705. also as Tech Rep 95-05, TICAM, University of Texas, 1995. |

[8] | C. A. M. Duarte, I. Babuska and J. T. Oden. Generalized Finite Element Methods for Three Dimensional Structural Mechanics Problems, Computers and Structures, 77 (2000), pp. 215-232. |

[9] | J. H. Bramble, J. E. Pasciak and J. Xu. The Analysis of Multigrid Algorithms with nonnested Spaces or noninherited quadratic Forms, Math. Comp., 56 (1991), pp. 1-34. |