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 324–423 of 1604. Source text is displayed literally.
324def kernel_dim(op, n, k):325 """dimension of the kernel of a linear operator on homogeneous polynomials of degree k in n variables"""326 src = monomials(n, k)327 imgs = [op({m: Fr(1)}) for m in src]328 tgt = sorted({key for im in imgs for key in im})329 if not tgt:330 return len(src)331 return len(src) - rank_exact([[im.get(t, 0) for t in tgt] for im in imgs])332 333 334# ---------- special functions ----------335def besselj(n, x, m=400):336 return sum(math.cos(n * (PI * (j + 0.5) / m) - x * math.sin(PI * (j + 0.5) / m)) for j in range(m)) / m337 338 339def legendre(l):340 """coefficients (Fractions, ascending powers) of the Legendre polynomial P_l"""341 p0, p1 = [Fr(1)], [Fr(0), Fr(1)]342 if l == 0:343 return p0344 for k in range(1, l):345 nxt = [Fr(0)] * (k + 2)346 for i, c in enumerate(p1):347 nxt[i + 1] += Fr(2 * k + 1, k + 1) * c348 for i, c in enumerate(p0):349 nxt[i] -= Fr(k, k + 1) * c350 p0, p1 = p1, nxt351 return p1352 353 354def heat(x, t, k=1.0):355 return math.exp(-x * x / (4 * k * t)) / math.sqrt(4 * PI * k * t)356 357 358def charpoly_int(A):359 n = len(A)360 M = [[int(i == j) for j in range(n)] for i in range(n)]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# ######################## 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]