Spatial decomposition

The real-space sum is particularly easy to parallelize as it simply involves a spatial decomposition with appropriate attention to the overlap between adjacent regions due to the cut-off radius. Performance for the real-space contribution alone is given in Fig. 4. 

Fig. 1. Nonbonded force evaluation may be distributed among processors according to atomic coordinates, as in spatial decomposition (left), or according to the indices of the interacting atoms, as in force-matrix decomposition (right). Shades of gray indicate processors to which interactions are assigned.

Methods of decomposing the nonbonded force evaluation fall into two classes, spatial decomposition [15] in which atoms and their interactions are divided among processors based on their coordinates, and force-matrix decomposition [16] in which the calculation of the interaction between a pair of atoms is assigned to a processor without considering the location of either atom (Fig. 1). Spatial decomposition scales better to large numbers of... 

In order to improve parallelism and load balancing, a hybrid force-spatial decomposition scheme was adopted in NAMD 2. Rather than decomposing the nonbonded computation into regions of space or pairwise atomic interactions, the basic unit of work was chosen to be interactions between atoms... 

Clark, T., Hanxleden, R., McCammon, J., Scott, L. Parallelizing molecular dynamics using spatial decomposition. In Proceedings of the scalable high performance computing conference. May 23-25, 1994, Knoxville, Tennessee. IEEE Computer Society Press, Los Alamitos, California, 1994. 

Each processor is assigned a portion of the physical simulation domain, involving a spatial decomposition of the workload. 

In spatial decomposition, or geometric methods,249 tjjg physical simulation domain is subdivided into small three-dimensional boxes, one for each processor. Each processor computes forces on and updates the positions and velocities of all atoms within its box at each time step, with atoms reassigned to new processors as they move through the physical domain. Because a processor can compute forces on its atoms knowing only the positions of atoms in nearby boxes, the communication required in the spatial decomposition is local, in contrast to the global communications required in the atom and force decomposition methods. 

Brown, Clarke, Okuda, and Yamazaki also adopted a domain decomposition parallelization strategy on the Fujitsu API 000 machine. " They describe an algorithm that is a development of a spatial decomposition technique due to Liem and co-workers but incorporated decomposition of three-dimensional space in all three dimensions with linked-cell and neighbor table techniques for enhanced efficiency. Communications between processors were minimized without incurring the penalties associated with redundant force calculation. 

The first problem is generally solved by introducing mass- and phase weighted volume averaged variables and the concept of spatial decomposition of these variables [98, 81]. 

We can now adopt the concept of spatial decomposition of the mass-weighted variables to relate the average of products to products of average. 

Introducing the mass-weighted variables (3.182) and manipulating the convective terms by use of the concept of spatial decomposition (3.183), the averaged equation (3.139) can be written as ... 

The modified volume averaged internal energy equation can be deduced from (3.170) introducing a spatial decomposition of the velocity variable. The result is ... 

Since the spatially averaged model for incompressible systems is used occasionally in chemical engineering practice, we will briefly outline the Re3molds like spatial decomposition and averaging procedure for completeness. In this case the 0 represents the spatial deviation of the point variable tjjk from the intrinsic volume average value ipk)vk7 is defined by ... 

Prom (3.184) the volume averaged mass flux of phase k in (3.138) is reformulated using a spatial decomposition (3.183) of the velocity variable. Thus, we can write ... 

Once this spatial decomposition has been stated, modeling the role of space consists of defining local variables that correspond to global state variables. Each local variable results from application of a spatial operator that depends on the geometry of space. The simplest is the Euclidean space, that is, ordinary space independent from time, also called flat space by opposition with curved space-time, which is the frame of the general relativity. 

To find the overall time complexity we have to look at every step of the algorithm separately. We begin discussing the spatial decomposition analysis In order to distribute the points contained by a voxel set to their respective subvoxel we need to determine the subvoxel affiliation of every point. This leads to an computational complexity of 0( P ) in every refinement step. Considering the HM wrapping we have to differentiate between the regular TZ and the irregular I operation but keep in mind that both are interdependent. Due to the fact that TZ basically depends linearly on the number of faces of and hence on ... 

---