| When solving partial differential equations numerically, the continuous problem is discretized and represented by a system of linear equations. The matrix representation of the discrete problem is built by a process known as data assembly. Finite Element Method (FEM) discretizations are based on a mesh. Data assembly is fairly simple for FEMs, but problems are encountered with discontinuous PDEs and expensive remeshing is required for adaptive FEMs. An alternative to FEMs are a class of Meshfree methods, in which the discretizations are based on nodes. For meshfree Galerkin methods, solutions are constructed using a collection of basis functions. Data assembly in meshfree methods is more complicated than for FEMs, in that sparsity pattern of the matrices involved is not as regular as it is in FEMs, where the (i, j)th entry is nonzero if node i is adjacent to node j. For meshfree methods, the (i, j)th entry is nonzero if nodes i and j lie in the intersection of the supports of the basis functions associated with nodes i and j. This leads to a computational geometry problem which must be solved. We solve the following problem: Given a collection of N sets (d-rectangles or d-spheres) S i and P points xk in compute Ik = {lcub}(i, j) | xk ∈ Si ∩ Sj{rcub}. We describe a computationally efficient implementation for d = 2 using quadtrees to solve I( k) = {lcub}i | xk ∈ Si{rcub} from which Ik can easily be produced. The results may be extended to using 2d-trees (for example, octrees for the case d = 3). In this thesis we describe a parallel algorithm for solving this problem. Parallel issues of load balancing and characteristics of the collections of sets and points that are used in applications which have implications for the performance of the algorithm are considered theoretically and also exhibited through numerical examples. |
