Is there any fast way to find the master dofs?


When we impose the Periodic BC, the master dofs and puppet dofs should be matched one by one.

I can easily find all the master dofs and puppet dofs using dolfinx::mesh::locate_entities_boundary and dolfinx::fem::locate_dofs_topological. But in order to find the corresponding master for each puppet dof, the easiest way I can think about is using a nest loop, as follows

for i in master_dofs
   for j in puppet_dofs
     if coordinates match

The above algorithm can be very slow when I work in 3D mesh, since there are many dofs. I also tried DOLFINX_MPC, and it turns out to be very fast, so I wonder what is the algorithm you used? Can I do locate_dofs for each coordinates one by one, is this going to be faster?


As seen in the source code: dolfinx_mpc/cpp/PeriodicConstraint.h at main · jorgensd/dolfinx_mpc · GitHub the code leverages process bounding box trees (global across all processors) and local bounding box trees, to limit the search of a degree of freedom to a sub-set of candidates, and then in turn uses the GJK algorithm to get an accurate collision (in case of point-cell collisions, you do not need GJK for point-point collision).