jacobi_solve

std.linalg.jacobi_solve · Level L3

Solve A·x = b by Jacobi iteration for a diagonally dominant A, from x = 0 until the relative residual is below 10⁻¹⁰. The diagonal comes from an Iota mask; the loop is a While.

x ← x + (b − A·x) ⊘ diag(A) until ‖b − A·x‖ ≤ 10⁻¹⁰·‖b‖

Signature

jacobi_solve(A: f64[k, k], b: f64[k]) → f64[k]

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.

Af64[k, k]bf64[k]0.0IotarowIotacolMultiplyx0EqualeyeMultiplyAdiagReduceSumdSubtractRWhile·jacobi_stepxxf64[k]
  • input
  • operation
  • constant
  • call
  • output

Verification

  • Signature proven by NOVA’s shape solver, for every size.
  • Equal to the reference x = 0; while ||b - A@x||^2 > 1e-20*||b||^2: x = (b - R@x) / diag(A) in exact rational arithmetic, on all 40 test cases.
  • All 147 float64 results inside the running error bound; the closest uses 28% of it.
  • Interpreter and NumPy backend return bit-identical results.
Accuracy in detail
correctly rounded (the float64 nearest the exact value)
64%
bit-equal to the NumPy formula in float64
100%
largest error, in units in the last place
12

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.

Note

Jacobi converges when each diagonal entry outweighs the rest of its row; the test matrices make it twice their sum, so the error at least halves every step.

Identity

sha256:5f7f8f1c8e4507d383aa84a5fe876365b2b6862f1b7702dab1c18784933da0e5

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

Control handle

Symbol
Ω:std.linalg.jacobi_solve · Ω:jacobi_solve
Pins
sha256:e0c754acde8aca8aa285e908163daff75126fc1fdc8573272d457d796750823cthis graph and the 2 it reaches through calls
Evidence
sha256:1aaa0e4248d886b6d3e20c859a7931a7214b8fd79fed78a23c08fac8d48a5f64the 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.