Author - Bastian Wieck
Organization - CERN-HSF
Project Name - Jet Clustering Optimizations in Fads
Repository - https://github.com/go-hep/hep
Mentors - Sebastien Binet, Emmanuel Busato
Fads is a fast detector simulation toolkit in Go used for High Energy Physics analyses. The current version is not very scalable and it takes up too much CPU. To make fads competitive a faster jet clustering strategy using Delaunay triangulation is being implemented.
Work submitted1:
predicates:
A package that handles predicates including the Incircle test and the orientation test. For the Delaunay triangulation to work properly it needs robust Incircle and Orientation tests. The decisions in these tests are based on the result of a big determinant being greater than, equal to or less than zero. Floating point imprecision adds up and can lead to a wrong decision. The math/big package provides accurate calculations, but is very slow. A little better option is the gonum.org/v1/gonum/mat package. It calculates the determinant very accurately, leading to the wrong decision only for points far away. The mat package is way faster than the big package, but still way slower than using floating operations. To optimize performance, but guarantee correct results at the same time, the upper bound of potential error in floating operations is dynamically calculated. When a determinant is within that error range to zero the mat package is used.
delaunay:
A package that computes the Delaunay triangulation of points in a 2D plane. The Delaunay triangulation is defined by one rule: No point can be inside the Circumcircle of any triangle. Points can be inserted and removed dynamically. The time complexity is O(n*ln(n)). The insertion is performed by using the Hierarchical Delaunay algorithm. When a point is inserted new triangles are created with that point. These new triangles are children of the triangle they replaced. The triangulation is turned back into a Delaunay triangulation by doing Incircle tests with the new triangles and swapping edges if necessary. To locate the triangle where a point is inserted the hierarchy is used. The children of the triangle that contains the point are recursively inspected, until a leaf triangle is reached. The removal of points is implemented by using the re-triangulate and sew method. The points surrounding the removed point are inserted into a new triangulation. Then the triangles outside the polygon formed by those points are removed. The remaining triangles are inserted into the original triangulation.
heap:
A min-heap.
The start of the integration of the Delaunay implementation into jet clustering. For the jet clustering the nearest neighbor is needed. The Delaunay implementation provides the nearest neighbor of each point and it also provides whose nearest neighbor updated due to an insertion or removal.
Commits: https://github.com/go-hep/hep/commits?author=Bastiantheone
The PR's have been also reviewed by a larger than just Go-HEP community (Gonum). The goal is to later on add the Delaunay implementation to the gonum library.
PR's: https://github.com/go-hep/hep/pulls?utf8=%E2%9C%93&q=is%3Apr%20author%3ABastiantheone%20
Work not yet tested and reviewed1:
The rest of that integration.
https://github.com/Bastiantheone/hep/commit/1c88d1eee773835a20d0764b0553009bda1172e5
Work left1:
Test and submit the commit above
Clean up and resubmit stochastic walk implementation, Voronoi implementation and Plotting. All were part of this PR: go-hep/hep#72
Performance improvement is possible by implementing low degree optimization for removal of points in Delaunay. An attempt is found in the
PR above.
Another possible performance improvement is to add a function that removes two neighbors and adds a point in between at once instead of step by step.
It would be used in fastjet after two jets recombine and create a new one.
1 As of End of GSoC Aug 29, 2017