Paper VIII: Sparse transfer graphs and schedules

6 Sparse transfer graphs and schedules

On this page · Permalink · Source line 946

6.1 Support under algebraic operations

On this page · Permalink · Source line 948

Theorem 6.1: Path support of powers

For every positive integer \(m\),

\[ P_\gamma A^mP_\alpha \]

is the sum over directed walks (vertices may repeat)

\[ \alpha=\alpha_0 \longrightarrow \alpha_1 \longrightarrow\cdots\longrightarrow \alpha_m=\gamma \]

in \(G_A\), with contribution

\[ A_{\alpha_m\alpha_{m-1}} \cdots A_{\alpha_1\alpha_0}. \]

If no such path exists, the block vanishes.

Read proof · Visual guide: Two routes can cancel exactly · Visual guide: Inverse reachability is still an inclusion · Read statement and proof side by side · Permalink · Source line 950 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 6.1

Insert the packet identity between every two consecutive factors of \(A\). Every nonzero term determines one path of length \(m\).

Back to statement · Read statement and proof side by side · Permalink · Source line 972 · Claim record · Lean coverage · Code · Worked examples

Corollary 6.2: Polynomial support

\[ p(z)=\sum_{j=0}^dc_jz^j, \]

then

\[ {\operatorname{supp}}(p(A)) \]

is contained in the union of the support relations of \(A^j\) for \(0\leq j\leq d\).

Read proof · Read statement and proof side by side · Permalink · Source line 976 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary 6.2

Apply Theorem 6.1 to every power in the polynomial.

Back to statement · Read statement and proof side by side · Permalink · Source line 988 · Claim record · Lean coverage · Code · Worked examples

Corollary 6.3: Acyclic transfer nilpotence

Let \(K\) contain only strict transfer blocks. If its support graph is acyclic and its longest directed path has \(h\) edges, then

\[ K^{h+1}=0. \]

Read proof · Visual guide: Two routes can cancel exactly · Visual guide: Inverse reachability is still an inclusion · Read statement and proof side by side · Permalink · Source line 992 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary 6.3

There is no directed path of length \(h+1\). Every block of \(K^{h+1}\) therefore vanishes by Theorem 6.1.

Back to statement · Read statement and proof side by side · Permalink · Source line 999 · Claim record · Lean coverage · Code · Worked examples

Composition creates possible support along directed paths. Cancellation can remove an allowed block, so the graph gives an inclusion rather than an equality.

6.2 Block triangular solves

On this page · Permalink · Source line 1010

Definition 6.4: Topological level

Let \(G\) be a directed acyclic graph. The first level contains its source vertices. Remove them. The next level contains the new sources. Continue until every vertex has been assigned.

Permalink · Source line 1012 · Claim record · Lean coverage · Code · Worked examples

Theorem 6.5: Level schedule for a triangular solve

Let \(A=D+K\) be block lower triangular after a topological ordering. Assume every diagonal block \(D_\alpha\) is invertible. The solve

\[ Ax=b \]

can be completed in one sequential stage per topological level. Blocks in the same level may be solved independently after all earlier levels are known.

Read proof · Visual guide: A solve has a dependency clock · Read statement and proof side by side · Permalink · Source line 1016 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 6.5

The equation in packet \(\beta\) is

\[ D_\beta x_\beta = b_\beta - \sum_{\alpha\to\beta}K_{\beta\alpha}x_\alpha. \]

Every predecessor of \(\beta\) lies in an earlier level. Once those values are available, \(x_\beta\) is obtained from the local solve with \(D_\beta\). Vertices in the same level have no directed edge between them, so their solves are independent.

Back to statement · Read statement and proof side by side · Permalink · Source line 1024 · Claim record · Lean coverage · Code · Worked examples

Corollary 6.6: Sequential depth

For a nonempty finite graph, the number of sequential stages in the level schedule equals one plus the length of the longest directed path. The empty graph has depth zero.

Read proof · Visual guide: A solve has a dependency clock · Read statement and proof side by side · Permalink · Source line 1036 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary 6.6

The recursive level of a vertex is one plus the largest level of its predecessors. For a nonempty graph, the largest level therefore counts the vertices on a longest path. For an empty graph, no task is scheduled and the depth is zero.

Back to statement · Read statement and proof side by side · Permalink · Source line 1040 · Claim record · Lean coverage · Code · Worked examples

Packets in the same topological level can be processed concurrently in a triangular solve.

6.3 Fill under elimination

On this page · Permalink · Source line 1051

Theorem 6.7: Inverse support lies in the transitive closure

Let \(A\) be an invertible packet operator. Reachability here includes a zero-length path from a packet to itself. If there is no directed path from packet \(\alpha\) to packet \(\beta\) in \(G_A\), then

\[ \boxed{ P_\beta A^{-1}P_\alpha=0. } \]

Read proof · Visual guide: Elimination creates new interactions · Visual guide: Inverse reachability is still an inclusion · Read statement and proof side by side · Permalink · Source line 1053 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 6.7

Let \(R\) be the set of packets reachable from \(\alpha\), including \(\alpha\), and set

\[ X_R=\bigoplus_{\gamma\in R}X_\gamma. \]

No active edge leaves \(R\), so \(AX_R\subseteq X_R\). The restriction of \(A\) to the finite dimensional space \(X_R\) is injective. It is therefore onto \(X_R\). Hence \(A^{-1}X_R\subseteq X_R\). Since \(\beta\notin R\), the stated block of \(A^{-1}\) vanishes.

Back to statement · Read statement and proof side by side · Permalink · Source line 1062 · Claim record · Lean coverage · Code · Worked examples

Proposition 6.8: Schur support inclusion

Split the packets into retained indices \(R\) and hidden indices \(H\). Suppose the hidden block \(A_{HH}\) is invertible. The retained Schur complement is

\[ S = A_{RR} - A_{RH}A_{HH}^{-1}A_{HR}. \]

A retained block \(({\beta},{\alpha})\) can be active only if it was already active in \(A_{RR}\), or if there is a directed walk from \(\alpha\) through hidden packets to \(\beta\). The internal hidden path may have length zero, so entrance and exit may use the same hidden packet.

Read proof · Visual guide: Elimination creates new interactions · Read statement and proof side by side · Permalink · Source line 1070 · Claim record · Lean coverage · Code · Worked examples

Proof of Proposition 6.8

The correction block is

\[ P_\beta A_{RH}A_{HH}^{-1}A_{HR}P_\alpha. \]

It can be nonzero only when \(A_{HR}P_\alpha\) enters a hidden packet, the inverse hidden operator connects hidden packets, and \(P_\beta A_{RH}\) exits to \(\beta\). By Theorem 6.7, the hidden inverse can connect only packets joined by a hidden directed path. Cancellation may still remove an allowed block.

Back to statement · Read statement and proof side by side · Permalink · Source line 1082 · Claim record · Lean coverage · Code · Worked examples

Sparse elimination and fill are treated systematically in [Davis2006]. The packet graph records the same structural issue at block scale.

Permalink · Source line 1090

Source and conversion record

Source SHA-256: ef616bca9291ac766d492b88f3166be4bc2b39f9ba6034dea3a4bcf2d2bf5d7f

Unsupported prose commands stop the build. The mathematical expression sequence is checked against the source, with manuscript macros expanded for display.

Conversion records

Read and explore

Proofs and implementation

About this work

Other resources