Page 116 - The Combined Finite-Discrete Element Method

SORTING CONTACT DETECTION ALGORITHM 99

Thus, the total number of operations necessary to perform all three steps (i.e. to detect
all the contacts for a single discrete element) is proportional to log N.
2
The total CPU time for detecting all the contacts is therefore given by

T ∝ N log N (3.47)
2
The total RAM requirements of the sorting contact detection algorithm are proportional
to the total number of discrete elements N, and do not depend upon how the discrete
elements are distributed (packed) in space. In fact, the total RAM requirements are equal
to 3N integer numbers. In 3D space these increase to 4N integer numbers, which is
usually 16 bytes per discrete element.
The CPU performance of the sorting algorithm is not a function of spatial distribution
of the discrete elements. Arrays X, Y and D are the same regardless of whether discrete
elements are close to each other or far away. For instance, if the only change to the
discrete element system is the doubling of the distance between discrete elements (i.e.
doubling the size of the edge of the space bounding box), the search operations together
with arrays X, Y and D would not change at all.
However, to achieve the above described CPU and RAM performance, it is necessary
to develop an efficient procedure for sorting arrays X, Y and D. There are a number of
ways to sort these arrays. The procedure described below does not require any additional
RAM space, and achieves sorting in CPU time proportional to

T sort ∝ N log (3.48)
2

The procedure is explained using the example given in Figure 3.28.
The first step in sorting is to identify the maximum and minimum number in the array,
as shown in Figure 3.29. This operation requires a CPU time proportional to the total
number of discrete elements N.
The next step is to calculate the middle point between the identified maximum and
minimum number:
x min + x max 1 + 16
x mid = = = 8 (3.49)
2 2
Now the array is parsed from both sides simultaneously. Each number is compared to the
middle point:
x mid = 8 (3.50)

3167112145 9 4 812613 15110

Figure 3.28 A hypothetical array to be sorted.

3167112145 9 4 812613 15110

Figure 3.29 Identifying the maximum and minimum number.