HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Development of IRA : a shape matching algorithm, its implementation, and utility in a general off-lattice kMC kernel

Miha Gunde 1
1 LAAS-M3 - Équipe Modélisation Multi-niveaux des Matériaux
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : The long-term evolution of a large-scale atomic system can be simulated by approximating it as a series of events, also called jumps, with a kinetic Monte Carlo (kMC) algorithm. Particular problems arise when the system to be simulated cannot be assigned to a rigid, periodic lattice. Off-lattice kMC approaches can be used to overcome this difficulty. For off-lattice kMC software, desirable characteristics are the ability to efficiently reuse information from its event catalogue and to be accurate throughout the simulation. To enable these characteristics, a structural comparison technique is needed at two stages of each kMC simulation step: when identifying the possible events, and when executing the events in the simulation. This thesis presents the development of the necessary structural comparison technique, the so-called Iterative Rotations and Assignments (IRA) shape matching algorithm, and details of its implementation and use within a general off-lattice kinetic Monte Carlo kernel. As an independent algorithm, the IRA algorithm is able to solve the shape matching problem for any two arbitrarily-rotated and/or distorted atomic structures. The IRA algorithm is based on the idea of reducing the phase space of possible rotations to a set of points, given by the atomic vectors of the structure itself. The algorithm iterates through all of the rotation points thus generated and selects the rotation for which a particular distance function (the Hausdorff distance function) gives the minimum value. To address and solve the problem of atomic assignment between two atomic structures, generally called the Linear Assignment Problem (LAP), within the shape matching problem, the IRA algorithm uses the Constrained Shortest Distance Assignments (CShDA) algorithm also developed and presented in this thesis. Due to the ability of CShDA to solve assignments for structures containing different numbers of atoms, the IRA algorithm can also be applied to structural fragments. When inserted into the specific situation of off-lattice kMC software, we establish that the IRA algorithm is an efficient structural comparison technique, at both critical stages of kMC simulation. In addition, IRA is able to efficiently and accurately identify all symmetries of kMC events, thus granting a statistically correct execution of the move directions. The off-lattice kMC approach using the shape matching algorithm developed here (IRA) also allows the simulation of processes which change the total number of atoms in a system, namely adsorption and desorption processes. Several examples of simulations using the off-lattice kMC software that incorporates IRA and CShDA algorithms are discussed, along with the novelties of our approach. We also discuss the successful and unsuccessful resolutions of the difficulties encountered in the examples. The thesis concludes with the possible future directions for the work, including an exciting fully independent learning-on-the-fly approach to kMC.
Complete list of metadata

Contributor : Abes Star :  Contact
Submitted on : Friday, April 8, 2022 - 11:37:36 AM
Last modification on : Monday, April 11, 2022 - 10:52:18 AM


Version validated by the jury (STAR)


  • HAL Id : tel-03635139, version 2


Miha Gunde. Development of IRA : a shape matching algorithm, its implementation, and utility in a general off-lattice kMC kernel. Atomic Physics [physics.atom-ph]. Université Paul Sabatier - Toulouse III, 2021. English. ⟨NNT : 2021TOU30132⟩. ⟨tel-03635139v2⟩



Record views


Files downloads