TABLE OF CONTENTS The process of subdividing a model system into roughly equal pieces of computational work is referred to as mesh partitioning or domain decomposition. It is fortunate that our physical systems modeled with SPAM particles that flow throngh a space, governed by gradient* ( ? v , ? P ), can lake advantage of partitioning techniques developed for grid-based Eulerian and Lagrangian algorithms.
Continuum mechanics problems of interest, whether simulated with particles or regular Eulerian meshes or Lagrangian finite elements, always involve algorithms that most be designed carefully to balance the work among processors ( load balancing). Partitioning is a challenge for the topologies and interface conditions found in real-world simulations. Graph theory [9] is a useful conceptual basis for constructing partitions. "Graphs" are simply sets of "vertices", some pairs of which are connected by "lines".
Either a two-or-three-dimensional mesh or a one-or-two-dimensional material interface can be represented as a graph by first associating each element to a vertex and then drawing a line to any other vertices (elements) that have at least one nodal point in common with the element. This correspondence is illustrated in Figure 4.9 for a portion of a two-dimensional rectangular mesh of quadrilateral elements. Individual elements in such a mesh can interact with up to eight neighbors ( 26 in three dimensions ).
