Page 91 - The Combined Finite-Discrete Element Method

74 CONTACT DETECTION

total number of discrete elements and is, for instance, said to be proportional to the total
number of discrete elements, i.e.
T ∝ N (3.2)

or proportional to
T ∝ N 2 (3.3)
or
T ∝ N log N (3.4)
2
This expression means that the total CPU time necessary to perform contact detection
will simply double if the size of the problem doubles, (equation (3.2)), or that doubling
the size of the problem means that CPU time will increase four times, (equation (3.3)).
For instance, if the size of the combined finite-discrete element problem changes from
two discrete elements to 2,000,000 discrete elements, the total CPU time according to
equation (3.4) would increase 20,000,000 times. Thus, if the contact detection algorithm
is less CPU efficient, the total CPU time may increase much faster than the size of
the problem, making very large scale problems unaffordable in terms of either available
hardware performance or hardware cost and affordability.
Routine combined finite-discrete element problems may involve millions of interacting
discrete elements, and in these the ideal situation is the total CPU time being proportional
to the total number of discrete elements, as indicated by equation (3.2). Contact detection
algorithms for which equation (3.2) applies are in general classified as linear contact
detection algorithms, meaning that CPU time is a linear function of the size of the problem.
Examples of linear contact detection algorithms are, for instance,

• Munjiza-NBS (No binary search) contact detection algorithm,
• Williams C-grid contact detection algorithm,
• Screening contact detection algorithm.
These algorithms have appeared relatively recently, starting with Munjiza-NBS (1995),
which was the first linear contact detection algorithm employed in the combined finite-
discrete element method.
All other contact detection algorithms are classified as nonlinear contact detection algo-
rithms, meaning that CPU time increases either slower or faster than the size of the
problem. Nonlinear contact detection algorithms are classified either as hypo-linear con-
tact detection algorithms or hyper-linear contact detection algorithms. Hyper-linear contact
detection algorithms have CPU time increasing faster than the size of the combined finite-
discrete element problem. Examples of such algorithms are

• quadratic contact detection algorithms (equation (3.3)), and
• logarithmic contact detection algorithms (equation (3.4)).
Hypo-linear algorithms should theoretically have better performance than linear contact
detection algorithms. A typical such performance would be
√
T ∝ N (3.5)

or
T ∝ N x (3.6)