[ET Trac] [Einstein Toolkit] #2211: gh::regrid contains code whose runtime is quadratic in number of components

[Einstein Toolkit]

#2211: gh::regrid contains code whose runtime is quadratic in number of components
--------------------------+---------------------------------
  Reporter:  Roland Haas  |      Owner:  (none)
      Type:  defect       |     Status:  new
  Priority:  minor        |  Milestone:
 Component:  Carpet       |    Version:  development version
Resolution:               |   Keywords:
--------------------------+---------------------------------

Comment (by Erik Schnetter):

 For obvious reasons, I am in the unique position to confirm that the
 person who wrote this wasn't thinking straight. There are several
 straightforward ways to improve this code.

 1. There is no need to first calculate the intersection and then check
 whether it is empty. It is much more efficient to check whether {{{b}}}
 and {{{extent}}} are disjoint.
 2. Instead of checking whether the bounding boxes are pairwise disjoint,
 one can calculate their union, and then compare the cardinality of the
 union with the sum of the cardinality of the individual boxes. This
 algorithm has complexity {{{n * log(n)}}}.
 3. This check is most likely superfluous, as {{{dh::regrid}}}, which does
 the actual work, contains much more stringent checks. In fact, to my
 recollection, none of the {{{gh}}} consistency checks ever caught a bug.
 We could put all of them into an {{{#ifdef CARPET_DEBUG}}} clause.

-- 
Ticket URL: <https://trac.einsteintoolkit.org/ticket/2211#comment:1>
Einstein Toolkit <http://einsteintoolkit.org>
The Einstein Toolkit