Indexed text attachment
verify-topology-learning.py
Source for Algebraic and Differential Topology in Machine Learning and AI: Obstructions, Invariants, and Counts
View paper · Download original file
Lines 384–483 of 1604. Source text is displayed literally.
384 s.S = closure(facets)385 s.dim = max(s.S)386 s.idx = {d: {x: i for i, x in enumerate(s.S[d])} for d in s.S}387 388 def n(s, d):389 return len(s.S.get(d, []))390 391 def fvec(s):392 return [s.n(d) for d in range(s.dim + 1)]393 394 def chi(s):395 return sum((-1) ** d * s.n(d) for d in range(s.dim + 1))396 397 def bd(s, d):398 """boundary matrix C_d -> C_{d-1} (rows: (d-1)-simplices)"""399 if d <= 0 or d > s.dim:400 return [[0] * s.n(d) for _ in range(s.n(d - 1) if d > 0 else 0)]401 M = [[0] * s.n(d) for _ in range(s.n(d - 1))]402 for j, x in enumerate(s.S[d]):403 for i in range(d + 1):404 M[s.idx[d - 1][x[:i] + x[i + 1:]]][j] = (-1) ** i405 return M406 407 408def snf(M):409 """non-zero invariant factors of an integer matrix (Smith normal form)"""410 A = [list(r) for r in M]411 m = len(A)412 n = len(A[0]) if m else 0413 out = []414 t = 0415 while t < min(m, n):416 piv = None417 for i in range(t, m):418 for j in range(t, n):419 if A[i][j] and (piv is None or abs(A[i][j]) < abs(A[piv[0]][piv[1]])):420 piv = (i, j)421 if piv is None:422 break423 A[t], A[piv[0]] = A[piv[0]], A[t]424 for r in A:425 r[t], r[piv[1]] = r[piv[1]], r[t]426 while True:427 done = True428 for i in range(t + 1, m):429 if A[i][t]:430 q = A[i][t] // A[t][t]431 if q:432 A[i] = [a - q * b for a, b in zip(A[i], A[t])]433 if A[i][t]:434 A[t], A[i] = A[i], A[t]435 done = False436 for j in range(t + 1, n):437 if A[t][j]:438 q = A[t][j] // A[t][t]439 if q:440 for r in A:441 r[j] -= q * r[t]442 if A[t][j]:443 for r in A:444 r[t], r[j] = r[j], r[t]445 done = False446 if done:447 bad = None448 for i in range(t + 1, m):449 for j in range(t + 1, n):450 if A[i][j] % A[t][t]:451 bad = i452 break453 if bad is not None:454 break455 if bad is None:456 break457 A[t] = [a + b for a, b in zip(A[t], A[bad])]458 out.append(abs(A[t][t]))459 t += 1460 return out461 462 463def rank_mod(M, p):464 A = [[x % p for x in r] for r in M]465 rk = 0466 n = len(A[0]) if A else 0467 for c in range(n):468 piv = next((i for i in range(rk, len(A)) if A[i][c]), None)469 if piv is None:470 continue471 A[rk], A[piv] = A[piv], A[rk]472 inv_ = pow(A[rk][c], p - 2, p)473 A[rk] = [(x * inv_) % p for x in A[rk]]474 for i in range(len(A)):475 if i != rk and A[i][c]:476 f = A[i][c]477 A[i] = [(x - f * y) % p for x, y in zip(A[i], A[rk])]478 rk += 1479 return rk480 481 482BIGP = 1000003483