nx_power_iter.nx source

1// nx_power_iter.nx -- the team's GENERAL integer power-iteration ability (the bits-up core of truncated 2// SVD, the most-urgent MISSING gap the team's own gap-scan named, toward S-class semantic retrieval). 3// Power iteration finds the DOMINANT eigenvector of a symmetric matrix: v <- M v, renormalized, repeats 4// to the top eigen-direction; the eigenvalue is the inf-norm ratio. Integer fixed-point only (scale 5// 1000), no floats -- so it runs anywhere the team deploys. This is a GENERAL ability: it reduces ANY 6// matrix (e.g. the PPMI co-occurrence gram) to a dense embedding direction; the team applies it, Claude 7// does not hand-solve instances. Triangulated against a float reference (numpy eig). license_tier: ORIGINAL 8 9import "nx_syscalls.nx" 10 11const PI_SCALE: i64 = 1000 // fixed-point scale for the eigenvector (inf-norm normalized to 1000) 12 13// out = M * v, where M is nn x nn row-major, integers. 14func pi_matvec(M: *i64, v: *i64, nn: i64, out: *i64) -> i64 { 15 var i: i64 = 0 16 while i < nn { 17 var acc: i64 = 0; var j: i64 = 0 18 while j < nn { acc = acc + M[i * nn + j] * v[j]; j = j + 1 } 19 out[i] = acc 20 i = i + 1 21 } 22 return 0 23} 24 25// the inf-norm: max |v[i]| (normalization without a sqrt -- keeps it integer + cheap). 26func pi_absmax(v: *i64, nn: i64) -> i64 { 27 var m: i64 = 0; var i: i64 = 0 28 while i < nn { var a: i64 = v[i]; if a < 0 { a = 0 - a } if a > m { m = a } i = i + 1 } 29 return m 30} 31 32// K iterations of power iteration; out = dominant eigenvector, inf-norm-scaled to PI_SCALE. (M symmetric) 33func pi_iterate(M: *i64, nn: i64, K: i64, out: *i64) -> i64 { 34 var i: i64 = 0 35 while i < nn { out[i] = PI_SCALE; i = i + 1 } // start v = [1000, 1000, ...] 36 let tmp: *i64 = sys_mmap(nn * 8 + 64) as *i64 37 var k: i64 = 0 38 while k < K { 39 pi_matvec(M, out, nn, tmp) 40 let am: i64 = pi_absmax(tmp, nn) 41 if am == 0 { k = K } else { 42 i = 0 43 while i < nn { out[i] = (tmp[i] * PI_SCALE) / am; i = i + 1 } 44 } 45 k = k + 1 46 } 47 return 0 48} 49 50// the dominant eigenvalue in milli-units: |M v|_inf / |v|_inf (v is scaled so |v|_inf = PI_SCALE). 51func pi_eigenvalue_milli(M: *i64, v: *i64, nn: i64) -> i64 { 52 let tmp: *i64 = sys_mmap(nn * 8 + 64) as *i64 53 pi_matvec(M, v, nn, tmp) 54 let mv: i64 = pi_absmax(tmp, nn) 55 let vv: i64 = pi_absmax(v, nn) 56 if vv == 0 { return 0 } 57 return (mv * PI_SCALE) / vv 58} 59 60// the ratio v[a]/v[b] in milli (the eigen-direction signature, for triangulation against a reference). 61func pi_ratio_milli(v: *i64, a: i64, b: i64) -> i64 { 62 if v[b] == 0 { return 0 } 63 return (v[a] * PI_SCALE) / v[b] 64}