Mapping from an xyz lattice to a list of moves...

[SpitValve]

ok... I don't know much computer science (more of a physicist) so I was wondering if you guys could help me a little.

Abstractly, I have a 3D array. The algorithm goes through the array and builts up a list of "moves". Each move belongs to a certain class, so there's a 2D array for the moves - the first index is the class, the 2nd index is just to fit all the different moves of that class. Each time step one of these "moves" is performed, and the big list of moves is erased and built up again.

Now, it's kinda silly to loop through the big 3D array when each move only affects at most a 5*5*3 volume around it. So I figured I could keep most of the 2D array of moves, and delete and recalculate the moves for the 5*5*3 area. I'm having a bit of trouble though figuring out how to link the two arrays well - I tried having another 3D array that stored a list of what moves originated from each point, but it didn't work very well because the indices of the moves change as you delete them...

Can anyone suggest something that would be a good set of data structures & algorithms to implement this in Fortran 90?

[bitwiseshiftleft]

I'm really confused by what you said... can you be more specific?

[SpitValve]

ok... sorry about that

The algorithm is kinetic monte carlo. I have a 3D array of atom sites, and I have to build a list of all possible moves each atom can do. Then I randomly select one move and perform it. Then I built up the list of all possible moves and so on.

It's quite intensive to loop through the whole 3D array of atom sites, so I'd like to just loop through the ones that were actually changed when the atom moved. The hard bit is how to keep track of which moves I need to delete and refresh (i.e. moves that are from sites that are close to the atom that moved last time) and which moves can be retained.

probably just confused you more meh, never mind...

[HiEv]

I'm also a bit confused, but might it make things a bit easier to turn your system inside out? Instead of taking each atom and figuring out where it can go, could you find all of the locations that could receive an atom initially, and then each time an atom moves you would only need to change the data in the area where the last atom moved from and moved to. That way you'd only need to rebuild the data for two areas instead of the whole system. This may require some complex indexing initially to prevent it from becoming equivalently difficult as your original problem though.

Of course, depending on how you need the locations stored this may not be possible. If you could give a tiny example of the data and a few of the potential movements for each it might be easier to understand. (If the atom positions are stored as integers instead of doubles/floats then it makes things easier.)

Also, if you could explain why you need to recompute the other atoms that don't move each time. Couldn't you keep the same lists for the other atoms that didn't move, and if they attempt to make an "illegal" move, simply try a different move? It should be faster to determine if a single move is "illegal" than recompute the list of all legal moves each time, right?

The best method probably also depends on whether the number of atoms is larger or smaller than the average number of possible moves for each atom. Is one of those usually larger than the other? Do all atoms technically have the same list of potential moves (ignoring "illegal" moves)? How big is the potential volume that needs to be dealt with? Is it possible for two atoms to "swap" positions?

Seems like a fun problem, but we need a bit more information.

[bitwiseshiftleft]

I think I basically get it. Since moves depend only on local information, you basically need to have a way to find all atoms near one location. If they aren't already sorted by location, you can use an oct-tree or a hash table for this. I'm not sure which is the better solution, but I bet the hash table is easier to implement.

[SpitValve]

I'm also a bit confused, but might it make things a bit easier to turn your system inside out? Instead of taking each atom and figuring out where it can go, could you find all of the locations that could receive an atom initially, and then each time an atom moves you would only need to change the data in the area where the last atom moved from and moved to. That way you'd only need to rebuild the data for two areas instead of the whole system. This may require some complex indexing initially to prevent it from becoming equivalently difficult as your original problem though.

Of course, depending on how you need the locations stored this may not be possible. If you could give a tiny example of the data and a few of the potential movements for each it might be easier to understand. (If the atom positions are stored as integers instead of doubles/floats then it makes things easier.)

Also, if you could explain why you need to recompute the other atoms that don't move each time. Couldn't you keep the same lists for the other atoms that didn't move, and if they attempt to make an "illegal" move, simply try a different move? It should be faster to determine if a single move is "illegal" than recompute the list of all legal moves each time, right?

The best method probably also depends on whether the number of atoms is larger or smaller than the average number of possible moves for each atom. Is one of those usually larger than the other? Do all atoms technically have the same list of potential moves (ignoring "illegal" moves)? How big is the potential volume that needs to be dealt with? Is it possible for two atoms to "swap" positions?

Seems like a fun problem, but we need a bit more information.

Sorry but I was trying my best not to write three pages describing the problem Guess I was a bit obscure.

Typically the number of moves is smaller than the number of atoms, as many atoms are surrounded by other atoms and aren't able to move. Adatoms (free atoms on a surface) can move to maybe 9 different nearby sites (3 of them are much more likely than the other 6 though), while an atom on the side of an island might be able to move to 2 or 3, and an atom inside the lattice can't move at all. But there are 24 different directions of move in total.

The atoms are stored in a 3D Boolean array. Atoms can only sit in sites that are properly supported by atoms in the proper places beneath it (the bottom layer is fixed btw to prevent silliness), and you can't have two atoms within 3 lattice spaces of each other, so there's a lot of empty space in the lattice. So their locations are all integers.

I think I basically get it. Since moves depend only on local information, you basically need to have a way to find all atoms near one location. If they aren't already sorted by location, you can use an oct-tree or a hash table for this. I'm not sure which is the better solution, but I bet the hash table is easier to implement.

Yep, you've got the idea of what the problem is.

So where can I read up about oct-trees and hash tables?

[HiEv]

OK, how about this, instead of your 3D array of booleans, make a 3D array of arrays of atom numbers (integers, basically making a 4D array) making your virtual volume. In other words, each 3D position holds a list of nearby atoms. The array of atom numbers only needs to be as large as the largest possible number of atoms that can be within three lattice spaces away from that position. (You could add other indexes to that array of atom numbers to indicate, for example, if that 3D position can properly support an atom or other things.) Then you will also have a second array of atoms that stores the 3D position of each atom indexed by atom number. (This array could also store other information, such as potential moves for the atom, if you wanted to.)

When you first start you fill in your atom array with the positions of each of the atoms, and then put that atom number in each of the volume array points that are within three lattice positions from that atom's position. Now, your atoms can only move into locations where their atom number is the only atom number for that position in the volume and it can be supported by the atoms below. When an atom moves, remove it from all of the points in the volume array within three lattice positions of the old position, and then re-add it to all of the lattice points within three positions from the new position. (For bonus points, just remove it from the positions that it got far enough from and just add it to the positions it got close enough too, instead of removing and re-adding it to some of the locations it was already marked for.)

So, for example (assuming a cubic lattice, for simplicity), if you have an atom #1 at X,Y,Z position 15, 15, 15, then all points within the volume that are within three lattice spaces of that point will have atom #1 in their atom array list. If atom #2 is at 20, 15, 15 then position 16, 15, 15 would only have atom #1 in its atom array list, but position 17, 15, 15 would have atoms #1 & #2 in its list. So, if position 16, 15, 15 could support atom #1 (i.e. the atoms below support it) it could move there, but it couldn't move to 17, 15, 15 because that's too close to atom #2.

Obviously this will take a lot more memory and a longer initial setup, but I think it should be really fast once it gets started.

P.S. I'm curious about the shape of your lattice. I'm having trouble creating a cohesive picture of it with your "5*5*3 volume around it" and "24 different directions of move in total" comments.

[SpitValve]

Well, I had a chat with one of the postdocs and we worked out something that should work pretty efficiently without completely gutting my code. Thanks for your input guys