For \(q\) right-hand sides, the paper models dense application by \(2n^2q\) operations. A block-diagonal-plus-rank-\(r\) representation with equal block width \(b\) uses
These formulas count the dense block products and two thin products. They follow the manuscript convention rather than adding every scalar accumulation or index operation.
Reading the drawing
The displayed counts compare declared representations of the same operator. They are model counts rather than measured device timings.
Drawing labels and data 14 labels
Read the original labels as selectable text. Tables preserve grid relationships; other short labels are grouped compactly.
- \(n/(b+2r)\) with \(b=2,r=1\)
- 6
\(\frac{3}{2}\)
- 12
- \(3\)
- 24
- \(6\)
- 48
- \(12\)
- ambient dimension \(n\)
- Six-dimensional running operator
- dense: \(36\) scalars, \(72q\) work
- BDLR: \(24\) scalars, \(48q\) work
- ratio: \(3/2\), not a timing result
For the running example, \(n=6,b=2,r=1\). The model reduces storage from 36 to 24 scalars and application work from \(72q\) to \(48q\). For fixed \(b,r\), the ratio \(n/(b+2r)\) grows with \(n\). If the rank instead grows proportionally with dimension, that apparent advantage need not grow.
Memory is another constraint
With scalar size \(s\), the representation alone requires \(sM\) bytes. Inputs, outputs, workspace, allocator overhead, and stored indices are additional. A matrix-only capacity inequality is not a complete device-memory fit test.
For a block band of \(p\) packets and half-bandwidth \(w\), the exact active-block count is
The subtraction removes overcounted edge diagonals. The checker enumerates all addresses for \(1\le p\le6\) and every admissible \(w\), including \(w=0\) and \(w=p-1\).
Read this as
An arithmetic or storage ratio explains a representation advantage. Kernel launch cost, traffic, utilization, and conversion determine whether that advantage becomes a time advantage.