A Multilevel Particle-Partition of Unity Method

Michael Griebel
Marc Alexander Schweitzer

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

\begin{displaymath} a_k\,({\bf I}_{k-1}^k \phi_{k-1}, {\bf I}_{k-1}^k \psi_{k-1}) \not= a_{k - 1}\,(\phi_{k-1}, \psi_{k-1}) \end{displaymath}
is no longer valid (even if we assume that the bilinear forms are the same on all levels) and the standard theory for variational multilevel algorithms is not applicable. Along the lines of a general multilevel theory presented in [9] the (uniform) convergence of the V and W cycles can be shown if
\begin{displaymath} a_k\,({\bf I}_{k-1}^k \phi_{k-1}, {\bf I}_{k-1}^k \psi_{k-1}) \leq C a_{k - 1}\,(\phi_{k-1}, \psi_{k-1}) \end{displaymath}
holds (in addition to further regularity assumptions). The results of our numerical experiments show that this is indeed the case for our method (for L = -\Delta + id). The V(1,1) cycle converges independently of the number of points N (which are generated by a Halton sequence) and the polynomial degree p used during the discretization of the PDE. The average error reduction factor is independent of the number of points N and the polynomial degree p between 0.1 and 0.25 for the V(1,1) cycle, i.e.
\begin{displaymath} 0.2 \sim \rho \not= \rho\,(N, p) \end{displaymath}
using block Gauss-Seidel smoothing and about 0.5 for block Jacobi smoothing. Furthermore, these results also hold for highly irregular point sets, which correspond to adaptive discretizations. In summary, our multilevel Parition of Unity Method converges independently of the polynomial degree of the discretization and independently of the number and position of the discretization points.

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
\begin{displaymath} C = O(Np^{3d}) \end{displaymath}
In some cases, the computational costs C may even be reduced to
\begin{displaymath} C = O(Np^{d}) \end{displaymath}
leading to a multilevel solver for an hp discretization which would be only linearly dependent on the total number of degrees of freedom.

Bibliography

[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.