Implement Solid-angle Nearest Neighbors (SANN)

[bdice]

The Solid-angle Nearest Neighbors method of determining particle neighbors [1] has been used in several recent papers. We would like to implement this feature in freud so it can be compared to other analysis methods. @csadorf expressed interest in helping with this.

1. https://aip.scitation.org/doi/full/10.1063/1.4729313

Describe the solution you'd like I would build this from the next branch, which will become freud 2.0. It should be possible to build this method by using the other methods query and queryBall and increasing the number of neighbors until finding a solution of the iterative problem described in [1] above. See the two expressions below:

In particular, I think queryBall might be a lot faster than query, so if you're choosing one method to "query and expand," I would try using queryBall method internally and expand the search radius until the computed solid angle is >= 4pi.

Steps to implement:

• add a "mode" for SANN to the QueryArgs object: https://github.com/glotzerlab/freud/blob/b25c6e2455dd9e6d412f5eadd1f8f91384a91262/freud/locality.pyx#L78-L85 https://github.com/glotzerlab/freud/blob/b25c6e2455dd9e6d412f5eadd1f8f91384a91262/freud/_locality.pxd#L21-L23 https://github.com/glotzerlab/freud/blob/b25c6e2455dd9e6d412f5eadd1f8f91384a91262/cpp/locality/NeighborQuery.h#L29-L49

• add virtual method to NeighborQuery parent class https://github.com/glotzerlab/freud/blob/b25c6e2455dd9e6d412f5eadd1f8f91384a91262/cpp/locality/NeighborQuery.h#L110-L113

• add method definition to AABBQuery and LinkCell classes

Describe alternatives you've considered It might be possible to implement this in NeighborQuery directly, instead of implementing it twice in AABBQuery and LinkCell, but I'm not sure. @vyasr would have more insight on that.

Additional context Papers citing the SANN method: https://aip.scitation.org/doi/citedby/10.1063/1.4729313

[vyasr]

I suggest prototyping this in Python since all the necessary methods are exposed in the API and the performance characteristics will be the same up to a (roughly) constant factor. I agree that this should be possible to implement by calling query/queryBall. I don't immediately have a sense for which would perform better, and I suspect that it would be somewhat system dependent. I would recommend trying queryBall first since it matches their provided implementation in the supplement (just replace their call to computeVerletNeighbors code and the rest should follow the same pattern), then you can optimize as needed.

If this calculation really becomes a bottleneck you would probably want to write it as a completely separate querying method so that you could find exactly the right number of neighbors, no more, but you'd probably want to show compelling evidence for that before trying to write that iterator. Let's get the algorithmic complexity and correctness sorted out with a Python implementation since that should be relatively easy, then we can translate to C++ in the most appropriate manner.

[vyasr]

@csadorf you managed to prototype this in Python, right? Could you share that with us if you'd like someone else to take over the final implementation?

[csadorf]

@vyasr I did not forget this. I am going to share my implementation before the end of this week.

[vyasr]

Thanks!

[csadorf]

Hi! So here is my very basic implementation of SANN:

def compute_sann(distances):
    for m in range(3, len(distances)):
        R = sum(distances[:m]) / (m - 2)
        if R <= distances[m]:
            return m, R
    else:
        raise RuntimeError("Failed to converge.")

nneighbors = defaultdict(list)

with get_trajectory(job) as traj:
    for frame in tqdm(traj[len(traj)//2::50]):
        box, points = frame.configuration.box, frame.particles.position
        lc = LinkCell(box, 1.5, points)
        query = lc.queryBall(points, 1.5)
        nneighbors['ball'].extend(query.toNList().neighbor_counts)

        for point in points:
            r = [q[2] for q in lc.query(point, 20)]
            nneighbors['sann'].append(compute_sann(r[1:])[0])

I've attached a notebook where I validated my results against those presented in the paper. They are off by one, because I did not account for the fact that freud includes the particle itself in the neighbor count.

@tcmoore3 I assume this is also of interest to you.

[bdice]

@csadorf Thanks! We can add this feature if there's continued interest, it shouldn't be too tough to implement into C++ from what you shared.

[vyasr]

I'm going to close this since there hasn't been sufficient interest to make this happen. I'm happy to reopen if anyone wants to move forward with this in the future.

[vyasr]

@tommy-waltmann @csadorf's Python implementation and testing notebook might be helpful for you to use as validation or add testing in #1051.

[vyasr]

SANN was added in #1051