Distributed Solve

TreePartition

The result of partition_tree: an assignment of every clique-tree node to a worker, chosen so that every worker's nodes form one connected rooted subtree and the number of parent/child edges crossing between workers is the minimum possible for the resulting worker count (length(chunks) - 1 for a tree with a single root).

Fields

• owner::Vector{Int}: owner[j] is the worker id (1-based) that node j is assigned to.
• chunks::Vector{Vector{Int}}: chunks[w] lists the node ids owned by worker w. The actual worker count is length(chunks), which may exceed the requested target_workers — see partition_tree.
• cut_edges::Vector{Pair{Int,Int}}: child => parent pairs whose two endpoints are owned by different workers. Only these edges require actual cross-worker communication; every other edge in the tree is a same-worker memory read.

TreeWorkspace(L, T=Float64) -> TreeWorkspace

Preallocated scratch for repeated flat solves against a fixed CliqueTrees.Multifrontal chordal factor L with element type T. Build it once per factorization and pass it to the three-argument tree_forward_ldiv! / tree_backward_ldiv!; those methods then perform no per-solve allocation, which is what makes re-solving against a cached factor every control step (as moving targets change only the right-hand side) cheap.

The workspace caches the symbolic tree — each node's residual, separator and child lists, a postorder in which every node follows all its descendants, an offset table locating each node's separator contribution in a single flat store buffer, and a precomputed scatter map tgt that replaces the findfirst search of the recursive version — together with the reusable store, c1 and f2 numeric buffers.

WorkerFactorization

A self-contained slice of a chordal factorization, holding only the data one worker needs to run its portion of tree_forward_ldiv! / tree_backward_ldiv!: exactly the Dval/Lval entries for the nodes it owns (copied out, not aliased into the shared array — this is the data a separate process, or drone, would actually be shipped), reindexed by a fresh local Dptr/Lptr starting at 1.

Fields

• ids::Vector{Int}: the (global) node ids this worker owns, ascending.
• Dval::Vector, Lval::Vector: this worker's own copy of the diagonal and off-diagonal factor blocks, concatenated in ids order.
• Dptr::Vector{Int}, Lptr::Vector{Int}: local offsets into the arrays above, Dptr[k]:Dptr[k+1]-1 giving node ids[k]'s diagonal block.
• res::Dict{Int,Vector{Int}}, sep::Dict{Int,Vector{Int}}, chd::Dict{Int,Vector{Int}}, pnt::Dict{Int,Int}: the symbolic tree structure restricted to owned nodes (global vertex/node ids throughout, matching tree_forward_ldiv!/tree_backward_ldiv!'s own indexing).
• boundary_up::Vector{Int}: owned nodes whose parent belongs to a different worker — the forward pass must send that node's contribution out, and the backward pass must receive a value for it, over the network.
• boundary_down::Vector{Int}: owned nodes with at least one child belonging to a different worker — the mirror image of boundary_up.

distributed_tree_solve(L, b::AbstractVector, target_workers::Integer; pids=workers()) -> Vector

Solve against L (a CliqueTrees.Multifrontal chordal factorization's triangular factor) genuinely distributed across separate worker processes: partition_tree splits the clique tree into target_workers-ish chunks (see its docstring — the actual chunk count is an approximation, not exact), each worker gets its own worker_factorization slice via remotecall, and worker_forward_pass/worker_backward_pass run on each worker with RemoteChannel messages carrying exactly the cross-worker corrections. Errors if pids doesn't have enough entries for the resulting chunk count.

This function does not call addprocs itself — set up and provision worker processes first (addprocs(N; exeflags="--project=..."), then @everywhere using CellularSheaves so the worker-side functions above are loadable on every process), matching how process/cluster provisioning is the caller's decision, not this package's.

partition_tree(L, target_workers::Integer; weight=nothing) -> TreePartition

Partition the clique tree of L (a CliqueTrees.Multifrontal chordal factorization's triangular factor) into roughly target_workers connected, rooted subtrees, by a single bottom-up sweep in the tree's own postorder: each node accumulates the weight of itself plus every child not yet claimed by an earlier chunk, and is sealed off (together with everything it just accumulated) into a new chunk as soon as that running total reaches total_weight / target_workers. Every root is always sealed regardless of weight, since there is nothing above it to merge into.

weight defaults to each node's bag size (|res(j)| + |sep(j)|), a standard proxy for triangular-solve cost. Pass a custom (S, j) -> Int function to use a different cost model.

Because sealing only ever happens along an existing parent/child edge, every chunk is guaranteed connected and the resulting number of cross-worker edges (cut_edges) is provably minimal for the worker count obtained — but that worker count is only approximately target_workers (a next-fit-style approximation), and can be far short of it: a wide, shallow tree (e.g. a star sheaf) has nowhere to place an interior cut, so it collapses toward one large chunk regardless of target_workers, only fragmenting into many tiny single-node chunks once the threshold drops below a single node's weight. This is not a bug — it is the tree's own separator width limiting available parallelism, made explicit (see dear_itay.md).

tree_backward_ldiv!(L, b::AbstractVector) -> b

Solve $L^\mathsf{T} y = b$ in place — the top-down half of a symmetric solve. Unlike tree_forward_ldiv!, this pass needs no per-node store: each node only ever reads the already-finalized values at its own separator (written by an ancestor earlier in the root-to-leaves traversal) and writes only to its own residual, so the shared solution vector itself carries every message.

Calling tree_forward_ldiv! then tree_backward_ldiv! on the same b reproduces M \ b for the original factored matrix M, matching CliqueTrees.Multifrontal.ldiv!(L, ldiv!(L', b)) bit for bit.

tree_backward_ldiv!(L, b, ws::TreeWorkspace) -> b

Allocation-free backward solve Lᵀ y = b in place, reusing ws (see TreeWorkspace). Mathematically identical to the two-argument tree_backward_ldiv!. It sweeps the tree in reverse postorder (every node before its children), so a node's separator entries — which reference only already-finalized ancestor residuals — are read straight from b; no per-node store is needed, as in the recursive version.

tree_forward_ldiv!(L, b, ws::TreeWorkspace) -> b

Allocation-free forward solve L y = b in place, reusing the preallocated ws (see TreeWorkspace). Mathematically identical to the two-argument tree_forward_ldiv!; it sweeps the clique tree flat in postorder rather than by recursion, and scatters each node's contribution through the precomputed ws.tgt map instead of searching for it.

tree_forward_ldiv!(L, b::AbstractVector) -> b

Solve $L y = b$ in place, where L is the lower-triangular factor of a CliqueTrees.Multifrontal chordal factorization (ChordalCholesky or ChordalLDLt). This is the forward half of a symmetric solve — the bottom-up pass over the clique tree that condenses each supernode's local unknowns and pushes a correction up to its parent (see tree_backward_ldiv! for the top-down half).

Mathematically this reproduces CliqueTrees.Multifrontal.ldiv!(L, b) exactly; the only difference is how the intermediate per-node corrections are stored while walking the tree (indexed by node id here, versus a shared stack internally in CliqueTrees).

worker_backward_pass(wd::WorkerFactorization, y1_owned::Dict{Int,T}, bwd_channels) -> Dict{Int,T}

The backward-pass counterpart of worker_forward_pass (see tree_backward_ldiv!). y1_owned is this worker's own result from the forward pass. A node whose parent belongs to another worker blocks on take! from bwd_channels[node]; a node with a child owned elsewhere put!s its own whole bag (residual and separator both — a child's separator can reach past its immediate parent into the parent's own separator, so the residual alone is not always enough) to that child's channel once finished.

worker_factorization(L, partition::TreePartition, worker::Integer) -> WorkerFactorization

Extract the WorkerFactorization for one worker of a partition_tree result — the exact packet that worker (or drone) needs, and nothing else: its own copied slice of L's factor data plus the symbolic metadata for its owned nodes.

worker_forward_pass(wd::WorkerFactorization, b_owned::Dict{Int,T}, fwd_channels) -> Dict{Int,T}

Run the forward pass (see tree_forward_ldiv!) restricted to one worker's owned subtree. b_owned supplies the right-hand-side entries for this worker's own residual vertices only. fwd_channels is a node_id => RemoteChannel map covering every cut edge in the tree (workers only ever touch the entries for their own boundary nodes); a node whose child belongs to another worker blocks on take! from that child's channel, and a node whose own parent belongs to another worker put!s its correction there once solved. Returns this worker's solved values, keyed by global vertex id.