Learn more about our redesign on our blog. Click here for details.
 

Volume 172, Issue 2, 20 September 2001, Pages 766–807

Regular Article

Algorithms for Particle-Field Simulations with Collisions


Abstract

We develop an efficient algorithm for detecting collisions among a large number of particles moving in a velocity field, when the field itself is possibly coupled to the particle motions. We build on ideas from molecular dynamics simulations and, as a byproduct, give a literature survey of methods for hard sphere molecular dynamics. We analyze the complexity of the algorithm in detail and present several experimental results on performance which corroborate the analysis. An optimal algorithm for collision detection has cost scaling at least like the total number of collisions detected. We argue, both theoretically and experimentally, that with the appropriate parameter choice and when the number of collisions grows with the number of particles at least as fast as for billiards, the algorithm we recommend is optimal.

Abbreviations

  • collision detection algorithm

Abbreviations

  • hard sphere molecular dynamics

Abbreviations

  • complexity

Abbreviations

  • particle laden flow

Abbreviations

  • fluid suspension

Abbreviations

  • back-coupling

References

REFERENCES

    • 2
    • J. J. Erpenbeck and W. W. Wood, Molecular dynamics techniques for hard-core systems, in Statistical Mechanics B, edited by B. J. Berne, volume 6 of Modern Thoretical Chemistry, Plenum Press, New York, 1977, Ch. 1, pp. 1–40.
    • 10
    • D.-J. Kim, L. J. Guibas, and S.-Y. Shin, Fast collision detection among multiple moving spheres, in Proceedings of the Thirteenth Annual Symposium on Computational Geometry, Nice, France, 1997,ACM, Vol. 13, pp. 373–375.
    • 11
    • D.-J. Kim, L.J. Guibas, S.-Y. Shin
    • IEEE Trans. Visualization Comput. Graph, 4 (1998), p. 230

    • 12
    • P. Hontalas, B. Beckman, M. DiLoreto, L. Blume, P. Reiher, K. Sturdevant, L. V. Warren, J. Wedel, F. Wieland, and D. Jefferson, Performance of the Colliding Pucks simulation on the Time Warp operating systems (Part 1: Asynchronous behavior & sectoring), in Distributed Simulation, edited by B. Unger and R. Fujimoto, Simulation Series (SCS, 1989), Vol. 21, pp. 3–7.
    • 14
    • B. D. Lubachevsky, Simulating colliding rigid disks in parallel using bounded lag without Time Warp, in Distributed Simulation, edited by D. Nicol, Simulation Series SCS, 1990, Vol. 22, pp. 194–202.
    • 17
    • T.H. Cormen, C.E. Leiserson, R.L. Rivest
    • Introduction to Algorithms (1990)

    • 18
    • M. Dyer, Personal communication, 2000.
    • 19
    • L. Boltzmann
    • Vorlesungen über Gastheorie (1912)

    • 20
    • G.E. Uhlenbeck, G.W. Ford
    • Lectures in Statistical Mechanics, I (1963)

    • 21
    • F. Reif
    • Fundamentals of Statistical and Thermal Physics (1965)

    • 24
    • G.K. Batchelor
    • An Introduction to Fluid Dynamics (1967)

    • 25
    • A.A. Amsden, P.J. O'Rourke, T.D. Butler
    • KIVA-II: A Computer Program for Chemically Reactive Flows with Sprays (1989)

    • 26
    • Y.A. Houndonougbo, B.B. Laird, B.J. Leimkuhler
    • Mol. Phys, 98 (1999), p. 309

    • 28
    • G.I. Taylor
    • The decay of eddies in a fluid

    • Scientific Papers of G. I. Taylor,, 2 (1960), pp. 190–192

    • 30
    • J. Garcı́a-Ojalvo, J.M. Sancho
    • Noise in Spatially Extended Systems (1999)

    • 32
    • H. Sigurgeirsson, and, A. Stuart, Particles in synthetic turbulence: A random dynamical system, in preparation.
    • 33
    • G. Da Prato, J. Zabczyk
    • Stochastic equations in infinite dimensions

    • Encyclopedia of Mathematics and its Applications, 44 (1992)

    • 34
    • M. Frigo, and, S. G. Johnson, The fastest Fourier transform in the west, available at, http://www.fftw.org/.
f1

hersir@hersir.com