A particle-partition of unity method - Part II: Efficient cover construction and reliable integration

In this paper we present a meshfree discretization technique based only on a set of irregularly spaced points x(i) is an element of R-d and the partition of unity approach. In this sequel to [ M. Griebel and M. A. Schweitzer, SIAM J. Sci. Comput., 22 ( 2000), pp. 853 890] we focus on the cover construction and its interplay with the integration problem arising in a Galerkin discretization. We present a hierarchical cover construction algorithm and a reliable decomposition quadrature scheme. Here, we decompose the integration domains into disjoint cells on which we employ local sparse grid quadrature rules to improve computational efficiency. The use of these two schemes already reduces the operation count for the assembly of the stiffness matrix significantly. Now the overall computational costs are dominated by the number of the integration cells. We present a regularized version of the hierarchical cover construction algorithm which reduces the number of integration cells even further and subsequently improves the computational efficiency. In fact, the computational costs during the integration of the nonzeros of the stiffness matrix are comparable to that of a finite element method, yet the presented method is completely independent of a mesh. Moreover, our method is applicable to general domains and allows for the construction of approximations of any order and regularity.