lu_det_step

std.linalg.lu_det_step · Level L3

One step of Gaussian elimination with partial pivoting, on column k: bring the row at or below k with the largest |U[i, k]| to row k, subtract multiples of it from the rows below, and multiply the running determinant d by the pivot, and by −1 for a swap. Columns and rows are taken by Gather, which is exact, so a choice between equal candidates is certain. The body that det scans.

p = argmaxᵢ≥ₖ |Uᵢₖ|; swap rows k, p; Uᵢ ← Uᵢ − (Uᵢₖ/Uₖₖ)·Uₖ (i > k); d ← ±d·Uₖₖ

Signature

lu_det_step(U: f64[n, n], d: f64[], k: f64[]) → f64[n, n], f64[]

Structure

The function as NOVA stores it: one box per input, operation and output, and arrows that carry values. A double border marks another library function this one runs — called once, or by Scan once per element; select it to open that function.

input
operation
constant
call
output

Verification

Signature proven by NOVA’s shape solver, for every size.
Equal to the reference swap in the first largest |U[i, k]|, i ≥ k; eliminate below; d·pivot, negated for a swap in exact rational arithmetic, on all 40 test cases.
All 839 float64 results inside the running error bound; the closest uses 87% of it.
Interpreter and NumPy backend return bit-identical results.
At float32 too: the 40 test cases rounded to float32, and 40 of them inside the running error bound at u = 2⁻²⁴; the closest uses 72% of it.

Accuracy in detail

correctly rounded (the float64 nearest the exact value): 96%
bit-equal to the NumPy formula in float64: 100%
largest error, in units in the last place: 21

Large ulp counts appear where a result is tiny next to the numbers it is computed from (after cancellation, for example), so one unit in the last place is tiny too; the absolute error is still inside the bound. Results within their own error of zero are not counted.

Identity

Calls

—

Called by

det

sha256:499c58943fc2395b6845bdf3221610b39ec7bb68a15d537dc8dbf0a74cfee4fe

The semantic hash of the graph. It changes when the program changes, and never when only its documentation does.

Control handle

Symbol: Ω:std.linalg.lu_det_step · Ω:lu_det_step
Pins: sha256:f286b5704985e3a74079fa6aee623c5426171697fd37763b5787cc9cd8031945this graph alone
Evidence: sha256:dbb163ae417925636d7cdb4b4f672a6122820ed3a132535b3e7759ab581c634athe hash of its verification record
Needs: no capability: a pure function

Through NOVA’s control layer, the symbol launches this function only while the program still matches what it pins: a change to this graph, or to any graph it reaches, needs a migration first.