Independent scholarship · Open accessThe monthly digest

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 364–463 of 1604. Source text is displayed literally.

364        c = -sum(AM[i][i] for i in range(n)) // k365        cs.append(c)366        M = [[AM[i][j] + (c if i == j else 0) for j in range(n)] for i in range(n)]367    return tuple(cs)368 369 370# ######################## SIMPLICIAL TOPOLOGY (exact) ########################371def closure(facets):372    S = {}373    for f in facets:374        f = tuple(sorted(f))375        for k in range(1, len(f) + 1):376            for c in itertools.combinations(f, k):377                S.setdefault(k - 1, set()).add(c)378    return {d: sorted(v) for d, v in S.items()}379 380 381class Cx:382    """finite simplicial complex with vertices ordered; simplices are sorted tuples"""383    def __init__(s, facets):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):