Next: 6.3 Surface Geometry Up: 6 Implementation Issues Previous: 6.1 Spatial Binning and Contents
For representing the move list required by the N-fold way[1], we chose to use a set of fixed-size arrays (since we know the maximum number of potential moves of each class). In each array, the particle IDs of all particles capable of that sort of move are stored. This allows us to choose such a particle to move with constant cost.
With the data structure for each particle, we also store a list of its move list IDs -- the location in the KMC move list that stores its particular number. This allows us to be able to delete a particle's entry without having to search the entire move list to find that particle's ID number.
To add a move, we simply tack it on to the end of the appropriate list, and increment the appropriate counter. This has a constant cost. To delete a move, we simply copy the last move on the list into its position, decrement the appropriate counter and then update the internal list of the particle whos move list entry we just moved. This is a constant time operation. If we want to delete all moves for a particle (i.e. if it desorbs or relocates), we run the delete algorithm for every move found on its move list ID lists. We can do this in constant time since particles store their own move list IDs. Thus overall, adding particles to or deleting particles from the KMC move list has a constant cost.
Chris Siefert and Molly Moore 2002