Implement grid adapted cut-plane method

[susilehtola]

The paper on numerical integration in FHI-aims, J. Comput. Phys. 228, 8367 (2009), describes a grid adapted cut-plane method which is apparently better than the octrees currently used by GauXC.

The obvious drawback (from the algorithmic point of view) of the octree method is that the coordinate axes are given a special role as the planes determining the three planes to cut the set S. Also tying the local origin to the center of mass of S does not necessarily result in even-sized subsets Sl . Both shortcomings are relatively easy to overcome by (1) using only a single plane to cut S but adapting the orientation of the plane to S and (2) adjusting the location of the plane so that the resulting partitions are even-sized. The details are given in Algorithm 3. In Step 6 we use the same criteria as in the case of the octree method. We note that the adapted cut-plane method is a variation of a method presented in the lecture notes by Kahan [39] and closely related to ‘‘Principal Direction Divisive Partitioning” algorithm used in data mining [40].

The best method we have obtained, the adapted cut-plane method, is rather close to the theoretical optimum for our test systems, indicating a good level of heuristic approach. The octree method suffers from the tendency to generate batches with very few points leading to inefficiency and has the drawback of unnecessarily replicating the geometry of the system.