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 timeconsuming
component of any Finite Element simulation. With the partition of unity approach, we define an approximate global solution
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
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 dbinary 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]).


Bibliography 


Related projects 


In cooperation with 
