📐algorithm-lu-decomposition

The groupant beside algorithms/src/lu_decomposition/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

Partial-pivot LU with explicit permutation and fresh reconstruction

Original std-only bounded Rust. Citations are in the implementation module. This file groupant preserves the prospective model, typed excluded-output and compatible-preimage relations, independent checks and exact source binding.

Epoch 2026-10-30: 31 new named tests; complete library 724 tests passes twice debug and twice release with identical nonempty normalized outcomes. Five production mutants fail named assertions after compilation; restoration reruns pass. Strict algorithm all-target Clippy passes. No timing was performed.

Model correction: the Jacobi implementation recomputes every original-matrix eigenpair residual each round, so its actual bound is O(bn^3), stronger work than the prospective O(bn^2+n^3) sketch. This is retained as a modeling correction, not a speed claim.

Gaps: no semantic AST or macro expansion, allocator exhaustion injection, general floating error proof, or calibrated approximate profiles.

model

Mathematical combiner

Inputs: exact mod.rs, source-bound partial syntax, prospective recurrence, current forward/invariant, typed family and assertion outcomes. First validate the domain; compose ordered updates under dimension and finite-arithmetic guards; compare fresh observations with independent oracle relations. No logical implication from a finite pass to universal accuracy is allowed.

The shared helper dependency is algorithms/src/lu_decomposition/mod.rs: checked allocation, finite arithmetic, shape/control validation and vector operations. LU is the owner and the remaining modules import only crate-private helpers plus the shared public Error. Cross-file correctness still requires integration exports and tests; these leaf models do not prove wiring.

Epoch memory retains the original prospective math and its corrected Jacobi cost. Zero residual is an observed rounded equality; ambiguous preimages remain explicit.

approximant

Forward approximant and invariant

Domain: Square 1..64; finite entries with magnitude <=1e100. Exactly zero encountered pivot is SingularPivot; no pivot tolerance or conditioning certificate.

At column k select earliest maximum |Uik|. Swap U rows, permutation, and completed L prefixes. Set Lik=Uik/Ukk and Uij-=Lik*Ukj. Unit diagonal L and upper U satisfy PA=LU over reals. Compute ||LU-PA||F freshly.

Cost: O(n^3) arithmetic including reconstruction; O(n^2) owned storage and O(n) row allocations.

Validation precedence: shape/value bounds first, then control parameters, symmetry where applicable, initial vector where applicable, checked allocations, then arithmetic/encountered-pivot failures in recurrence order. No callbacks, random state, caller-input mutation or persistent effects. Checked reservations map errors to AllocationFailed; Rust panic/OOM abort outside reserved bounded production allocations are not modeled. Finite helper checks reject nonfinite intermediates; rounded underflow remains permitted. Ties and signs follow models.md.

No executable 1/2/5/10% surrogate is attached. Residual and orthogonality norms are finite observations, not generic relative solution-error certificates. A meaningful percentage profile needs a separate domain, metric, zero-reference rule and analytical or finite evidence. No benchmark, production speedup or end-to-end Mova quality gain is claimed.

models

Typed obernant family

behavior_complement

Outputs with nonunit L diagonal, nonzero strict upper L, nonzero strict lower U, or nonpermutation P are excluded by the structural relation. Successful division by an encountered zero pivot is excluded. The factor does not return a solve, determinant estimate, or rank certificate.

reverse_reconstruction

In real arithmetic (P,L,U) reconstructs A=P^T LU uniquely. Under finite rounded updates, the compatible preimage contains bounded matrices producing those factors and residual; it need not be unique. Residual alone loses all factor and permutation information. Ties in absolute pivot magnitudes choose the earliest remaining row.

pivot_tie_order

At k, rows with strictly greater magnitude replace p; equal magnitudes do not. The permutation is a deterministic ordered witness, not only a set.

prefix_swap_dependency

When p differs from k, only previous columns of L swap. Future L entries are zero, and unit diagonal stays attached to row positions. This preserves the accumulated elimination relation.

reconstruction_observation

The report recomputes all LU entries against original A indexed by P. A finite small norm is a backward-style observation, not a condition-number-independent solution bound.

shared_kernel_composition

The other four modules reuse this module's checked matrix buffers, shape validation, finite arithmetic, dot/norm, canonical initial vector and orthogonality. Helpers are private to the crate; callers establish dimensions before helper invocation. Shared Error includes variants unused by factor. Dot uses zip under equal-length caller invariant; no arbitrary mismatched-length public dot API exists.

tests

Checks

Exhaustive 625 integer 2x2 matrices compare singularity and determinant with integer ad-bc; direct pivot and later prefix-swap fixtures; scalar, tie, 64-dimensional identity, malformed/oversize/nonfinite input and checked allocation overflow.

Run cargo test -p mova-algorithms lu_decomposition::tests. Repeat debug and release outcomes. A compiled production mutant exercises a named assertion; exact source restoration must pass. Strict all-target Clippy and focused rustfmt complete static checks.

prospective

Prospective linear algebra epoch (before implementation)

Domain: finite entries bounded by 1e100, dimensions 1..64 (MGS m>=n up to 128), tolerance finite 0..1e100, iteration budgets 0..4096. Empty matrices rejected. Exact symmetry for Jacobi eigen and Lanczos. Checked reservations and finite intermediate checks; failures precede successful reports. No callbacks, randomness, mutation of caller data, timing or accuracy-cap claims.

LU: partial pivot chooses earliest maximal absolute entry; swap permutation and completed L columns. L unit lower triangular, U upper triangular; PA=LU in reals. Reject exactly zero encountered pivot. Fresh Frobenius reconstruction. O(n^3) work O(n^2) space. MGS: copy column v; sequential dot and projection against prior normalized columns; positive Rjj=norm(v); reject norm<=tolerance as dependent column. A=QR in reals, Q column orthonormal. Fresh reconstruction and orthogonality. O(mn^2), O(mn+n^2) space. Not numerical rank revelation. Jacobi eigen: repeatedly annihilate earliest largest upper offdiagonal via stable bounded angle rotation, accumulate column eigenvectors; stop by fresh original-matrix residual or budget. Return unsorted diagonal approximations and canonical signs (first largest-magnitude coordinate nonnegative). A V=V D and V^T V=I in exact converged arithmetic. O(bn^2+n^3), O(n^2). Offdiagonal decisions deterministic. Power: normalize initial vector; Rayleigh quotient and fresh norm(Ax-lambdax); check residual then budget; normalize Ax, classify zero image breakdown if encountered. Canonical signs. O(bn^2), O(n^2+n). Residual only certifies observed approximate eigenpair; no unconditional dominant eigenvalue promise (start may miss dominant eigenspace). Lanczos: symmetric three-term recurrence alpha=q^T A q, w=Aq-alphaq-beta_prevq_prev; two full MGS reorthogonalization passes against every current basis vector. Nonnegative beta=norm(w). Break down if beta<=tol, complete if n columns reached, budget otherwise. Report actual ||AQ-QT||F including terminal residual and dropped finite reorthogonalization corrections; orthogonality observed separately. O(kn^2+nk^2), O(nk). No implicit eigenvalue accuracy guarantee; beta threshold is absolute. No explicit generic 1/2/5/10% surrogates justified.

Oracles planned: exact 2x2 LU with pivot, QR on orthogonal columns and reconstruction, 2x2 symmetric analytic eigenvalues, diagonal power start/missing-component and zero budget, diagonal Lanczos full span/early invariant subspace. Boundary validation and compiled mutants for each algorithm. Repeated debug/release normalized named outcomes. No performance prediction beyond operation bounds until exclusive measurement grant.

validation

Validation epoch 2026-10-30

31 new tests (6 LU, 6 MGS, 6 Jacobi eigen, 6 power, 7 Lanczos); complete library 724 pass twice debug and twice release. Sorted nonempty test-name/outcome records agree in each mode. Strict cargo clippy -p mova-algorithms --all-targets -- -D warnings passes. Focused rustfmt passes.

Compiled mutant: permutation swap omitted; pivot_oracle assertion fails. Source restored byte-for-byte and named positive rerun passes. First exploratory LU mutation omitted the U row swap and failed by unwrap of an arithmetic error; it was not accepted as assertion evidence. The accepted LU mutation omits the permutation swap and fails assert_eq.

Receipts: $MOVA_DATA/runs/octopus-wave26-linear-2026-10-30/ contains prospective.md, debug-1/2.log, release-1/2.log, normalized records, controls.log, mutant-.log, restored-.log, clippy-verified.log, paired syntax JSON and generator log. Validation log paths are observations from this finite run, not universal certificates. No timing or allocator-exhaustion injection performed. Partial syntax is generated twice, compared exactly, then installed and SHA-bound.

Integration boundary: checking the full augmented temporary registry reports 21 diagnostics, all confined to parent algorithm-library/mova child lists and transitive source bindings that the integration owner will refresh. No new leaf diagnostics occur in that report. The full hierarchy is not yet declared valid. A single-node registry cannot validate this whole checkout because the checker discovers all sidecars.

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