BUG: Point cell ownership algorithm will get ghost vertices wrong

[connorjward]

Consider the interval mesh partitioned between 2 processes:

           p0   |      p1
        o-----o | -----o-----o
                |

Rank 0 (p0) will see something like the following:

           p0   |   p1
        o-----o | -----o
                |

Then, on rank 0, if we want to allocate point A to a cell where A is on the ghost vertex:

           p0   |   p1
        o-----o | -----o
                |      A

we run into trouble. If p1 says that A lives inside the rightmost cell, and p0 says that it lives in the middle cell then the current approach cannot distinguish this as both points have "distance to cell" of 0, and an owning rank of 1. In this case rank 0 should drop A but will not, erroneously believing it to live in the middle cell.

To illustrate this, rank 0 sees:

           p0   |   p1
        o-----o | -----o
                |   A

Whereas rank 1 sees:

           p0   |      p1
        o-----o | -----o-----o
                |         A

https://github.com/firedrakeproject/firedrake/pull/3293 fixes this problem for vertices that touch owned and ghost cells. E.g:

           p0   |   p1
        o-----o | -----o
              B |

but for purely ghost vertices will always get this wrong.

Possible solution

I think the fix is to instead use an algorithm where each rank only tries to determine point ownership for cells that it owns and halo data can then be exchanged via PetscSections and StarForests (which are also more scalable than the current approach).

[jrmaddison]

Previously when I've used this approach this makes it difficult to tell if a point is outside the domain, or has fallen into the roundoff 'gap' between two partitions.

[connorjward]

Previously when I've used this approach this makes it difficult to tell if a point is outside the domain, or has fallen into the roundoff 'gap' between two partitions.

I was thinking that we would use the existing tolerance behaviour to eagerly claim points into owned cells that actually exist in ghost cells. Then these can be contested in a later step to find the "true" owner.