Paper VIII: Packet Operator Algorithms, Exact Compilation, and GPU Realization

Download original file

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

Read the typeset paper

1 \vpage{29}{A complex range needs an adjoint}{THE INNER PRODUCT IS PART OF THE CONTRACT}{}
2 The earlier compact example is real. Over $\CC$, an isometry means $Q^*Q=I$, with conjugation. Take the exact Gaussian-rational factors
3 \[
4 Q_L=\mat{3/5&0\\4\mathrm i/5&0\\0&1},\qquad
5 Q_R=\mat{1&0\\0&\mathrm i},\qquad G=\diag(5,2).
6 \]
7 Their product is a genuinely complex rectangular operator:
8 \[
9 A=Q_LGQ_R^*=\mat{3&0\\4\mathrm i&0\\0&-2\mathrm i},
10 \qquad A^*A=\diag(25,4).
11 \]
12 \vfig{complex_core}
13 \head{The small calculation exposes a wrong convention}
14 The first column of $Q_L$ has Hermitian squared length $9/25+16/25=1$. Its bilinear square without conjugation is $9/25-16/25=-7/25$. Thus $Q_L^TQ_L$ is not the identity. The portable negative control replaces the adjoint by transpose and rejects the resulting isometry claim.
15 
16 Keeping the first diagonal entry of $G$ gives $A_1$ with its second column zero. The residual has squared Frobenius norm four and Gram matrix $\diag(0,4)$, hence spectral norm two. Both errors agree with the discarded core singular value. Every displayed arithmetic operation occurs in $\QQ(\mathrm i)$.
17 \head{What the finite check establishes}
18 It checks both isometries, the reconstructed ambient matrix, its Gram matrix, and the explicit rank-one residual. Global best-rank optimality still comes from the manuscript's compression and lower-bound proof; this two-column calculation is a worked instance of that argument. No existence theorem or numerical SVD routine is executed.
19 \takeaway{Conjugation preserves the complex Euclidean norm. A transpose is correct in the vectorization identity on \pagerefV{7}, but an adjoint is required for an isometric range lift.}
20 
21 \vpage{30}{Inverse reachability is still an inclusion}{A FINITE INVERSE WITH A CANCELLED ROUTE}{}
22 Reuse the signed diamond from \pagerefV{14}, now as a complete operator:
23 \[
24 A=I+K=\mat{1&0&0&0\\1&1&0&0\\1&0&1&0\\0&1&-1&1}.
25 \]
26 The two routes from coordinate zero to coordinate three cancel, so $K^2=0$. Consequently
27 \[
28 A^{-1}=I-K=\mat{1&0&0&0\\-1&1&0&0\\-1&0&1&0\\0&-1&1&1}.
29 \]
30 \vfig[.52]{inverse_closure}
31 \head{What the closure permits}
32 The directed transitive closure includes $0\to3$, because it records existence of a route rather than the signed sum of its coefficients. Nevertheless $(A^{-1})_{30}=0$. Reachability is therefore an upper envelope for inverse support, just as it is for product support.
33 
34 The portable checker computes the inverse independently by rational row elimination, compares it with $I-K$, constructs Boolean reachability, and checks every inverse entry outside that closure. It separately rejects the assertion that every reachable transfer is nonzero.
35 \head{Why the general proof is broader}
36 This example happens to have a terminating Neumann polynomial. The general finite-dimensional theorem does not require nilpotence or a small norm. For a fixed source coordinate, its reachable-coordinate subspace is invariant under $A$. If $A$ is invertible, the restricted map is injective. Equal finite domain and codomain dimensions make it surjective, so the inverse preserves the same subspace.
37 
38 The finite-dimensional and invertibility hypotheses matter. In an infinite-dimensional space, an injective restriction can fail to be onto. A singular matrix does not have an inverse whose support can be tested at all.
39 \takeaway{The inverse can never transmit outside the reachable subspace under the theorem's hypotheses. Inside that subspace, coefficient cancellation can still remove a structurally permitted interaction.}
40 
41 \vpage{31}{One tree can serve a weighted family}{SHARED COMPILATION HAS ITS OWN OBJECTIVE}{}
42 Use a tree with one root and two terminal children. There are exactly two admissible prunings: keep the root, or split into both children. All declared errors and the split overhead are zero. Their additive total costs are:
43 \begin{center}
44 \begin{tabular}{lrr}\toprule
45 Cost component & Keep & Split\\\midrule
46 Setup paid once & 4 & 2\\
47 Operator 1, per use & 2 & 8\\
48 Operator 2, per use & 7 & 2\\\bottomrule
49 \end{tabular}
50 \end{center}
51 \vfig[.45]{shared_family}
52 With reuse weights $(r_1,r_2)=(1,3)$, the aggregated objectives are
53 \[
54 J_{\rm keep}=4+2+3\cdot7=27,\qquad
55 J_{\rm split}=2+8+3\cdot2=16.
56 \]
57 The exact shared optimum is split. Operator 1 alone prefers keep on its per-use costs, while operator 2 prefers split. Choosing independently and trying to combine those decisions would not solve the declared one-pruning problem.
58 \head{A hand-computable decision threshold}
59 Fix $r_1=1$ and vary $r_2=r\ge0$. Keeping costs $6+7r$ and splitting costs $10+2r$. Splitting is strictly cheaper when $r>4/5$; its first integer reuse win is $r=1$. The checker evaluates both admissible choices for integers zero through four and checks the displayed totals at three.
60 \head{Where the common-tree proof applies}
61 The family corollary aggregates local keep costs and errors, then uses the same exact subtree recurrence. In this example, each row denotes the sum of the selected local leaf terms; it does not conceal a nonlocal discount. A setup shared by distant unrelated nodes, overlapping candidates, or a global resource constraint would need an enlarged state or a different model.
62 \takeaway{Reuse weights change the objective before compilation. Shared optimality is exact for the supplied common tree and additive family costs, rather than for an unspecified set of future workloads.}
63 
64 \vpage{32}{Safe integers can still be conservative}{QUANTIZATION AND THE SIZE OF THE BUDGET TABLE}{}
65 Let one integer unit represent $h=1/10$ of certified error. For an individual nonnegative error $e$, choosing
66 \[
67 w=\lceil e/h\rceil\qquad\text{ensures}\qquad e\le hw.
68 \]
69 Thus integer feasibility $\sum w\le B$ implies the real bound $\sum e\le hB$. This implication is checked before applying the exact option or tree recurrence.
70 \vfig{quantization}
71 \head{A false certificate and a conservative rejection}
72 For errors $(3/50,2/25)$, rounding down assigns weights $(0,0)$ although their real sum is $7/50>1/10$. Rounding up gives $(1,1)$ and correctly excludes the assignment from budget one.
73 
74 Now change the errors to $(3/50,1/50)$. Their sum is $2/25\le1/10$, but separate ceilings still give $(1,1)$. The integer model rejects a genuinely real-feasible assignment. Conservative rounding protects soundness; it need not preserve every optimum of the unquantized problem.
75 \head{Why the complexity is pseudo polynomial}
76 For a declared integer budget $B$, a table has $B+1$ possible exact-weight states. A direct merge checks at most $(B+1)^2$ state pairs. At $B=255$, this means 256 states and 65,536 candidate pairs at a merge, even though the budget fits in eight binary digits.
77 
78 With a bounded number of children, the paper's direct tree implementation therefore has quadratic budget dependence at each node. Polynomial dependence on the numerical value of $B$ does not mean polynomial dependence on the binary input length. These are counts of declared states and pairs, not measured runtimes or claims that every state is reachable.
79 \takeaway{The dynamic program is exact for its integer data. Conservative conversion and the numerical size of the budget are separate obligations that determine its accuracy and practical scale.}

Back to source controls

Back to Paper VIII: Packet Operator Algorithms, Exact Compilation, and GPU Realization