A recursive decomposition of an affine Tile.

A Tiling defines the structural children of a tile. Each structural child is labelled by its relationship to the parent: an Anchor child contains the parent root, while a Sibling child introduces a distinct communication root.

A lawful Tiling satisfies:

Inclusion

Every structural child is contained in its parent.

  tileRanks child `isSubsetOf` tileRanks parent
  

Structural cover

For a non-terminal parent, the structural children partition the parent ranks: their ranks are pairwise disjoint and their union is the parent.

Progress

Every structural child is strictly smaller than its parent.

  length (tileRanks child) < length (tileRanks parent)
  

Anchor preservation

An anchor child preserves the parent root.

  case relation node of
    Anchor _ -> root (tile node) == root parent
    _        -> True
  

Sibling movement

A sibling child has a distinct root from its parent.

  case relation node of
    Sibling _ -> root (tile node) /= root parent
    _         -> True
  

Partition by fixing one coordinate at a time.

BlockPartitioning finds the first non-singleton dimension. It creates one anchor child at index 0 and one sibling child for each remaining index in that dimension.

Partition by bisecting one dimension at a time.

Bisection finds the first non-singleton dimension. It keeps the lower floor(n / 2) half as the anchor and creates one sibling from the remaining upper half.

The affine dimension and starting index selected by a tiling step.

A Split records where a child tile came from inside its parent.

Relationship between a TileNode and its parent.

Relations distinguish geometry-only anchor steps from communication steps. The tree layer contracts anchor edges; sibling edges become communication edges.

A tile labelled with its relationship to a parent tile.

TileNode is the node type used by decomposition and hop trees. The relation field records how the node arises from its parent; the root node of a tree uses Root.