Page 128 - The Combined Finite-Discrete Element Method

MUNJIZA-NBS CONTACT DETECTION ALGORITHM IN 2D 111

i.e. set head of the list to zero
}
}
}
8. loop over all discrete elements
{ remove the corresponding y-lists i.e. set the head of the list to zero
}

CPU and RAM requirements. Detailed analysis of the Munjiza-NBS contact detection algo-
rithm as explained in the previous section leads to the conclusion that the total detection
time is proportional to the total number of discrete elements present:

T ∝ N (3.63)

In other words, the total CPU time needed to detect all the contacts is given by

T ∝ cN (3.64)

where c is a constant independent of either packing density or number of discrete elements.
This can be proved by analysing each step of the algorithm presented in the previ-
ous section.
To make all singly connected lists y iy (where i y = 1, 2, 3,...,n y ), a loop over all
elements is involved. Inside the loop the current discrete element is added to the corre-
sponding singly connected list, as specified by its integerised coordinate i y .
To make all singly connected lists x ix,iy (where i x = 1, 2, 3,...,n x ), for a particular
value of i y , a loop over discrete elements from the corresponding y iy list is employed,
and inside the loop the current discrete element is added to the corresponding singly
connected list x ix,iy , as specified by its integerised coordinate i x .
To find a ‘new list’ y iy , a loop over all discrete elements is performed, while to find a
‘new list’ x ix,iy , a loop over discrete elements from the y iy list is performed. It is worth
noting that a loop over all y iy lists is equivalent to a single loop over all discrete elements,
because each y iy list contains only discrete elements mapped onto one row of cells, while
all y iy lists together contain all discrete element comprising the combined finite-discrete
element problem.
At no place is a loop over cells employed; loops over discrete elements are employed
instead. Those consist of:

• Three loops over all discrete elements, i.e. loops 1, 2 and 8.
• Three loops over discrete elements from central y lists, i.e. loops 3, 5 and 6 (as explained
above, all these loops are in total equivalent to three loops over all discrete elements).
• Two loops over discrete elements from neighbouring y − 1 list, i.e. loops 4 and 7
(as explained above, all these loops are in total equivalent to two loops over all dis-
crete elements).

In total, an equivalent of eight loops over all discrete elements is performed. Operations
performed inside the loops do not depend upon either the number of cells in the x-
direction n x , or the number of cells in the y-direction n y . This leads to the conclusion