3 Polyphase propagation and scheduling
On this page · Permalink · Source line 1
Storage blocks say where data are held. Structural phases say where an operator can send a vector. Exact zero couplings produce finite propagation frontiers. Weak couplings produce a controlled leakage problem instead. The scheduler must distinguish those two cases and state what knowledge of the phase graph is assumed.
3.1 Polyphase structure
On this page · Permalink · Source line 7
Let the phase projectors form an orthogonal decomposition of variant space:
Thus \(P_h\) projects onto variant phase \(h\). Again set
Define the exact phase graph by
Theorem 3.1: Polyphase light cone
If the graph distance from phase \(g\) to phase \(h\) exceeds \(k\), then
Proof
Insert the projector resolution \(\sum_jP_j=I\) between successive factors of \(H\). Every nonzero term in \(P_hH^kP_g\) corresponds to a phase path of length \(k\). If no such path exists, every term vanishes.
Theorem 3.2: Streaming-polyphase composition
At Krylov depth \(k\), an exact matrix-free iteration may omit every phase outside the exact light cone. Within each active phase, arbitrary storage refinement may be used.
Proof
The light-cone theorem removes inactive phase contributions exactly. Partition-refinement invariance shows that the remaining active phase operators may be streamed through any exact subpartition.
This is the key composition law:
3.2 Certified approximate light cones
On this page · Permalink · Source line 72
The exact light-cone theorem requires literal zero phase couplings. Real LD, annotation, and feature graphs are often only approximately sparse. This section replaces exact support by a computable phasewise envelope.
Let the phase projectors be \(P_1,\ldots,P_q\), and let \(X\) be a vector or block vector. Define its phase-norm profile
and define the nonnegative phase-transfer matrix
The matrix \(\mathcal B\) records the strength of every one-step phase transfer without assuming that weak couplings vanish.
Theorem 3.3: Weighted phase-transfer envelope
For every block vector \(X\),
componentwise. Consequently, for every integer \(k\geq0\),
Proof
Using \(\sum_gP_g=I\) and submultiplicativity,
Iteration gives the power bound.
Now choose a symmetric set of retained phase blocks and define
Let
Symmetric pair retention preserves self-adjointness of \(H_0\), although the following error theorem does not require positive semidefiniteness of \(H_0\).
Theorem 3.4: Thresholded-power certificate
For every \(k\geq1\),
In particular,
Proof
Write \(E=H-H_0\). The telescoping identity gives
The block-norm matrix of \(E\) is \(\mathcal R\). Applying Theorem 3.3 successively to each term gives
The matrix telescoping identity
yields the phasewise formula. Orthogonality of the phase projectors gives
which proves the global bound.
Corollary 3.5: Certified approximate light cone
Assume \(X\) is supported on a set of start phases \(S\). If phase \(h\) is not reachable from \(S\) by a retained path of length at most \(k\), then
and
Thus an exact zero outside the retained light cone is replaced by a certified nonzero leakage budget.
Corollary 3.6: Scalar threshold law
For any induced matrix norm, let
Then
Hence weak discarded coupling produces a first-order error bound proportional to the discarded transfer norm and to the Krylov depth.
Theorem 3.7: Krylov-polynomial certificate
Let
Then
Proof
Apply Theorem 3.4 to every nonconstant power and use the triangle inequality. The constant terms cancel.
The theorem compares the same polynomial \(p\) and the same starting block \(X\) under the two operators. It therefore covers fixed polynomial filters and fixed linear combinations of Krylov powers, not only \(H^kX\). If an adaptive iteration selects different coefficients or restart vectors under \(H\) and \(H_0\), their discrepancy requires a separate bound. The fixed-polynomial certificate alone does not control that additional change.
Corollary 3.8: Certified phase pruning
If a thresholded phase graph is chosen so that
then replacing \(H^kX\) by \(H_0^kX\) incurs Frobenius error at most \(\tau\). The same statement holds for a Krylov polynomial with the certificate in Theorem 3.7.
This turns graph thresholding into an error-budget decision. A phase or interface is not discarded because it merely appears small. It is discarded only when the weighted sum of all paths using discarded couplings remains inside the requested tolerance.
3.2.1 Numerical audit
On this page · Permalink · Source line 283
The validation operator has twelve phases of width four. A block-bidiagonal factor generates a positive-definite local operator \(H_0\), and weak symmetric long-range blocks are then added to obtain \(H\). Both normalized operators remain positive definite. A three-column start block is supported in phase zero.
For depths one through eight:
every observed phase norm lay below \(\mathcal B^k\rho(X)\).
every observed thresholding error lay below \((\mathcal B^k-\mathcal B_0^k)\rho(X)\).
the largest total observed-error-to-certificate ratio was approximately \(0.669\).
A separate hard-threshold sweep retained between \(22\) and \(132\) directed off-diagonal phase blocks. Every measured depth-five error remained below its certificate. The largest observed-error-to-certificate ratio was approximately \(0.376\). Finally, a degree-four signed polynomial in \(H\) satisfied the phasewise polynomial certificate in all twelve phases, with maximum ratio approximately \(0.068\).
These computations validate the implementation and illustrate sharpness. The universal result is supplied by the preceding proofs, not by the finite test.
3.3 Certified budget-optimal phase scheduling
On this page · Permalink · Source line 312
The preceding section answers a validation question: given a retained phase operator \(H_0\), how large can the Krylov error be? This section turns that certificate into a selection rule. The goal is to remove as much phase communication as possible while remaining inside a prescribed error budget.
Let \(\mathcal E\) denote the set of undirected off-diagonal phase pairs. Because \(H\) is self-adjoint, \(\mathcal B\) is symmetric. For a phase pair \(e=\{h,g\}\) define the nonnegative matrix \(\Delta_e\) by
with every other entry zero. If \(\mathcal O\subseteq\mathcal E\) is the set of omitted pairs, define
The diagonal is always retained. The corresponding pruned operator is
Thus \(\mathcal B_{\mathcal O}\) is its block-norm transfer matrix.
For depth \(k\ge1\) and starting phase profile \(\rho_0=\rho(X)\), define the edge risk vector
and its scalar risk
Unlike the raw block norm \(\mathcal B_{hg}\), this quantity depends on the start profile and on Krylov depth.
Theorem 3.9: Edge-additive leakage majorant
For every omitted set \(\mathcal O\subseteq\mathcal E\),
componentwise. Consequently,
Proof
The first inequality in the second display is Theorem 3.4. For the transfer matrices, the exact noncommutative telescoping identity is
All matrices and \(\rho_0\) are nonnegative, and \(0\le\mathcal B_{\mathcal O}\le\mathcal B\) entrywise. Hence
Substituting
and distributing the sum gives the componentwise majorant. The final scalar bound follows from the Euclidean triangle inequality.
Corollary 3.10: Polynomial edge-risk certificate
Let
Define
Then
Thus the same scheduling machinery applies to finite Krylov combinations and polynomial filters.
Corollary 3.11: Query-invisible phase pair
If
then
Therefore a phase pair can be large in operator norm and still have zero risk for a particular finite-depth query. A magnitude-only threshold cannot represent this distinction.
3.3.1 Equal-cost optimality
On this page · Permalink · Source line 455
Suppose each retained phase pair has the same communication or scheduling cost, and fix a budget \(\tau\ge0\). Under the additive certificate, a set of omitted pairs is feasible if
Sort the risks as
Theorem 3.12: Cardinality-optimal certified pruning
Let \(r\in\{0,\ldots,N\}\) be the largest integer satisfying
Then omitting the \(r\) least-risk phase pairs is feasible, and no feasible omitted set can contain more than \(r\) pairs under the scalar additive certificate.
Proof
If \(r=N\), every candidate pair can be omitted and optimality is immediate. Otherwise, among all subsets of cardinality \(r+1\), the smallest possible sum of risks is
By maximality of \(r\), that sum exceeds \(\tau\). Hence no set of \(r+1\) omitted pairs is feasible. The prefix of length \(r\) is feasible by construction.
Optimality is relative to the scalar additive certificate, not to the actual operator error or to every tighter certificate. The exact transfer envelope can leave additional slack.
3.3.2 Exact-envelope refinement
On this page · Permalink · Source line 494
After the cardinality-optimal additive schedule is found, recomputing
may reveal unused budget. Additional pairs can then be removed one at a time, provided the exact transfer envelope remains below \(\tau\).
Proposition 3.13: Certified refinement
Any sequence of additional omissions accepted only when
remains a valid \(\tau\)-certificate for the original operator error.
The refinement rule used in the reference implementation chooses, among all currently feasible next omissions, the pair that produces the smallest increase in the exact transfer envelope. It is certified but is not claimed globally optimal.
3.3.3 Unequal communication costs
On this page · Permalink · Source line 520
Let \(c_e\ge0\) denote the communication or storage cost saved by omitting pair \(e\). Under the scalar additive certificate, the exact discrete selection problem is
This is the \(0\)–\(1\) knapsack problem. Hence unequal-cost scheduling is combinatorial in general. The implementation supplies a safe cost-to-risk greedy heuristic. Its output remains certified because it never exceeds the additive risk budget. A fractional-knapsack relaxation supplies an upper bound on the maximum possible saved cost.
3.3.4 Numerical audit
On this page · Permalink · Source line 553
The twelve-phase operator from Section 3.2 was reused at Krylov depth five. There are \(66\) undirected off-diagonal phase pairs. For error budgets \(10^{-3}\), \(2\times10^{-3}\), \(5\times10^{-3}\), and \(10^{-2}\), the additive-optimal scheduler retained respectively \(61\), \(56\), \(45\), and \(36\) pairs. Exact-envelope refinement reduced those counts further to \(58\), \(50\), \(36\), and \(30\) pairs while remaining inside budget.
In the same test, the best single global threshold on the raw block norm retained \(65\) pairs at every one of those four budgets. The difference is structural: the global threshold is blind to start phase and Krylov depth.
A separate six-phase problem contains \(15\) candidate phase pairs, so all \(2^{15}=32768\) subsets can be enumerated. At four distinct budgets, the sorted-risk scheduler matched the brute-force cardinality optimum under the additive certificate in every case. The exact-envelope greedy refinement also matched the brute-force exact-envelope optimum in cardinality for all four budgets in this finite audit. The latter agreement is empirical and is not promoted to a theorem.
For an unequal-cost eight-phase test, costs were proportional to the bytes in symmetric dense phase blocks. The cost-to-risk heuristic saved \(5408\) bytes out of a \(9472\)-byte communication proxy while using additive risk \(0.011632\) under budget \(0.012\). The fractional relaxation upper bound was \(5647.8\) bytes, placing the greedy schedule within about \(4.25\%\) of that relaxation bound on this instance.
3.4 Asynchronous double-buffer execution model
On this page · Permalink · Source line 583
The mathematical streaming identities do not require transfers and GEMMs to be serial. Consider \(B\) storage blocks. Let \(t_b\) be the transfer time for block \(b\) and \(c_b\) its device compute time.
Proposition 3.14: Ideal two-buffer pipeline
In a model with perfect asynchronous overlap, transfer of block \(b+1\) may run while block \(b\) is being processed. The serial one-buffer time is
whereas the two-buffer pipeline time is
For uniform times \(t_b=t\) and \(c_b=c\),
Proof
After the first block arrives, every interior pipeline stage finishes only when both the current computation and the next transfer have completed. Their joint stage duration is therefore the maximum of those two times. The initial transfer and final compute cannot be hidden and form the two boundary terms.
If one resident block uses \(M_{\rm block}\) bytes and all other fixed working state uses \(M_{\rm fixed}\) bytes, the corresponding memory models are
The proposition is a scheduling model, not a hardware timing claim. PCIe or NVLink contention, kernel launch overhead, synchronization, page pinning, and library workspaces can reduce realized overlap.
