COS Method

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

Read this chapter with formatted equations

1 \chapter{Composition, scope, and contribution}\label{ch:synthesis}
2 \chapterlead{The useful synthesis is not that every decomposition commutes with every
3 other. It is that each layer preserves a specified object or exposes a
4 specified error. The final calculation is justified only when those objects
5 and bounds agree at their interfaces. This chapter states the exact
6 composition result, locates the contribution among established methods, and
7 makes the remaining implementation boundaries explicit.}
8 \section{Method synthesis: composable decompositions}\label{sec:final-29}
9 
10 The solver is organized around four independent decomposition axes:
11 \[
12 \boxed{
13 \mathcal D
14 =
15 \mathcal D_{\rm storage}
16 \circ
17 \mathcal D_{\rm phase}
18 \circ
19 \mathcal D_{\rm rank}
20 \circ
21 \mathcal D_{\rm spectrum}.
22 }
23 \]
24 This display describes the pipeline schematically, not four endomorphisms
25 proved to commute pairwise.  The precise commutation theorem below is for
26 exact storage refinement and a fixed structural phase partition.  Full range
27 capture or residual completion preserves the nonzero spectrum exactly. A
28 truncated packet representation instead preserves the requested tail within
29 its explicit analytic error bound.
30 
31 They answer different questions.  Storage decomposition controls what is
32 resident.  Phase decomposition controls where information can propagate.
33 Rank decomposition controls how many directions must be retained.  Spectral
34 packetization controls the cost of the final deep-tail transform.  The central
35 structural fact is that these representations can be changed independently
36 without changing the exact operator when their respective invariance
37 conditions are satisfied.
38 
39 \subsection{Storage-phase commutation}
40 
41 Fix a structural phase partition
42 \[
43 \{1,\ldots,m\}=\mathcal P_1\sqcup\cdots\sqcup\mathcal P_H
44 \]
45 and let each phase be subdivided into arbitrary storage blocks
46 \[
47 \mathcal P_h
48 =
49 J_{h1}\sqcup\cdots\sqcup J_{hB_h}.
50 \]
51 Let $S$ denote this physical storage subdivision.  The phase projectors
52 $P_h$ are defined by the structural phases, not by $S$.
53 
54 \begin{theorem}[Storage-phase commutation theorem]\label{claim:final-29-1}
55 Let
56 \[
57 A=M_XGW^{1/2},
58 \qquad H=A^\top A,
59 \]
60 and let $S$ and $S'$ be any two exact storage refinements that respect the
61 same structural phase partition.  Then:
62 \begin{enumerate}[label=(\roman*)]
63 \item the exact operator $H$ is identical under $S$ and $S'$.
64 \item every phase coupling $P_hHP_g$ is identical under $S$ and $S'$.
65 \item the exact phase graph and every $k$-step polyphase light cone are
66 identical under $S$ and $S'$.
67 \item any exact matrix-free Krylov method applied through streamed products
68 produces the same Krylov subspaces in exact arithmetic under $S$ and $S'$.
69 \end{enumerate}
70 \end{theorem}
71 
72 \begin{proof}
73 Storage refinement changes only the order and grouping of finite sums.
74 By partition refinement invariance, the streamed products reconstruct the
75 same $A$, $A^\top$, and therefore the same $H=A^\top A$.  Since each
76 $P_h$ is fixed by the structural phase partition, every block
77 $P_hHP_g$ is unchanged.  The phase graph is defined only by these blocks, so
78 its path structure and light cones are unchanged.  Finally, an exact
79 matrix-free Krylov method depends only on repeated applications of the same
80 operator to the same starting block. Hence its generated subspaces are
81 identical.
82 \end{proof}
83 
84 \begin{corollary}[Adaptive resident-block scheduler]\label{claim:final-29-2}
85 An implementation may change resident block size at runtime, including
86 recursive splits after an allocation failure, without changing the exact
87 phase graph or the exact Krylov subspaces. All required storage blocks must
88 be processed exactly, with the operator and starting block held fixed.
89 \end{corollary}
90 
91 This separates \emph{mathematical locality} from \emph{physical storage
92 granularity}.  A phase may remain fixed as an LD window or annotation class
93 while its physical representation is subdivided according to free GPU
94 memory, scalar precision, transfer granularity, or stream count.
95 
96 \subsection{Frontier-to-I/O theorem}
97 
98 \begin{theorem}[Exact frontier-to-I/O reduction]\label{claim:final-29-3}
99 Suppose a validated exact phase graph of the fixed operator $H=A^\top A$
100 is already supplied and the initial Krylov block is supported on a phase set
101 $F_0$.  Keep covariate projections, weights, and structural phase metadata
102 fixed, and assume all factor-action blocks required for the retained phase
103 operator are available.  At depth $k$, let $F_k$ be the graph
104 $k$-neighborhood of $F_0$.  Then no storage block lying wholly in a phase
105 outside $F_k$ can affect the $k$-step Krylov vector.  Such a block need not be
106 loaded when evaluating the requested power through the restricted factor
107 $A_{F_k}$.  Storage blocks mixing active and inactive phases require a
108 separate refinement before this omission is valid.
109 \end{theorem}
110 
111 \begin{proof}
112 For every phase $h\notin F_k$ and every starting phase $g\in F_0$, the
113 polyphase light-cone theorem gives $P_hH^kP_g=0$.  Storage-phase commutation
114 allows each active phase operator to be evaluated through arbitrary exact
115 storage blocks.  Every path of length at most $k$ beginning in $F_0$ stays in $F_k$.
116 Let $J_F$ be the coordinate inclusion from the retained coordinates
117 $F=F_k$ into the full variant space. Thus $P_F=J_FJ_F^\top$ and
118 $A_F=AJ_F$. The compressed operator and its ambient embedding satisfy
119 \[
120 H_F=J_F^\top HJ_F=A_F^\top A_F,
121 \qquad P_FHP_F=J_FH_FJ_F^\top.
122 \]
123 These identities distinguish the compressed matrix from the larger ambient
124 matrix. Since every path of length at most $k$ from $F_0$ stays in $F$,
125 \[
126 H^kX=J_F H_F^k J_F^\top X.
127 \]
128 This includes the zero output outside $F$. Blocks wholly outside the retained
129 phase set may therefore be omitted from the restricted factor evaluation.
130 \end{proof}
131 
132 The theorem turns an algebraic support statement into an execution law:
133 \[
134 \boxed{
135 \text{Krylov depth}
136 \longrightarrow
137 \text{reachable phases}
138 \longrightarrow
139 \text{storage blocks that must be transferred}.
140 }
141 \]
142 Discovery or verification of the phase graph may itself require all inputs.
143 The theorem does not claim minimum total I/O, omission of mixed-phase blocks,
144 or correctness for an unverified approximate graph.  The scheduler is constrained
145 by the exact operator graph rather than solely by available memory.
146 
147 \subsection{Full method stack}
148 
149 The representation pipeline may therefore be written as
150 \[
151 \boxed{\begin{aligned}
152 A
153 &\longrightarrow \text{resident storage blocks}\\
154 &\longrightarrow \text{structural phase frontier}\\
155 &\longrightarrow \text{phase-local Krylov/range core}\\
156 &\longrightarrow \text{residual moment certificate or exact completion}\\
157 &\longrightarrow \text{spectrum or verified spectral enclosure}.
158 \end{aligned}}
159 \]
160 
161 From that point the implementation has two numerical paths. Centered packets
162 lead to an analytic error ledger evaluated in floating point. Direct evaluation
163 of the supplied positive spectrum leads to a directed probability enclosure.
164 The second path does not yet certify packet construction or packet arithmetic.
165 
166 Three invariances make the stack composable:
167 \begin{enumerate}
168 \item storage refinement does not change the represented operator.
169 \item structural phase scheduling does not depend on physical block size.
170 \item once the spectrum or a certified spectral enclosure is obtained, the
171       tail engine is independent of the application that produced it.
172 \end{enumerate}
173 
174 The resulting method can be aggressive during basis discovery and still return
175 to exactness.  Approximate phase pruning is controlled by query and operator
176 budgets. Unresolved range structure is measured by trace, square-trace, and
177 spectral-cap invariants. And when the remaining rank is small, streamed
178 residual completion restores the exact nonzero spectrum before the final tail
179 evaluation.
180 
181 \subsection{Method summary}
182 
183 The resolved synthesis is
184 \[
185 \boxed{\begin{aligned}
186 &\text{exact streamed factor actions}
187 +\text{ structural light cones}
188 +\text{ certified pruning}\\
189 &+\text{ phase-local rank}
190 +\text{ residual moment certificates}
191 +\text{ exact residual completion}\\
192 &+\text{ spectral packets}
193 +\text{ log-domain extreme-tail evaluation}.
194 \end{aligned}}
195 \]
196 
197 The central design principle is separation of representation from semantics:
198 changing how an operator is stored, scheduled, compressed, or evaluated must
199 not silently change the mathematical quadratic form.  Each approximation
200 layer therefore either carries an explicit certificate or terminates in an
201 exact completion step.
202 
203 
204 
205 \section{Prior work and the contribution boundary}\label{sec:prior-work}
206 Characteristic-function methods for quadratic forms substantially predate
207 this engine.  Imhof's 1961 paper is a foundational historical comparator
208 \cite{Imhof1961}.  Davies' Algorithm AS~155 treats linear combinations of
209 noncentral chi-square variables with signed coefficients and an optional
210 Gaussian term, using characteristic-function inversion and explicit
211 truncation/integration controls \cite{Davies1980}.  Its documented difficult
212 low-degree cases are relevant to the retained low-rank limitations here.
213 
214 The Fourier-cosine representation and the use of characteristic-function
215 values for cosine coefficients are due to Fang and Oosterlee
216 \cite{FangOosterlee2008}.  Their formulation distinguishes finite-domain
217 coefficients from the full characteristic-function coefficients used to
218 approximate them.  The support/folding argument above supplies the particular
219 positive-law alias bound needed here. A general COS accuracy theorem is not
220 inherited without checking its hypotheses.
221 
222 The choice of truncation range is studied by Junike and Pankrashkin
223 \cite{JunikePankrashkin2022}, and explicit mode-count bounds under stated
224 regularity assumptions by Junike \cite{Junike2024}. Junike and Stier develop
225 a damped COS framework for distributional quantities and related integrals
226 \cite{JunikeStier2025}. These are relevant predecessors to the support,
227 mode, and reweighting layers. The bounds proved here are specialized to the
228 quadratic-form transform and must be justified under their own hypotheses.
229 
230 No novelty is claimed for Gaussian spectral reduction, exponential tilting,
231 saddlepoint centering, Fourier-cosine inversion, Weyl bounds, QR updates, or
232 out-of-core multiplication themselves.  The proposed contribution is their
233 explicit integration with independently adjustable storage, structural,
234 range-residual, and query-specific centered spectral representations.  The
235 packet compiler in Chapter~\ref{ch:packets} is a concrete mechanism: its
236 local CGF remainder is propagated to the requested tail functional and
237 refined jointly with support and mode errors.  The finite refinement theorem
238 is an existence theorem, not a complexity guarantee or proof of planner
239 optimality.
240 
241 The source-attribution record supports the listed COS and Davies formulas
242 and the Imhof bibliographic entry. It is not an exhaustive priority search.
243 The independent Imhof-style inversion checks support accuracy on the tested
244 heterogeneous spectra. They do not establish a universal runtime advantage
245 over a mature Davies implementation.
246 
247 
248 \section{Guarantee levels and scope}\label{sec:final-31}
249 
250 The framework contains several different evidence levels.  They are kept
251 separate because a proved algebraic identity, a finite numerical validation,
252 and a directed-rounding probability enclosure are different kinds of claims.
253 
254 \begin{center}
255 \small
256 \begin{tabular}{@{}P{0.30\linewidth}P{0.20\linewidth}P{0.41\linewidth}@{}}
257 \toprule
258 Statement & Status & Meaning\\
259 \midrule
260 Block factor and streamed-action identities &
261 proved &
262 Exact finite-dimensional matrix identities. Storage blocking introduces no
263 mathematical approximation.\\
264 
265 Storage-phase commutation and exact light cones &
266 proved &
267 Physical block refinement does not change the structural phase graph. Phases
268 outside the exact finite-depth frontier contribute zero.\\
269 
270 Approximate light-cone and pruning certificates &
271 proved + tested &
272 Weak discarded couplings carry explicit finite-depth transfer and
273 operator-norm budgets.\\
274 
275 Range residual and exact completion &
276 proved + tested &
277 The unresolved factor is measured directly. Small residual rank can be
278 completed exactly.\\
279 
280 Positive exact-spectrum tail enclosure &
281 directed rounding + proved remainders &
282 For rank \(>2\), the finite transform is enclosed numerically and enlarged by
283 proved support/alias and infinite-mode bounds.\\
284 
285 Accuracy-driven positive tail solver &
286 certified / fail-closed &
287 A result is accepted only after
288 \(p_+/p_- - 1\le\varepsilon_{\rm requested}\) is proved.\\
289 
290 Positive noncentral engine &
291 exact reduction + tested tail solver &
292 The Gaussian form is reduced to a deterministic shift plus positive
293 noncentral chi-square components.\\
294 
295 Signed / indefinite engine &
296 proved reduction + analytic-ledger tests &
297 High-rank and finite-endpoint cases passed analytic error checks. Low-rank mixed-sign forms
298 remain limited by slow Fourier decay of the present COS certificate.\\
299 
300 Binary64 factor to rigorous spectrum &
301 implemented at moderate dimension &
302 Candidate eigensystems are post-certified by directed-rounding orthogonality
303 and reconstruction bounds, then propagated monotonically into the tail.  The
304 remaining issue is scalable streamed/subspace verification rather than the
305 basic correctness theorem.\\
306 \bottomrule
307 \end{tabular}
308 \end{center}
309 
310 Four implementation boundaries remain material:
311 
312 \begin{enumerate}
313 \item The verified matrix-to-spectrum bridge is dense. Its streamed range-core
314 and residual-completion counterparts require verified linear algebra.
315 \item Packet construction and evaluation are not implemented with directed
316 rounding. Their analytic ledgers remain distinct from numerical enclosures.
317 \item The mixed-sign low-rank certificate is conservative. Signed and noncentral
318 numerical paths do not inherit the positive backend's directed guarantee.
319 \item Native GPU execution and hardware transfer/compute crossover measurements
320 are outside the supplied Python implementation and recorded benchmarks.
321 \end{enumerate}
322 
323 These are boundaries of the implementation, not hidden assumptions in the
324 certified positive matrix-to-tail result at moderate dimension.
325 
326 
327 
328 \section{Conclusion}\label{sec:final-32}
329 
330 The quadratic-form problem can be separated into representation, structure,
331 spectral recovery, and tail evaluation.
332 
333 At the representation level, factors can be streamed in blocks without
334 changing the operator.  At the structural level, phase graphs constrain
335 finite-depth propagation and allow certified scheduling.  At the spectral
336 level, unresolved range structure is measured rather than guessed and can be
337 completed exactly when its rank becomes small.  At the probability level,
338 exponential tilting and spectral packets make extreme tails computationally
339 tractable, while directed-rounding interval arithmetic and analytic remainder
340 bounds turn the positive exact-spectrum calculation into an explicit
341 probability enclosure.
342 
343 The resulting numerical contract is deliberately stronger than
344 ``approximately evaluate a small probability.''  For the rigorous positive
345 backend, the user supplies an accuracy requirement.  Internal resolution is
346 refined until that requirement is proved, or the solver returns an
347 uncertified interval rather than claiming success.
348 
349 The deepest retained exact control reaches
350 \[
351 p\approx10^{-5000}.
352 \]
353 At that point the recorded accuracy-driven run reported relative multiplicative
354 uncertainty below \(10^{-18}\).  This establishes that extreme-tail depth by
355 itself is not the limiting numerical variable. The meaningful limit is whether
356 the complete error ledger can be made smaller than the requested tolerance.
357 
358 The matrix-to-spectrum bridge closes that upstream correctness gap for
359 moderate binary64 factors by post-certifying an otherwise untrusted candidate
360 eigensystem.  Further numerical guarantees require scalable
361 representation and a directed implementation of packet arithmetic: carry the same enclosure through streamed range cores and
362 residual completion without forming a full dense eigenbasis, while extending
363 the fail-closed accuracy contract to difficult low-rank mixed-sign forms.
364 
365 
366 
367 

Back to source controls

Back to COS Method