Development of IRA : a shape matching algorithm, its implementation, and utility in a general off-lattice kMC kernel
Développement de l'IRA : un algorithme de shape matching, sa mise en oeuvre et son utilité dans un kMC général hors réseau
Résumé
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.
L'évolution à long terme d'un système atomique à grande échelle peut être simulée en l'approchant comme une série d'événements, également appelés sauts, à l'aide d'un algorithme de Monte Carlo cinétique (kMC). Des problèmes particuliers se posent lorsque le système à simuler ne peut être assigné à un réseau rigide et périodique. Les approches kMC hors réseau peuvent être utilisées pour surmonter cette difficulté. Pour un logiciel kMC hors réseau, les caractéristiques souhaitables sont la capacité de réutiliser efficacement les informations de son catalogue d'événements et d'être précis tout au long de la simulation. Pour permettre ces caractéristiques, une technique de comparaison structurelle est nécessaire à deux étapes de chaque simulation kMC : lors de l'identification des événements possibles, et lors de l'exécution des événements dans la simulation. Cette thèse présente le développement de la technique de comparaison structurelle nécessaire, l'algorithme IRA (Iterative Rotations and Assignments) de mise en correspondance des formes, ainsi que les détails de sa mise en œuvre et de son utilisation dans un noyau général de Monte Carlo cinétique hors réseau. En tant qu'algorithme indépendant, l'algorithme IRA est capable de résoudre le problème de correspondance de forme pour deux structures atomiques arbitrairement tournées et/ou déformées. L'algorithme IRA est basé sur l'idée de réduire l'espace de phase des rotations possibles à un ensemble de points, donnés par les vecteurs atomiques de la structure elle-même. L'algorithme itère à travers tous les points de rotation ainsi générés et sélectionne la rotation pour laquelle une fonction de distance particulière (la fonction de distance de Hausdorff) donne la valeur minimale. Pour aborder et résoudre le problème de l'affectation atomique entre deux structures atomiques, généralement appelé le Linear Assignment Problem (LAP), dans le cadre du problème de correspondance des formes, l'algorithme IRA utilise l'algorithme Constrained Shortest Distance Assignments (CShDA) également développé et présenté dans cette thèse. En raison de la capacité de CShDA à résoudre les assignations pour des structures contenant différents nombres d'atomes, l'algorithme IRA peut également être appliqué à des fragments structurels. Lorsqu'il est inséré dans la situation spécifique du logiciel kMC hors réseau, nous établissons que l'algorithme IRA est une technique de comparaison structurelle efficace, aux deux étapes critiques de la simulation kMC. En outre, l'IRA est capable d'identifier efficacement et précisément toutes les symétries des événements kMC, garantissant ainsi une exécution statistiquement correcte des directions de déplacement. L'approche kMC hors réseau utilisant l'algorithme de correspondance de forme développé ici (IRA) permet également la simulation de processus qui modifient le nombre total d'atomes dans un système, à savoir les processus d'adsorption et de désorption. Plusieurs exemples de simulations utilisant le logiciel kMC hors réseau qui incorpore les algorithmes IRA et CShDA sont discutés, ainsi que les nouveautés de notre approche. Nous discutons également des résolutions réussies et non réussies des difficultés rencontrées dans les exemples. La thèse se termine par les directions futures possibles pour le travail, y compris une approche passionnante d'apprentissage à la volée totalement indépendante pour kMC.
Origine : Version validée par le jury (STAR)