12 Composition, scope, and contribution
On this page · Permalink · Source line 1
The useful synthesis is not that every decomposition commutes with every other. It is that each layer preserves a specified object or exposes a specified error. The final calculation is justified only when those objects and bounds agree at their interfaces. This chapter states the exact composition result, locates the contribution among established methods, and makes the remaining implementation boundaries explicit.
12.1 Method synthesis: composable decompositions
On this page · Permalink · Source line 8
The solver is organized around four independent decomposition axes:
This display describes the pipeline schematically, not four endomorphisms proved to commute pairwise. The precise commutation theorem below is for exact storage refinement and a fixed structural phase partition. Full range capture or residual completion preserves the nonzero spectrum exactly. A truncated packet representation instead preserves the requested tail within its explicit analytic error bound.
They answer different questions. Storage decomposition controls what is resident. Phase decomposition controls where information can propagate. Rank decomposition controls how many directions must be retained. Spectral packetization controls the cost of the final deep-tail transform. The central structural fact is that these representations can be changed independently without changing the exact operator when their respective invariance conditions are satisfied.
12.1.1 Storage-phase commutation
On this page · Permalink · Source line 39
Fix a structural phase partition
and let each phase be subdivided into arbitrary storage blocks
Let \(S\) denote this physical storage subdivision. The phase projectors \(P_h\) are defined by the structural phases, not by \(S\).
Theorem 12.1: Storage-phase commutation theorem
Let
and let \(S\) and \(S'\) be any two exact storage refinements that respect the same structural phase partition. Then:
the exact operator \(H\) is identical under \(S\) and \(S'\).
every phase coupling \(P_hHP_g\) is identical under \(S\) and \(S'\).
the exact phase graph and every \(k\)-step polyphase light cone are identical under \(S\) and \(S'\).
any exact matrix-free Krylov method applied through streamed products produces the same Krylov subspaces in exact arithmetic under \(S\) and \(S'\).
Proof
Storage refinement changes only the order and grouping of finite sums. By partition refinement invariance, the streamed products reconstruct the same \(A\), \(A^\top\), and therefore the same \(H=A^\top A\). Since each \(P_h\) is fixed by the structural phase partition, every block \(P_hHP_g\) is unchanged. The phase graph is defined only by these blocks, so its path structure and light cones are unchanged. Finally, an exact matrix-free Krylov method depends only on repeated applications of the same operator to the same starting block. Hence its generated subspaces are identical.
Corollary 12.2: Adaptive resident-block scheduler
An implementation may change resident block size at runtime, including recursive splits after an allocation failure, without changing the exact phase graph or the exact Krylov subspaces. All required storage blocks must be processed exactly, with the operator and starting block held fixed.
This separates mathematical locality from physical storage granularity. A phase may remain fixed as an LD window or annotation class while its physical representation is subdivided according to free GPU memory, scalar precision, transfer granularity, or stream count.
12.1.2 Frontier-to-I/O theorem
On this page · Permalink · Source line 96
Theorem 12.3: Exact frontier-to-I/O reduction
Suppose a validated exact phase graph of the fixed operator \(H=A^\top A\) is already supplied and the initial Krylov block is supported on a phase set \(F_0\). Keep covariate projections, weights, and structural phase metadata fixed, and assume all factor-action blocks required for the retained phase operator are available. At depth \(k\), let \(F_k\) be the graph \(k\)-neighborhood of \(F_0\). Then no storage block lying wholly in a phase outside \(F_k\) can affect the \(k\)-step Krylov vector. Such a block need not be loaded when evaluating the requested power through the restricted factor \(A_{F_k}\). Storage blocks mixing active and inactive phases require a separate refinement before this omission is valid.
Proof
For every phase \(h\notin F_k\) and every starting phase \(g\in F_0\), the polyphase light-cone theorem gives \(P_hH^kP_g=0\). Storage-phase commutation allows each active phase operator to be evaluated through arbitrary exact storage blocks. Every path of length at most \(k\) beginning in \(F_0\) stays in \(F_k\). Let \(J_F\) be the coordinate inclusion from the retained coordinates \(F=F_k\) into the full variant space. Thus \(P_F=J_FJ_F^\top\) and \(A_F=AJ_F\). The compressed operator and its ambient embedding satisfy
These identities distinguish the compressed matrix from the larger ambient matrix. Since every path of length at most \(k\) from \(F_0\) stays in \(F\),
This includes the zero output outside \(F\). Blocks wholly outside the retained phase set may therefore be omitted from the restricted factor evaluation.
The theorem turns an algebraic support statement into an execution law:
Discovery or verification of the phase graph may itself require all inputs. The theorem does not claim minimum total I/O, omission of mixed-phase blocks, or correctness for an unverified approximate graph. The scheduler is constrained by the exact operator graph rather than solely by available memory.
12.1.3 Full method stack
On this page · Permalink · Source line 147
The representation pipeline may therefore be written as
From that point the implementation has two numerical paths. Centered packets lead to an analytic error ledger evaluated in floating point. Direct evaluation of the supplied positive spectrum leads to a directed probability enclosure. The second path does not yet certify packet construction or packet arithmetic.
Three invariances make the stack composable:
storage refinement does not change the represented operator.
structural phase scheduling does not depend on physical block size.
once the spectrum or a certified spectral enclosure is obtained, the tail engine is independent of the application that produced it.
The resulting method can be aggressive during basis discovery and still return to exactness. Approximate phase pruning is controlled by query and operator budgets. Unresolved range structure is measured by trace, square-trace, and spectral-cap invariants. And when the remaining rank is small, streamed residual completion restores the exact nonzero spectrum before the final tail evaluation.
12.1.4 Method summary
On this page · Permalink · Source line 181
The resolved synthesis is
The central design principle is separation of representation from semantics: changing how an operator is stored, scheduled, compressed, or evaluated must not silently change the mathematical quadratic form. Each approximation layer therefore either carries an explicit certificate or terminates in an exact completion step.
12.2 Prior work and the contribution boundary
On this page · Permalink · Source line 205
Characteristic-function methods for quadratic forms substantially predate this engine. Imhof's 1961 paper is a foundational historical comparator [1]. Davies' Algorithm AS 155 treats linear combinations of noncentral chi-square variables with signed coefficients and an optional Gaussian term, using characteristic-function inversion and explicit truncation/integration controls [2]. Its documented difficult low-degree cases are relevant to the retained low-rank limitations here.
The Fourier-cosine representation and the use of characteristic-function values for cosine coefficients are due to Fang and Oosterlee [3]. Their formulation distinguishes finite-domain coefficients from the full characteristic-function coefficients used to approximate them. The support/folding argument above supplies the particular positive-law alias bound needed here. A general COS accuracy theorem is not inherited without checking its hypotheses.
The choice of truncation range is studied by Junike and Pankrashkin [4], and explicit mode-count bounds under stated regularity assumptions by Junike [5]. Junike and Stier develop a damped COS framework for distributional quantities and related integrals [6]. These are relevant predecessors to the support, mode, and reweighting layers. The bounds proved here are specialized to the quadratic-form transform and must be justified under their own hypotheses.
No novelty is claimed for Gaussian spectral reduction, exponential tilting, saddlepoint centering, Fourier-cosine inversion, Weyl bounds, QR updates, or out-of-core multiplication themselves. The proposed contribution is their explicit integration with independently adjustable storage, structural, range-residual, and query-specific centered spectral representations. The packet compiler in Chapter 6 is a concrete mechanism: its local CGF remainder is propagated to the requested tail functional and refined jointly with support and mode errors. The finite refinement theorem is an existence theorem, not a complexity guarantee or proof of planner optimality.
The source-attribution record supports the listed COS and Davies formulas and the Imhof bibliographic entry. It is not an exhaustive priority search. The independent Imhof-style inversion checks support accuracy on the tested heterogeneous spectra. They do not establish a universal runtime advantage over a mature Davies implementation.
12.3 Guarantee levels and scope
On this page · Permalink · Source line 248
The framework contains several different evidence levels. They are kept separate because a proved algebraic identity, a finite numerical validation, and a directed-rounding probability enclosure are different kinds of claims.
| Statement | Status | Meaning |
|---|---|---|
| Block factor and streamed-action identities | proved | Exact finite-dimensional matrix identities. Storage blocking introduces no mathematical approximation. |
| Storage-phase commutation and exact light cones | proved | Physical block refinement does not change the structural phase graph. Phases outside the exact finite-depth frontier contribute zero. |
| Approximate light-cone and pruning certificates | proved + tested | Weak discarded couplings carry explicit finite-depth transfer and operator-norm budgets. |
| Range residual and exact completion | proved + tested | The unresolved factor is measured directly. Small residual rank can be completed exactly. |
| Positive exact-spectrum tail enclosure | directed rounding + proved remainders | For rank \(>2\), the finite transform is enclosed numerically and enlarged by proved support/alias and infinite-mode bounds. |
| Accuracy-driven positive tail solver | certified / fail-closed | A result is accepted only after \(p_+/p_- - 1\le\varepsilon_{\rm requested}\) is proved. |
| Positive noncentral engine | exact reduction + tested tail solver | The Gaussian form is reduced to a deterministic shift plus positive noncentral chi-square components. |
| Signed / indefinite engine | proved reduction + analytic-ledger tests | High-rank and finite-endpoint cases passed analytic error checks. Low-rank mixed-sign forms remain limited by slow Fourier decay of the present COS certificate. |
| Binary64 factor to rigorous spectrum | implemented at moderate dimension | Candidate eigensystems are post-certified by directed-rounding orthogonality and reconstruction bounds, then propagated monotonically into the tail. The remaining issue is scalable streamed/subspace verification rather than the basic correctness theorem. |
Four implementation boundaries remain material:
The verified matrix-to-spectrum bridge is dense. Its streamed range-core and residual-completion counterparts require verified linear algebra.
Packet construction and evaluation are not implemented with directed rounding. Their analytic ledgers remain distinct from numerical enclosures.
The mixed-sign low-rank certificate is conservative. Signed and noncentral numerical paths do not inherit the positive backend's directed guarantee.
Native GPU execution and hardware transfer/compute crossover measurements are outside the supplied Python implementation and recorded benchmarks.
These are boundaries of the implementation, not hidden assumptions in the certified positive matrix-to-tail result at moderate dimension.
12.4 Conclusion
On this page · Permalink · Source line 328
The quadratic-form problem can be separated into representation, structure, spectral recovery, and tail evaluation.
At the representation level, factors can be streamed in blocks without changing the operator. At the structural level, phase graphs constrain finite-depth propagation and allow certified scheduling. At the spectral level, unresolved range structure is measured rather than guessed and can be completed exactly when its rank becomes small. At the probability level, exponential tilting and spectral packets make extreme tails computationally tractable, while directed-rounding interval arithmetic and analytic remainder bounds turn the positive exact-spectrum calculation into an explicit probability enclosure.
The resulting numerical contract is deliberately stronger than “approximately evaluate a small probability.” For the rigorous positive backend, the user supplies an accuracy requirement. Internal resolution is refined until that requirement is proved, or the solver returns an uncertified interval rather than claiming success.
The deepest retained exact control reaches
At that point the recorded accuracy-driven run reported relative multiplicative uncertainty below \(10^{-18}\). This establishes that extreme-tail depth by itself is not the limiting numerical variable. The meaningful limit is whether the complete error ledger can be made smaller than the requested tolerance.
The matrix-to-spectrum bridge closes that upstream correctness gap for moderate binary64 factors by post-certifying an otherwise untrusted candidate eigensystem. Further numerical guarantees require scalable representation and a directed implementation of packet arithmetic: carry the same enclosure through streamed range cores and residual completion without forming a full dense eigenbasis, while extending the fail-closed accuracy contract to difficult low-rank mixed-sign forms.