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{Range cores and low-rank interfaces}\label{ch:range}
2 \chapterlead{After storage and propagation have been organized, the remaining question is
3 which subspace has actually been resolved. Local ranks govern the width of
4 phase messages. Orthogonal factor updates carry that information into a small
5 core with the same nonzero spectrum when the full range has been captured.
6 An incomplete range requires an additional certificate, developed next.}
7 \section{Phase-local rank}\label{sec:final-18}
8 
9 Let \(R\) be a newly generated Krylov residual and
10 \[
11 R_h=P_hR.
12 \]
13 
14 \begin{theorem}[Minimal exact phase width]\label{claim:final-18-1}
15 Let
16 \[
17 r_h=\operatorname{rank}(R_h).
18 \]
19 Every phase-supported basis spanning \(\operatorname{range}(R_h)\) has at
20 least \(r_h\) vectors, and a rank-revealing QR or compact SVD attains exactly
21 \(r_h\).
22 \end{theorem}
23 
24 This justifies nonuniform Krylov block widths by phase. Here rank means exact
25 algebraic rank. Discarding a direction by a floating singular-value threshold
26 is an approximation and requires its own error bound.
27 
28 
29 \begin{figure}[htbp]
30 \centering
31 \includegraphics[width=\linewidth]{figures_production/figure_05_phase_local_rank.pdf}
32 \caption{The recorded six-phase ranks require widths from one through six. Pale bars show the excess capacity of a uniform width of twelve. The comparison uses the rank inventory, not a reconstructed singular-value distribution.}
33 \label{fig:phase-local-rank}
34 \end{figure}
35 
36 
37 \section{Low-rank interface messages}\label{sec:final-19}
38 
39 If an inter-phase coupling has exact factorization
40 \[
41 P_hHP_g
42 =
43 U_{hg}V_{hg}^\top
44 \]
45 of rank \(r_{hg}\), then
46 \[
47 \boxed{
48 P_hHP_gx
49 =
50 U_{hg}(V_{hg}^\top x).
51 }
52 \]
53 
54 This representation reduces storage and communication.  It does not
55 automatically reduce wall-clock time unless the factors are applied through
56 batched or fused kernels. A Python reference implementation can lose to
57 dense BLAS despite lower arithmetic and storage.
58 
59 
60 \section{Exact QR-core updates}\label{sec:final-20}
61 
62 Suppose
63 \[
64 A=QR,
65 \qquad
66 Q^\top Q=I,
67 \]
68 and append a new block \(U\).  Set
69 \[
70 C=Q^\top U,
71 \qquad
72 F=U-QC,
73 \qquad
74 F=Q_\perp R_\perp,
75 \qquad Q_\perp^\top Q_\perp=I,
76 \qquad Q^\top Q_\perp=0.
77 \]
78 Here the columns of \(Q_\perp\) form an orthonormal basis of the nonzero
79 residual range. Zero residual directions are omitted.
80 
81 \begin{theorem}[Exact QR-core update]\label{claim:final-20-1}
82 \[
83 [A,U]
84 =
85 [Q,Q_\perp]
86 \begin{pmatrix}
87 R&C\\
88 0&R_\perp
89 \end{pmatrix}.
90 \]
91 Therefore the nonzero eigenvalues of
92 \([A,U][A,U]^\top\) are exactly the nonzero eigenvalues of the small
93 core Gram, with multiplicity. If $\operatorname{range}(Q)=\operatorname{range}(A)$,
94 the compact residual update also spans exactly $\operatorname{range}([A,U])$.
95 In that case the core has full row rank and its Gram matrix has no additional
96 zero eigenvalues.
97 \end{theorem}
98 
99 \begin{proof}
100 The first block product is \(QR=A\). The second is
101 \(QC+Q_\perp R_\perp=QC+F=U\).  The stated orthogonality
102 conditions make \([Q,Q_\perp]\) an isometry on the compact core
103 space.  Left multiplication by this isometry preserves all nonzero singular
104 values of the core, and squaring them yields the nonzero Gram eigenvalues.
105 If $Q$ spans exactly the old range and $Q_\perp$ spans exactly the residual
106 range, their combined range is precisely that of the appended factor.
107 The core then has full row rank. Without this exact-range hypothesis, unused
108 basis directions can introduce zero eigenvalues into the core Gram.
109 \end{proof}
110 
111 This is useful for overlapping genomic windows and small incremental variant
112 updates.
113 
114 
115 \begin{figure}[htbp]
116 \centering
117 \includegraphics[width=\linewidth]{figures_production/figure_06_qr_core_equivalence.pdf}
118 \caption{Under the stated orthonormality hypotheses, the full updated factor and its compact core have the same nonzero singular values. The two scalar discrepancies come from the retained 128-row control with 180 initial and 37 appended columns. They are numerical checks of the identity, not a new benchmark.}
119 \label{fig:qr-core-equivalence}
120 \end{figure}
121 
122 
123 \section{Range-core spectral compression}\label{sec:final-21}
124 
125 Suppose an orthonormal basis \(Q_r\) captures the factor range:
126 \[
127 \operatorname{range}(A)\subseteq\operatorname{range}(Q_r).
128 \]
129 Then
130 \[
131 A=Q_rB,
132 \qquad
133 B=Q_r^\top A.
134 \]
135 
136 \begin{theorem}[Exact range core]\label{claim:final-21-1}
137 The nonzero eigenvalues of
138 \[
139 K=AA^\top
140 \]
141 are exactly the nonzero eigenvalues of
142 \[
143 BB^\top,
144 \]
145 with multiplicity. If $\operatorname{range}(Q_r)=\operatorname{range}(A)$,
146 then $BB^\top$ is positive definite on the core space and its entire spectrum
147 is the nonzero spectrum of $K$.
148 \end{theorem}
149 
150 \begin{proof}
151 Since $A=Q_rB$ and $Q_r^\top Q_r=I$, one has
152 $AA^\top=Q_r(BB^\top)Q_r^\top$. The map $x\mapsto Q_rx$ is an isometry
153 from the core space onto $\operatorname{range}(Q_r)$. On that range the two
154 operators are conjugate, and $AA^\top$ vanishes on its orthogonal complement.
155 Hence their nonzero eigenvalues agree with multiplicity. If the captured
156 range equals $\operatorname{range}(A)$, then $B$ has full row rank, so
157 $BB^\top$ is positive definite. Without that equality, the core may retain
158 additional zero eigenvalues.
159 \end{proof}
160 
161 
162 Thus the computational pipeline can terminate its data-streaming stage after
163 the range is captured:
164 \[
165 \boxed{
166 \text{streamed data}
167 \to
168 \text{small spectral core}
169 \to
170 \text{tail evaluation}.
171 }
172 \]
173 
174 
175 
176 \clearpage
177 \section{An exact core calculation}
178 Consider the orthonormal range basis and core factor
179 \[
180 U=\begin{pmatrix}1&0\\0&1/\sqrt2\\0&1/\sqrt2\end{pmatrix},
181 \qquad
182 B=\begin{pmatrix}1&0&1\\0&2&0\end{pmatrix},
183 \qquad A=UB.
184 \]
185 Direct multiplication gives
186 \[
187 BB^\top=\begin{pmatrix}2&0\\0&4\end{pmatrix},
188 \qquad
189 AA^\top=\begin{pmatrix}2&0&0\\0&2&2\\0&2&2\end{pmatrix}.
190 \]
191 The large operator has eigenvalues $4,2,0$. Its two-dimensional core has
192 exactly the nonzero eigenvalues $4,2$. The Gaussian quadratic form therefore
193 has the law $4Z_1^2+2Z_2^2$, whether it is computed from the full factor, the
194 full Gram matrix, or the core.
195 
196 \subsection*{Why the nonzero-spectrum qualification matters}
197 Take instead
198 \[
199 A=\begin{pmatrix}1&0\\0&0\end{pmatrix},\qquad Q_r=I_2,\qquad B=Q_r^\top A=A.
200 \]
201 The captured subspace contains the range of $A$, but is larger than that range.
202 Both Gram matrices have spectrum $\{1,0\}$. Their nonzero spectrum is
203 $\{1\}$. Thus the nonzero spectrum of $AA^\top$ cannot be identified with the
204 \emph{entire} spectrum of $BB^\top$. Choosing the compact basis
205 $Q_r=(1,0)^\top$ instead gives $B=(1,0)$ and the one-dimensional core Gram
206 $(1)$. The extra zero records an unused basis direction, not an additional
207 random contribution. This is why range containment and exact-range equality
208 have different conclusions in Theorem~\ref{claim:final-21-1}.
209 
210 The first example in this section has active rank two. It separates algebraic
211 exactness from backend coverage. The spectral reduction and analytic packet theory remain
212 valid, but the implemented directed positive-tail backend described in
213 Chapter~\ref{ch:intervals} requires active rank greater than two. Capturing a
214 range exactly does not remove a later numerical method's hypotheses.

Back to source controls

Back to COS Method