Module entry 

Single-entry sublinear Neumann solver.

ADR-001 roadmap item #6 (phase-2B): compute x[i] = e_iᵀ A⁻¹ b for a diagonally-dominant A, without materialising the full x. This is the missing inner primitive for crate::contrastive::contrastive_solve_on_change to drop end-to-end to SubLinear in n.

Math

For A = D - O with D diagonal and ρ(D⁻¹O) < 1 (the strict-DD regime), the Neumann series expansion of A⁻¹ gives

  A⁻¹ = Σ_{k≥0} (D⁻¹O)^k D⁻¹
  x   = A⁻¹ b = Σ_{k≥0} y_k,    y_0 = D⁻¹b,    y_{k+1} = D⁻¹O y_k

For a single target entry x[i], we only need entries of y_k restricted to the rows reachable from i in ≤k hops through A’s row-graph — exactly the crate::closure::closure_indices primitive at depth k. So the per-iteration work is bounded by O(|closure| · branching), independent of n when the closure is small (sparse A, bounded depth).

Complexity

• Time: O(max_terms · |closure| · branching), where |closure| is the closure of {target} at depth max_terms. For sparse DD matrices with bounded degree this is o(n).
• Space: O(|closure|) for the sparse y map.
• ComplexityClass: crate::complexity::ComplexityClass::SubLinear when max_terms · branching ≪ n; widens to Linear if the closure spans the whole graph.

Correctness contract

On a strict-DD matrix with max_terms ≥ ⌈log_{1/ρ}(‖b‖∞ / ε)⌉ the returned estimate is within ε of the true x[i]. Caller picks max_terms from a spectral-radius bound; if it’s too small the tolerance check exits early when iterates fall below tolerance.

Structs

SolveSingleEntryNeumannOp

Op marker for solve_single_entry_neumann. Declares SubLinear so callers can budget against this class without running the op.

Functions

solve_single_entries_neumann

Batched variant — compute x[i] for every i in targets, sharing no per-target state. The orchestrator crate::contrastive::contrastive_solve_on_change is the natural caller: pass targets = closure_indices(matrix, &delta.indices, depth) and you get the candidate-set solution map for top-k anomaly ranking.

solve_single_entry_neumann

Compute x[i] = e_iᵀ A⁻¹ b to within tolerance using closure-restricted Neumann iteration, without materialising the full solution vector.