📐algorithm-gauss-seidel

The groupant beside algorithms/src/gauss_seidel/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

Facts

Components

Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

Model text

descriptant

Descriptant and retained epoch

Original std-only gauss_seidel implementation. Reference: Varga (1962), Matrix Iterative Analysis. No source code or fixtures were copied from the citation.

Prospective model was saved before implementation in $MOVA_DATA/runs/octopus-wave20-linear-2026-10-30/prospective.md and retained beside this source as prospective.md.

2026-10-30: bounded dense storage and fixed dependency order were selected to make costs and termination inspectable. Optimization hypothesis: reuse compact scratch buffers rather than allocate each iteration; no timing gain was measured or claimed.

All arithmetic is deterministic f64 in index order, with explicit nonfinite intermediate checks. Underflow and rounding can change real identities. No callbacks or random state. Input slices are not mutated. Size checks precede allocation; try_reserve_exact failure becomes AllocationFailed. Finite reports contain finite coordinates/residuals. No allocator-failure injection or universal conditioning analysis is supplied.

Retained observation: 405 strictly diagonally dominant manufactured 2x2 systems; exact one-sweep dependency witness; initial convergence and zero budget; scalar denominators 2..200 exposing nonzero-residual stagnation; invalid precedence; overflow; bounded divergence and n=64 diagonal solve.

model

Mathematical combiner

Intersect the accepted domain, recurrence invariants and the typed relations in models.md with partial Rust syntax and named finite observations. With A=D+L+U, x_new=(D+L)^-1(b-U*x_old). Component i uses newly written j<i and old j>i.

Cost composition: O(k*n^2) for k sweeps plus k+1 fresh residual evaluations; O(n) storage; one checked output reservation; in-place sequential sweeps. Initial residual is evaluated even at budget zero. Test modules are sibling source nodes, not implementation children. Raw source remains authoritative; source hashes and syntax projections bind the epoch but do not provide macro expansion or semantic AST.

All arithmetic is deterministic f64 in index order, with explicit nonfinite intermediate checks. Underflow and rounding can change real identities. No callbacks or random state. Input slices are not mutated. Size checks precede allocation; try_reserve_exact failure becomes AllocationFailed. Finite reports contain finite coordinates/residuals. No allocator-failure injection or universal conditioning analysis is supplied.

approximant

Forward approximant and invariant

Domain: Square 1<=n<=64 with matching rhs/initial; finite input magnitudes <=1e100, nonzero diagonal, positive finite tolerance, max_iterations<=10000. No contraction or SPD assumption is required for admission.

With A=D+L+U, x_new=(D+L)^-1(b-U*x_old). Component i uses newly written j<i and old j>i.

Cost: O(k*n^2) for k sweeps plus k+1 fresh residual evaluations; O(n) storage; one checked output reservation; in-place sequential sweeps. Initial residual is evaluated even at budget zero.

All arithmetic is deterministic f64 in index order, with explicit nonfinite intermediate checks. Underflow and rounding can change real identities. No callbacks or random state. Input slices are not mutated. Size checks precede allocation; try_reserve_exact failure becomes AllocationFailed. Finite reports contain finite coordinates/residuals. No allocator-failure injection or universal conditioning analysis is supplied.

Real equations model the intended transformation; they do not certify machine accuracy.

No executable 1/2/5/10% surrogate is attached. A residual is not a conditioning-free relative solution-error metric, whose zero-reference case would need separate treatment. No faster calibrated surrogate or universal floating error cap is claimed.

models

Typed obernant family

behavior_complement

Gauss-Seidel does not guarantee convergence for arbitrary nonzero-diagonal matrices; even bounded finite inputs can diverge. The output relation excludes Converged when the freshly measured residual exceeds tolerance. It excludes treating an unchanged iterate as an exact solution. A one-sweep witness from zero for A=[[4,1],[1,3]], b=[1,2] produces [1/4,7/12], not the simultaneous Jacobi second coordinate 2/3.

reverse_reconstruction

For fixed A,b one real sweep satisfies U*x_old=b-(D+L)*x_new. U is strictly upper triangular and singular, so compatible old iterates form a generally nonunique affine fiber; its first coordinate is unconstrained by U. A terminal report alone cannot reconstruct its iteration history.

sweep_dependency

A one-sweep witness from zero for A=[[4,1],[1,3]], b=[1,2] produces [1/4,7/12], not the simultaneous Jacobi second coordinate 2/3.

fixed_point_relation

In exact arithmetic every fixed point satisfies Ax=b because D is invertible (and D+L is invertible for sequential updates). A rounded fixed point can retain nonzero measured residual, motivating Stagnated.

termination_partition

At each iteration compute fresh ||Ax-b||_2; Converged takes precedence, then BudgetExhausted when count==budget, then Stagnated after an unchanged sweep. Thus convergence at the final allowed sweep succeeds, while simultaneous budget/stagnation is budget. Counts equal completed sweeps.

spectral_convergence

Real asymptotic convergence for all initial states requires spectral radius of the iteration matrix below one. Strict diagonal dominance is a sufficient test fixture condition, not an enforced input rule. Divergent finite iterates exhaust budget; nonfinite arithmetic returns error.

tests

Checks

cargo test -p mova-algorithms gauss_seidel::tests

405 strictly diagonally dominant manufactured 2x2 systems; exact one-sweep dependency witness; initial convergence and zero budget; scalar denominators 2..200 exposing nonzero-residual stagnation; invalid precedence; overflow; bounded divergence and n=64 diagonal solve.

Compiled production mutant must fail one_sweep_dependency_order by assertion, then byte restoration must pass the focused suite. Source fixtures are original and deterministic.

prospective

Prospective model before source changes

Five original standard-library dense algorithms. n=1..64, QR n<=m<=128, finite inputs <=1e100; stationary budget <=10000. Validate shapes/value/options before structure then allocation. Checked try_reserve buffers; no callbacks. No approximate profiles because residual is not conditioning-free solution error. All sums deterministic increasing index. Cholesky: Lij=(Aij-sum Lik Ljk)/Ljj and Lii=sqrt(Aii-sum Lik²); exact symmetry and positive encountered pivots; O(n³) work/O(n²) output; reconstruct LLᵀ to measure Frobenius residual. No claim SPD certification under rounding. Triangular solve: xi=(bi-sum Tij xj)/Tii in dependency order; reject nonzero opposite triangle and zero diagonal; O(n²)/O(n). Fresh Euclidean residual. No iteration budget applies to fixed finite loops. Householder QR: sign avoiding cancellation, normalized reflector v, R<-R-2v(vᵀR), c<-c-2v(vᵀc), back substitute. Tall least squares O(mn²), O(mn) memory. Reject exact zero encountered norm/diagonal; report fresh primal and normal-equation residual. Rank threshold deliberately absent; ill conditioning not certified. Jacobi uses old iterate for every component; Gauss-Seidel uses newest prefix, old suffix. O(kn²)/O(n), no convergence assumption; check fresh residual then budget then exact unchanged iterate; divergence overflow is explicit arithmetic error. Finite stopping never promises solution accuracy. Expected optimization is row-major bounded scratch reuse (Jacobi 2 vectors, Gauss-Seidel 1 update vector), no empirical speed claim. Tests will include exact manufactured solutions, independent products, rejection precedence, rank/pivot failures, zero budget and one-step distinctions. Mutants alter recurrence/diagonal/reflector and must fail named assertions.

validation

Validation epoch 2026-10-30

Two debug and two release library runs passed 573 tests each, including 26 native tests in this five-algorithm batch. Sorted named outcomes match in all four executions; elapsed time is intentionally excluded. Strict all-target algorithm Clippy and focused rustfmt pass.

Compiled gauss_seidel production mutant fails named assertion one_sweep_dependency_order; exact source restored and focused positive suite passes. One mutation shows finite local sensitivity, not comprehensive mutation coverage.

Receipts: $MOVA_DATA/runs/octopus-wave20-linear-2026-10-30/{debug1,debug2,release1,release2,mutant-gauss_seidel,restored-gauss_seidel}.log. Partial syntax projections are generated twice, compared byte-for-byte, then installed. Allocation failures remain unforced. No performance or universal numerical accuracy result is claimed.

This page in Markdown → https://md.groupants.elamur.ai/free/en/mova/algorithms/src/gauss_seidel/mod.rs.groupant/