How to simulate billiards and similar systems. (English) Zbl 0716.68094

Lubachevsky, Boris D.

J. Comput. Phys. 94, No. 2, 255-283 (1991).

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.

MSC:

68U20	Simulation (MSC2010)
68Q25	Analysis of algorithms and problem complexity

Keywords:

continuous-time dynamic system

References:

[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