Page 119 - The Combined Finite-Discrete Element Method

102 CONTACT DETECTION

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Figure 3.39 The final stage of the sorting process.

The process of identifying the largest and smallest number followed by the swapping
procedure as described above is now repeated for each of the sub-arrays in turn, until
each of them is split into two arrays.
This process of splitting arrays into two array is recursively performed until the size of
the individual arrays is reduced to a single number (Figure 3.39). At this point array X
is sorted.
It is evident that the total number of successive subdivisions is equal to

b = log N (3.51)
2
During each subdivision, the total number of operations is proportional to N. Thus, the
total number of algebraic operations necessary to sort an array of size N is proportional
to N log N, and the total CPU time necessary to sort the array is therefore given by
2
T s = N log N (3.52)
2
In summary, the sorting contact detection algorithm has the following properties:

• The total CPU time is not dependent on the spatial distribution of discrete elements.
Thus, the algorithm has the same performance for both dense and loose packs.
• The total RAM requirements are not a function of the spatial distribution of dis-
crete elements.
• The total CPU time is proportional to
T ∝ N log N (3.53)
2
• The total RAM space needed is given by

M = 3N;in 2D
M = 4N;in 3D, i.e. (3.54)
M ∝ N

3.8 MUNJIZA-NBS CONTACT DETECTION ALGORITHM IN 2D
The screening contact detection algorithm is very efficient in terms of CPU. However,
memory requirements may be very significant, and may emerge as a limiting factor in
determining the size of the problem that can be solved on a particular computer. The
sorting algorithm is very efficient in terms of the size of arrays, i.e. in terms of RAM
requirements. However, it is not as efficient in terms of the CPU time required to solve a
particular problem, because the CPU time is greater than the CPU time required by either
the screening or binary tree based contact detection algorithms. In addition, the CPU time
is not a linear function of the total number of discrete elements.