---
title: "algorithm-lu-decomposition — Mova code model"
description: "Mova code model of algorithms/src/lu_decomposition/mod.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/lu_decomposition/mod.rs.groupant/"
---
Elamur: [Mova](https://md.mova.elamur.ai/free/en/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · **Groupants**

This page as HTML: <https://groupants.elamur.ai/free/en/mova/algorithms/src/lu_decomposition/mod.rs.groupant/>

# 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

- **kind:** groupant
- **status:** partial descriptive instance
- **source:** [`algorithms/src/lu_decomposition/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/lu_decomposition/mod.rs)
- **source SHA-256:** `d6703f3c3eb740fe…`
- **repository folder:** [`algorithms/src/lu_decomposition/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/lu_decomposition/mod.rs.groupant)
- **repository commit:** `855da7bd4a7b`

> **Implementation material.** A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

## Components

| component | label | where |
|---|---|---|
| **approximant** | partial | [approximant](#approximant) |
| **ast** | partial | `syntax.json` |
| **descriptant** | present | [descriptant](#descriptant) |
| **invariant** | partial | [approximant](#approximant) |
| **tests** | finite checks | [tests](#tests) |

## 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.

| id | type | label | where |
|---|---|---|---|
| `behavior_complement` | behavior_complement | partial relational specification | [behavior_complement](#behavior-complement) |
| `reverse_reconstruction` | reverse_reconstruction | partial relational specification | [reverse_reconstruction](#reverse-reconstruction) |
| `pivot_tie_order` | pivot_tie_order | partial relational specification | [pivot_tie_order](#pivot-tie-order) |
| `prefix_swap_dependency` | prefix_swap_dependency | partial relational specification | [prefix_swap_dependency](#prefix-swap-dependency) |
| `reconstruction_observation` | reconstruction_observation | partial relational specification | [reconstruction_observation](#reconstruction-observation) |
| `shared_kernel_composition` | shared_kernel_composition | partial relational specification | [shared_kernel_composition](#shared-kernel-composition) |

## 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(b*n^3), stronger work than the prospective O(b*n^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(m*n^2), O(m*n+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(b*n^2+n^3), O(n^2). Offdiagonal decisions deterministic.
Power: normalize initial vector; Rayleigh quotient and fresh norm(Ax-lambda*x); check residual then budget; normalize Ax, classify zero image breakdown if encountered. Canonical signs. O(b*n^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-alpha*q-beta_prev*q_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(k*n^2+n*k^2), O(n*k). 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.