Independent scholarship · Open accessThe monthly digest

Indexed text attachment

verify-topology.py

Source for Algebraic and Differential Topology in Higher Categories

View paper · Download original file

Lines 361–460 of 1961. Source text is displayed literally.

361    cs = [1]362    for k in range(1, n + 1):363        AM = [[sum(A[i][l] * M[l][j] for l in range(n)) for j in range(n)] for i in range(n)]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 371 372# ######################## SIMPLICIAL TOPOLOGY (exact) ########################373def closure(facets):374    S = {}375    for f in facets:376        f = tuple(sorted(f))377        for k in range(1, len(f) + 1):378            for c in itertools.combinations(f, k):379                S.setdefault(k - 1, set()).add(c)380    return {d: sorted(v) for d, v in S.items()}381 382 383class Cx:384    """finite simplicial complex with vertices ordered; simplices are sorted tuples"""385    def __init__(s, facets):386        s.S = closure(facets)387        s.dim = max(s.S)388        s.idx = {d: {x: i for i, x in enumerate(s.S[d])} for d in s.S}389 390    def n(s, d):391        return len(s.S.get(d, []))392 393    def fvec(s):394        return [s.n(d) for d in range(s.dim + 1)]395 396    def chi(s):397        return sum((-1) ** d * s.n(d) for d in range(s.dim + 1))398 399    def bd(s, d):400        """boundary matrix C_d -> C_{d-1} (rows: (d-1)-simplices)"""401        if d <= 0 or d > s.dim:402            return [[0] * s.n(d) for _ in range(s.n(d - 1) if d > 0 else 0)]403        M = [[0] * s.n(d) for _ in range(s.n(d - 1))]404        for j, x in enumerate(s.S[d]):405            for i in range(d + 1):406                M[s.idx[d - 1][x[:i] + x[i + 1:]]][j] = (-1) ** i407        return M408 409 410def snf(M):411    """non-zero invariant factors of an integer matrix (Smith normal form)"""412    A = [list(r) for r in M]413    m = len(A)414    n = len(A[0]) if m else 0415    out = []416    t = 0417    while t < min(m, n):418        piv = None419        for i in range(t, m):420            for j in range(t, n):421                if A[i][j] and (piv is None or abs(A[i][j]) < abs(A[piv[0]][piv[1]])):422                    piv = (i, j)423        if piv is None:424            break425        A[t], A[piv[0]] = A[piv[0]], A[t]426        for r in A:427            r[t], r[piv[1]] = r[piv[1]], r[t]428        while True:429            done = True430            for i in range(t + 1, m):431                if A[i][t]:432                    q = A[i][t] // A[t][t]433                    if q:434                        A[i] = [a - q * b for a, b in zip(A[i], A[t])]435                    if A[i][t]:436                        A[t], A[i] = A[i], A[t]437                        done = False438            for j in range(t + 1, n):439                if A[t][j]:440                    q = A[t][j] // A[t][t]441                    if q:442                        for r in A:443                            r[j] -= q * r[t]444                    if A[t][j]:445                        for r in A:446                            r[t], r[j] = r[j], r[t]447                        done = False448            if done:449                bad = None450                for i in range(t + 1, m):451                    for j in range(t + 1, n):452                        if A[i][j] % A[t][t]:453                            bad = i454                            break455                    if bad is not None:456                        break457                if bad is None:458                    break459                A[t] = [a + b for a, b in zip(A[t], A[bad])]460        out.append(abs(A[t][t]))