More Efficient Way of Computing Neighbors in Range

[person123]

TL;DR Summary

I'm using searchrange to locate all pairs of points within a range of one another. This is done for each step of a simulation; points move gradually from one to the next. Could I use the neighbors from the previous step to speed up computation?

Hi. I have a collection of points in 3D space. I'm using MATLAB to find all pairs of points within a certain range from one another. Right now I'm using rangesearch(X,X,r), where X is the collection of points and r is the range.

These points are the locations of atoms and I am attempting to determine atomic bonds. I am doing this for every step in a simulation. Most bonds do not change from one step to the next. Would I be able to use the pairs computed from the previous step to speed up computation for the next, as opposed to rerunning rangesearch each time? Thanks.

 

[hacivat]

Would I be able to use the pairs computed from the previous step to speed up computation for the next,

I don't think so.

I am not sure what "rangesearch" does exactly but never try to compute every atom with every other atom in the simulation box. The standard way of computing a "neighbouring map" is to divide your simulation box into small regions and do a search in each small region (and also cross check with the neighbouring regions for the ones on the border.) You have to do that in each step though since atoms might be getting closer or away from each other.

You might also want to check some advanced MD simulator like LAMMPS (it is open code) to see if they implemented a clever solution using the previous step. (I doubt so though...)

 

[person123]

I am not sure what "rangesearch" does exactly but never try to compute every atom with every other atom in the simulation box. The standard way of computing a "neighbouring map" is to divide your simulation box into small regions and do a search in each small region (and also cross check with the neighbouring regions for the ones on the border.)

rangesearch uses a kd-tree algorithm, which I don't fully understand, but I think works similar to the standard way you're describing.

You might also want to check some advanced MD simulator like LAMMPS (it is open code) to see if they implemented a clever solution using the previous step. (I doubt so though...)

I'm actually using LAMMPS to run the simulation then analyzing the CFG files (they give me the atom coordinates at each frame) in MATLAB. I think the create_bonds command in LAMMPS does something similar. It seems to me like you would also rerun it each step and I assume it uses a similar approach.

 

[hacivat]

rangesearch uses a kd-tree algorithm

OK, just looked at the wikipedia page, that seems like an advanced thing. I doubt you will find something better. (I once had a graphene system with 5000 atoms and had to get the bonds, didn't know that algorithm, wrote my own code in python with the method I described, it was very quick in calculating actually. I only needed it once though.) The trick is to select the small regions like 2 - 2,5 Angstrom side cubes. Only slightly bigger than your expected bond length and also check with the neighbouring regions.