Abstract
Consider a system of N identical hard spherical particles moving in a d-dimensional box and undergoing elastic, possibly multiparticle, collisions. We develop a new algorithm that recovers the precollision state from the post-collision state of the system, across a series of consecutive collisions, with essentially no memory overhead. The challenge in achieving reversibility for an n-particle collision (where, in general, n ≪ N) arises from the presence of nd - d - 1 degrees of freedom (arbitrary angles) during each collision, as well as from the complex geometrical constraints placed on the colliding particles. To reverse the collisions in a traditional simulation setting, all of the particular realizations of these degrees of freedom (angles) during the forward simulation must be tracked. This requires memory proportional to the number of collisions, which grows very fast with N and d, thereby severely limiting the de facto applicability of the scheme. This limitation is addressed here by first performing a pseudorandomization of angles, which ensures determinism in the reverse path for any values of n and d. To address the more difficult problem of geometrical and dynamic constraints, a new approach is developed which correctly samples the constrained phase space. Upon combining the pseudorandomization with correct phase space sampling, perfect reversibility of collisions is achieved, as illustrated for n ≤ 3, d = 2, and n = 2, d = 3. This result enables, for the first time, reversible simulations of elastic collisions with essentially zero memory accumulation. In principle, the approach presented here could be generalized to larger values of n. The reverse computation methodology presented here uncovers important issues of irreversibility in conventional models, and the difficulties encountered in arriving at a reversible model for one of the most basic and widely used physical system processes, namely, elastic collisions for hard spheres. Insights and solution methodologies, with regard to accurate phase space coverage with reversible random sampling proposed in this context, can help serve as models and/or starting points for other reversible simulations.
Supplemental Material
Available for Download
Supplemental movie, appendix, image and software files for, Reversible simulations of elastic collisions
- Biswas, B. and Mall, R. 1999. Reverse execution of programs. ACM SIGPLAN Not. 34, 4, 61--69. Google ScholarDigital Library
- Broadwell, J. E. 2001. Irreversibility in a reversible lattice gas. J. Stati. Phys. 103, 5--6, 1125--1136.Google ScholarCross Ref
- Carothers, C., Perumalla, K. S., and Fujimoto, R. M. 1999. Efficient optimistic parallel simulations using reverse computation. ACM Trans. Model. Comput. Simul. 9, 3, 224--253. Google ScholarDigital Library
- Cleary, P. W. and Sawley, M. L. 2002. DEM modeling of industrial granular flows: 3D case studies and the effect of particle shape on hopper discharge. Appl. Math. Model. 26, 2.Google ScholarCross Ref
- Donev, A. 2009. Asynchronous event-driven particle algorithms. Simulation 85, 4, 229--242. Google ScholarDigital Library
- Fujimoto, R. M. 1990. Optimistic approaches to parallel discrete event simulation. Trans. Soci. Comput. Simul. 7, 2, 153--191. Google ScholarDigital Library
- Haile, J. M. 1992. Molecular Dynamics Simulation: Elementary Methods. Wiley. Google ScholarDigital Library
- Hontalas, P., Beckman, B., DiLorento, M., Blume, L., Reiher, P., Sturdevant, K., Warren, L. V., Wedel J., Wieland, F., and Jefferson D. R. 1989. Performance of the colliding pucks simulation on the time warp operating system. In Distributed Simulation.Google Scholar
- Jefferson, D. R. 1985. Virtual time. ACM Trans. Prog. Lang. Syst. 7, 3, 404--425. Google ScholarDigital Library
- Jefferson, D. R, Beckman, B., Wieland, F., Blume, L., DiLorento, M., Hontalas P., Reiher, P., Sturdevant, K., Tupman, J., Wedel, J., and Younger, H. 1987. The time warp operating systems. In Proceedings of the Symposium on Operating Systems Principles, vol. 21, 77--93. Google ScholarDigital Library
- Krantz, A. T. 1996. Analysis of an efficient algorithm for the hard-sphere problem. ACM Trans. Model. Comput. Simul. 6, 3, 185--209. Google ScholarDigital Library
- L'ecuyer, P. and Andres, T. H. 1997. A random number generator based on the combination of four LCGs. In Mathematics and Computers in Simulation, 99--107. Google ScholarDigital Library
- Leff, H., and Rex, A. F. 2002. Maxwell's Demon 2: Entropy, Classical and Quantum Information. Computing. Taylor and Francis.Google Scholar
- Lubachevsky, B. D. 1991. How to simulate billiards and similar systems. J. Comput. Phys. 92, 2, 255--283. Updated version (2006) arXiv.org as arXiv:cond-mat/0503627v2. Google ScholarDigital Library
- Manivannan, D., and Singhal, M. 1996. A low-overhead recovery technique using quasi-synchronous checkpointing. In Proceedings of the IEEE International Conference on Distributed Computing Systems. 100--107. Google ScholarDigital Library
- Marin, M. 1997a. Billiards and related systems on the bulk-synchronous parallel model. In Proceedings of the 11th Workshop on Parallel and Distributed Simulation. 164--171. Google ScholarDigital Library
- Marin, M. 1997b. Event-driven hard-particle molecular dynamics using bulk-synchronous parallelism. Comput. Phys. Comm. 102, 1--3, 81--96.Google ScholarCross Ref
- Marsaglia, G. 1972. Choosing a point from surface of a sphere. Ann. Math. Stat. 43, 2, 645--646.Google ScholarCross Ref
- Marsaglia, G. 1995. Diehard battery of tests of randomness. stat.fsu.edu/pub/diehard.Google Scholar
- Miller, S., and Luding, S. 2004. Event-driven molecular dynamics in parallel. J. Comput. Phys. 193, 1, 306--316. Google ScholarDigital Library
- Perumalla, K. S. 2007. Scaling time warp-based discrete event execution to 104 processors on the blue gene supercomputer. In Proceedings of the International Conference on Computing Frontiers, 69--76. Google ScholarDigital Library
- Perumalla, K. S. and Donev, A. 2009. Perfect reversal of rejection sampling methods for first-passage-time and similar distributions. Tech. rep. TM-2009/182. Oak Ridge National Laboratory.Google Scholar
- Pharr, M., Fernando, R., and Sweeney, T. 2005. GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation. Addison-Wesley Professional. Google ScholarDigital Library
- Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 2007. Numerical Recipes: The Art of Scientific Computing. Cambridge University Press. Google ScholarDigital Library
- Ross, B. J. 1997. Running programs backwards: The logical inversion of imperative computation. J. Form. Asp. Comput. 9, 3, 331--348.Google ScholarCross Ref
- Sanders, J. and Kandrot, E. 2010. CUDA by Example: An Introduction to General-Purpose GPU Programming. Addison-Wesley Professional. Google ScholarDigital Library
- Siiria, S. and Yliruusi, J. 2007. Particle packing simulations based on Newtonian mechanics. Powder Tech. 174, 3, 82--92.Google ScholarCross Ref
- Truesdell, C. and Muncaster, R. G. 1980. Fundamentals of Maxwell's Kinetic Theory of a Simple Monatomic Gas. Academic Press.Google Scholar
- Zhao, D., Nezami, E. G., Hashash, Y. M. A., and Ghaboussi, J. 2006. Three-dimensional discrete element simulation for granular materials. Eng. Computations 23, 7, 749--770.Google ScholarCross Ref
- Zhu, H. P., Zhou, Z. Y., Yang, R. Y., and Yu, A. B. 2007. Discrete particle simulation of particulate systems: Theoretical developments. Chem. Eng. Sci. 62, 13, 3378--3396.Google ScholarCross Ref
Index Terms
- Reversible simulations of elastic collisions
Recommendations
How to find many collisions of 3-pass HAVAL
IWSEC'07: Proceedings of the Security 2nd international conference on Advances in information and computer securityThe hash function HAVAL is a well known Merkle-Damgård hash function such as MD4 and MD5. It has three variants, 3-, 4- and 5-pass HAVAL. On 3-pass HAVAL, the best known attack finds a collision pair with 27 computations of the compression function. To ...
Finding collisions for round-reduced SM3
CT-RSA'13: Proceedings of the 13th international conference on Topics in CryptologyIn this work, we provide the first security analysis of reduced SM3 regarding its collision resistance. SM3 is a Chinese hash function standard published by the Chinese Commercial Cryptography Administration Office for the use of electronic ...
Practical Collisions for EnRUPT
The EnRUPT hash functions were proposed by O’Neil, Nohl and Henzen as candidates for the SHA-3 competition, organised by NIST. The proposal contains seven concrete hash functions, each with a different digest length. We present a practical collision ...
Comments