The most time-consuming part in a PUM simulation is the assembly of the stiffness matrix, hence we need to balance the work during the integration of the PUM shape functions. To this end, we use a space filling curve indexing scheme to order the cover patches and local approximation spaces. The curve defines a one-dimensional order of the cover patches which respects the multi-dimensional location of the patches, i.e. the difference of indices for overlapping patches is most likely very small. Hence, neighboring patches are most likely assigned to the same processor minimizing the number of communication steps. To control the communication volume, we need to estimate the work and memory load associated with each cover patch by the dimension and algebraic structure of the local approximation space, the number of overlapping neighbor patches and their associated approximation spaces. Summing these weights over all cover patches gives an estimate of the global work which has to be balanced. Hence, by a linear walk over the ordered cover patches and summing their associated work load up to the point when this local load excedes the optimal balance, we can achieve a good load balance independent of the spatial dimension and distribution of the points used for the PUM construction.

Depicted in the figures given below are the point sets used for the PUM construction and the associated space filling curve ordering for three simple domains in two dimensions: the unit cube, the L-domain and a cube with a cubical void. On these domains we approximate a simple diffusion problem. Also given are the error and approximate solution computed using our partition of unity.

Marc Alexander Schweitzer Last modified: Sat Nov 11 20:02:20 CET 2000