Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation
Title Parallel Partition of Unity Methods
Participiant Michael Griebel, Marc Alexander Schweitzer
Key words partition of unity, meshfree method, meshless method, particle method, parallel computing, domain decomposition, tree code, space filling curve, dynamic load balancing
Description We are concerned with the construction of a Meshless Galerkin Method for the numerical treatment of partial differential equations. Meshless Methods are promising approaches to overcome the need for mesh generators which are still the most time-consuming component of any Finite Element simulation.

With the partition of unity approach, we define an approximate global solution

u_{\rm PU} (x):= \sum_{i=1}^{N} \varphi_i (x) u_i (x).

simply as the ''weighted`` sum of local approximations, where these weighting functions form a partition of unity which fulfills any global regularity constraint. The local approximations are completely independent, i.e. not only the order of the local approximations may vary but also the local basis may vary locally. Hence, a global approximation constructed by a PUM is simply the collection of independent locally defined approximations spliced together using the partition of unity. Obviously, the selection of the partition of unity has significant impact on the computational effort necessary to construct such a global solution. For instance Moving Least Squares partition of unities (see [9]) involve the solution of a local approximation problem for every function evalution of the partition of unity. Therefore, we limit ourselves to the use of Shepard functions for the partition of unity.

Assume we have a cover of the domain. Then, we assign weight functions of anticipated regularity to each of the patches of the cover. Shepard's functions are then simply defined as

\varphi_i (x) = \frac {W_i(x)}{\sum W_j (x)}.

With this approach it is only necessary to construct a cover (with no further geometric constraints) of the domain. We have developed several different approaches to construct such a cover for our partition of unity method based only a given set of irregularly spaced points (see [3]). Here, we make use of d-binary trees to partition the domain into patches which we associate with a given point. See Cover Construction for examples.

Using the shape functions defined by the partition of unity approach within a Galerkin discretization raises the question of how to compute the entries of the stiffness matrix efficiently yet with prescribed accuracy. To this end, we have developed a numerical quadrature scheme based on domain subdivision (see [1, 4]) and sparse grid quadrature rules (see [1, 7]).

Large scale numerical simulations with several million degrees of freedom rely on the use of parallel computers due to memory restrictions of a single workstation. Furthermore, parallel computing can and should significantly reduce the overall runtime. We have implemented a scalable parallel version (using MPI) of our partition of unity method using a space filling curve indexing scheme for the cover patches, i.e. a general domain decomposition approach (see [3]). See Parallelization for some prelimenary results.

Furthermore, the coupling of our Partition of Unity Method and particle methods for the treatment of lagrangian motion and transport phenomena is studied (see [4]). See Linear Advection and Convection Diffusion for some numerical results.

Another benefit of the hierarchical cover construction algorithm is the fact that it introduced also a hierarchy on the PUM function space. Therefore, we can exploit the tree construction for the covers also in the design and implementation of fast multilevel solvers for our PUM (see [2]).

[1] M. Griebel and M. A. Schweitzer. A Particle-Partition of Unity Method-Part II: Efficient Cover Construction and Reliable Integration. SFB Preprint, Sonderforschungsbereich 256, Institut für Angewandte Mathematik, Universität Bonn, 2001.
BibTeX entry, Compressed PS, PDF, Abstract
[2] M. Griebel and M. A. Schweitzer. A Particle-Partition of Unity Method-Part III: A Multilevel Solver. SFB Preprint, Sonderforschungsbereich 256, Institut für Angewandte Mathematik, Universität Bonn, 2001.
BibTeX entry, Compressed PS, PDF, Abstract
[3] M. Griebel and M. A. Schweitzer. A Particle-Partition of Unity Method-Part IV: Parallelization, in preparation.
[4] 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
[5] 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
[6] 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
[7] T. Gerstner and M. Griebel. Numerical Integration using Sparse Grids. Numer. Algorithms, 18:209-232, 1998. (also as SFB 256 preprint 553, Univ. Bonn, 1998).
BibTeX entry, Compressed PS, Abstract
[8] 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.
[9] 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.
[10] 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.
Related projects
In cooperation with

Marc Alexander Schweitzer
Last modified: Wed Aug 15 08:15:06 CEST 2001