4 Structured packet primitives
On this page · Permalink · Source line 453
The packet representation can store different exact local operator types. This section records the finite formulas used by several measured suites. The results concern representation and arithmetic. They do not assert that one implementation is fastest at every size.
Proposition 4.1: Equal block banded count
Let \(p,b\ge1\) be integers, \(n=pb\), and let \(p=n/b\) equal packets have width \(b\). Suppose a block is active precisely when
The number of active blocks is
For \(q\) right hand sides, the modeled application cost and scalar storage are
Read proof · Visual guide: Work removed is not time measured · Read statement and proof side by side · Permalink · Source line 457 · Claim record · Lean coverage · Code · Worked examples
Proof of Proposition 4.1
The diagonal contributes \(p\) blocks. At offset \(k\), where \(1\leq k\leq w\), the upper and lower block diagonals contribute \(2(p-k)\) blocks. Therefore
The cost and storage follow from Theorem 3.1.
Back to statement · Read statement and proof side by side · Permalink · Source line 482 · Claim record · Lean coverage · Code · Worked examples
Proposition 4.2: Sparse plus low rank application
Let
where \(S\) has \(z\) stored scalar nonzeros and \(U,V\in{\mathbb C}^{n\times r}\). In the model that charges two operations per stored sparse entry and right hand side, applying \(A\) to \(q\) right hand sides costs
modeled operations and stores
scalar values, apart from sparse index metadata.
Read proof · Read statement and proof side by side · Permalink · Source line 492 · Claim record · Lean coverage · Code · Worked examples
Proof of Proposition 4.2
The sparse product costs \(2zq\). The two dense thin products cost \(2nrq\) each. The stored values are the nonzeros of \(S\) and the entries of the two factors.
Back to statement · Read statement and proof side by side · Permalink · Source line 512 · Claim record · Lean coverage · Code · Worked examples
Theorem 4.3: Circulant spectral representation
Let \(n\ge1\) be an integer and \(c\in{\mathbb C}^n\), with indices taken modulo \(n\), and define
Let \(F\) be the unitary discrete Fourier matrix
Then
The operator is determined by \(n\) scalars and can be applied through two Fourier transforms and one pointwise product.
Read proof · Visual guide: Four coefficients, four exact frequencies · Read statement and proof side by side · Permalink · Source line 516 · Claim record · Lean coverage · Code · Worked examples
Proof of Theorem 4.3
For each frequency \(k\), let
Then
The eigenvalue is \(\sqrt n(Fc)_k\). The vectors \(v^{(k)}\) are the columns of \(F^*\), which gives the formula.
Back to statement · Read statement and proof side by side · Permalink · Source line 539 · Claim record · Lean coverage · Code · Worked examples
The fast Fourier transform evaluates the two transforms in \(O(n\log n)\) arithmetic for the usual composite lengths [CooleyTukey1965]. This is an algorithmic factorization of the exact identity in Theorem 4.3.
Corollary 4.4: Toeplitz circulant embedding
Let \(n\ge1\) be an integer and \(T\in{\mathbb C}^{n\times n}\) be Toeplitz, with first column
and first row
Set
and append \(n\) zeros to \(x\in{\mathbb C}^n\). The first \(n\) entries of the circulant product \(C(g)(x,0)^T\) equal \(Tx\).
Read proof · Visual guide: Padding is part of the theorem · Read statement and proof side by side · Permalink · Source line 563 · Claim record · Lean coverage · Code · Worked examples
Proof of Corollary 4.4
For \(0\leq j<n\), the circular convolution sum separates into indices \(k\leq j\), where the coefficient is \(c_{j-k}\), and indices \(k>j\), where the wrapped coefficient is \(r_{k-j}\). The padded coordinates do not contribute. The resulting sum is exactly the \(j\)th Toeplitz row applied to \(x\).
Back to statement · Read statement and proof side by side · Permalink · Source line 582 · Claim record · Lean coverage · Code · Worked examples
Theorem 4.5: Kronecker modewise application
Let \(A\in{\mathbb C}^{m\times m}\), \(B\in{\mathbb C}^{n\times n}\), and \(X\in{\mathbb C}^{n\times m}\). With column major vectorization,
The right side has modeled cost
and stores \(n^2+m^2\) factor entries instead of \(n^2m^2\) entries.
Read proof · Visual guide: A transpose, not an adjoint · Read statement and proof side by side · Permalink · Source line 586 · Claim record · Lean coverage · Code · Worked examples
Proof of Theorem 4.5
The \((i,j)\) entry of \(BXA^T\) is
This is the coordinate formula for \((A\otimes B)\operatorname{vec}(X)\). Multiplying first by \(B\) and then by \(A^T\) gives the stated count.
Back to statement · Read statement and proof side by side · Permalink · Source line 604 · Claim record · Lean coverage · Code · Worked examples
Corollary 4.6: Equal tensor factors
For integers \(k,d\ge0\), a product of \(k\) square factors of order \(d\), acting on a tensor with \(d^k\) entries, can be applied by \(k\) modewise contractions, reusing intermediate slices, with modeled cost
and factor storage \(kd^2\).
Read proof · Visual guide: A transpose, not an adjoint · Read statement and proof side by side · Permalink · Source line 613 · Claim record · Lean coverage · Code · Worked examples
Proof of Corollary 4.6
For \(k=0\) there are no contractions and both modeled work and factor storage are zero. For \(k\ge1\), one mode has \(d^{k-1}\) fibers of length \(d\). Multiplying each fiber by a \(d\) by \(d\) matrix costs \(2d^2\), so one mode costs \(2d^{k+1}\). Sum over the \(k\) modes.
Back to statement · Read statement and proof side by side · Permalink · Source line 623 · Claim record · Lean coverage · Code · Worked examples
Theorem 4.7: Walsh Hadamard recursion
Let \(N=2^m\), and define
Then
The product \(H_Nx\) can be evaluated in exactly \(N\log_2N\) additions or subtractions through the recursion.
Read proof · Visual guide: See every butterfly value · Read statement and proof side by side · Permalink · Source line 627 · Claim record · Lean coverage · Code · Worked examples
Proof of Theorem 4.7
The orthogonality identity follows by induction from block multiplication. One recursive stage forms \(x_0+x_1\) and \(x_0-x_1\), which uses \(N\) additions or subtractions, and then applies two transforms of size \(N/2\). Thus
whose solution is \(T(N)=N\log_2N\).
Back to statement · Read statement and proof side by side · Permalink · Source line 646 · Claim record · Lean coverage · Code · Worked examples