14 Hardware implications and exact boundaries
On this page · Visual guide: What this edition certifies · Permalink · Source line 2066
The finite results suggest a device interface with grouped block kernels, low rank contractions, packet metadata, a transfer graph scheduler, and per edge precision tags. Such an interface may reduce materialization and repeated launch work when the operator family remains closed under the chosen representation.
The exact results stop at a finite candidate tree and a declared device model. Three broader problems remain open.
A universal discovery algorithm would need to find a profitable packet structure from an arbitrary operator and data distribution. The simultaneous spectral theorem and randomized low rank approximation cover special cases only.
A universal compiler would need a controlled approximation factor when costs are nonlocal and candidate decompositions overlap. The dynamic programs in Theorem 9.4 and Theorem 9.8 do not cover that setting.
A packet native memory hierarchy would need a communication theorem for a family of operators and a specified architecture. The one pass byte model in Proposition 3.6 is not such a lower bound.
Communication lower bounds require explicit machine models [HongKung1981], [BallardDemmelHoltzSchwartz2011]. CUDA Graph behavior and kernel constraints depend on the installed CUDA platform [NVIDIA2026]. The measured results in this paper do not prove an optimal accelerator.
The article also makes no claim about the exponent of generic dense matrix multiplication. Packet algorithms answer a different question. They exploit a restricted operator class and may return a compressed output.