2 Exact streamed representations
On this page · Permalink · Source line 1
Large factors need not be resident all at once. The identities in this chapter separate total data size from the working set without changing the operator. A storage partition is therefore a choice about execution, not a statistical approximation. Weighted features provide a concrete construction, but every subsequent identity applies to a supplied real factor.
2.1 Weighted-feature specialization
On this page · Permalink · Source line 7
A prominent application constructs the general factor from weighted, covariate-residualized features. The sequence kernel association test (SKAT) provides one application [7], but the same formulas apply to any feature matrix with nonnegative column weights.
Let
and let \(Q_X\in\mathbb R^{n\times p}\) have orthonormal columns spanning the null-model covariates. Define
The central implementation difficulty is not the algebraic size of the model but the mismatch between the total factor size \(n\times m\) and the working memory of an accelerator. The key point of this book is that several decompositions act on different mathematical coordinates and therefore compose:
Storage blocking controls residence. Structural phases encode linkage-disequilibrium (LD) windows, annotations, frequency bands, or other coordinate groups. Krylov methods compress the operator to the rank actually requested. Spectral packets compress the final generalized-\(\chi^2\) transform.
2.2 Variant-block Gram decomposition
On this page · Permalink · Source line 62
Partition the variant indices into disjoint blocks
Let
Then
Theorem 2.1: Additive block Gram identity
Proof
Horizontal concatenation gives
The final form follows from \(A_b=M_XG_bW_b^{1/2}\) and \(M_X^\top=M_X=M_X^2\).
Remark 2.2
The theorem is exact for every partition. Block boundaries are execution parameters, not statistical parameters.
2.3 Exact streamed kernel actions
On this page · Permalink · Source line 132
Theorem 2.3: One-pass sample-space streaming action
For every block vector \(V\in\mathbb R^{n\times s}\),
Proof
Apply the additive block Gram identity to \(KV\), then associate each block product as
Algorithm 2.4: Streamed \(KV\)
Compute \(U=M_XV\).
Set \(Y=0\).
For each resident block \(b\), compute
\[ T_b=G_b^\top U, \qquad Y\leftarrow Y+G_b(W_bT_b). \]Return \(M_XY\).
Corollary 2.5: Working memory independent of total variant count
If at most \(c\) variants are resident and the block-vector width is \(s\), then the algebraic working set is
independent of total variant count \(m\).
2.4 Streamed factor actions and Golub–Kahan
On this page · Permalink · Source line 182
Let \(V\in\mathbb R^{m\times s}\) be partitioned conformally:
Theorem 2.6: Streamed \(AV\)
Theorem 2.7: Streamed \(A^\top U\)
For \(U\in\mathbb R^{n\times s}\),
Proof
Both identities follow by substituting \(A=M_XGW^{1/2}\) and partitioning the variant coordinate.
Corollary 2.8: Streaming Golub–Kahan equivalence
With the same initial state, algorithmic choices, and random draws, any exact-arithmetic algorithm whose access to \(A\) occurs only through \(AV\) and \(A^\top U\) produces the same iterates when those products are implemented by the preceding streamed formulas.
This applies directly to block Golub–Kahan bidiagonalization, matrix-free singular-value iteration, range finding, and restarted variants. The factor need not be resident.
2.5 Two-pass dual action
On this page · Permalink · Source line 234
The variant-space normal operator is
Theorem 2.9: Two-pass streamed dual action
For every \(V\in\mathbb R^{m\times s}\),
The product is evaluated exactly by a streamed pass forming \(Y=AV\in\mathbb R^{n\times s}\), followed by a second streamed pass emitting the blocks
This form is particularly natural for variant-space polyphase Krylov iterations because the right-coordinate blocks can be produced and consumed sequentially.
2.6 Two-dimensional sample/variant tiling
On this page · Permalink · Source line 261
A variant block may itself exceed device memory. Let
and partition samples into row tiles \(I_1,\ldots,I_R\).
Theorem 2.10: Two-pass residualized tile construction
Define
Then
and after \(R_b\) is known,
Consequently,
Proof
The first identity is the row-partitioned matrix product \(Q_X^\top H_b\). The second is the definition \(M_XH_b=H_b-Q_XQ_X^\top H_b\). The last identity is the corresponding sample-tile expansion of \(AA^\top\).
With sample tile height \(t\) and resident variant width \(c\), the dominant working storage, including a resident covariate tile, is
This count excludes the backing input store, completed output blocks, allocator overhead, and library workspaces.
2.7 Partition refinement and permutation invariance
On this page · Permalink · Source line 318
Theorem 2.11: Partition-refinement invariance
Let \(\mathcal J\) be any partition of the variants and let \(\mathcal J'\) refine \(\mathcal J\). Then
The analogous streamed operator action is also invariant.
Proof
Each coarse block is a disjoint union of refined blocks. Apply the additive Gram theorem within each coarse block and sum.
Corollary 2.12: Adaptive memory splitting
A runtime may recursively subdivide any block that exceeds available device memory without changing the exact operator.
Proposition 2.13: Variant permutation invariance
If the columns of \(G\) and the diagonal entries of \(W\) are permuted by the same permutation, \(K\) and every streamed sample-space action are unchanged.
2.8 Memory planning law
On this page · Permalink · Source line 359
Let \(d\) be the number of bytes per floating scalar, \(c\) the resident variant count, \(s\) the Krylov width, and \(p\) the covariate rank. Ignoring library workspace and allocator overhead, a streamed sample-space action has working memory on the order of
The full factor costs
For fixed \(n,p,s,c\),
so device memory remains bounded as total variant count grows.
| \(m\) | full factor (MiB) | streamed \(KV\) (MiB) | tiled Gram (MiB) |
|---|---|---|---|
| 10,000 | 152.6 | 16.308 | 8.555 |
| 50,000 | 762.9 | 16.308 | 8.555 |
| 100,000 | 1,525.9 | 16.308 | 8.555 |
| 500,000 | 7,629.4 | 16.308 | 8.555 |
| 1,000,000 | 15,258.8 | 16.308 | 8.555 |
2.9 The running example in three storage blocks
On this page · Permalink · Source line 420
Partition the factor of Section 1.5 into consecutive pairs of columns,
Although \(A_2=A_3\), both column groups must be counted. Their Gram contributions are
The sum is \(K\). Merging the last two blocks preserves it. Discarding \(A_3\) instead changes the operator and its probability law.
For the declared vector \(v=(1,2,-1,0)^\top\), the action can be evaluated without forming any block Gram matrix:
The symbolic check confirms both storage partitions. Every column remains represented. Dropping an operator coupling instead changes the operator and requires the error analysis developed next.