zbMATH — the first resource for mathematics

How to simulate billiards and similar systems. (English) Zbl 0716.68094
Summary: An N-component continuous-time dynamic system is considered whose components evolve independently all the time except for discrete asynchronous instances of pairwise interactions. Examples include colliding billiard balls and combat models. A new efficient serial event- driven algorithm is described for simulating such systems. Rather than maintaining and updating the global state of the system, the algorithm tries to examine only essential events, i.e., component interactions. The algorithm uses a simple strategy for handling data: only two states are maintained for each simulated component. Fast data access in this strategy assures the practical efficiency of the algorithm. It works noticeably faster than other algorithms proposed for this model.

68U20 Simulation (MSC2010)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI arXiv
[1] Alder, B.J.; Wainwright, T.E., J. chem. phys., 31, No. 2, 459, (1959)
[2] Bashe, C.J., IBM’s early computers, (1986), MIT Press Cambridge, MA
[3] Erpenbeck, J.J.; Wood, W.W., (), 1
[4] Hontales, P.; Beckman, B., (), 3, No. 2
[5] Katzenelson, J., SIAM J. sci. statist. comput., 10, No. 4, 787, (1989)
[6] Knuth, D.E., ()
[7] Lubachevsky, B.D.; Stillinger, F.H., J. statist. phys., 60, No. 5/6, 561, (1990)
[8] \scB.D. Lubachevsky, in Proceedings, 1990 SCS Multiconference, Simulation Series (Society for Comput. Simulation, San Diego, CA, Vol. 22, No. 2, p.194
[9] Rosato, A., Phys. rev. lett., 58, No. 10, 1038, (1987)
[10] \scW. Smith, private communication.
[11] Wieland, F.; Jefferson, D., (), 255
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.