"""Graded conforming mesh and Bernstein polynomials on the reference triangle.""" from collections import deque from functools import cache from math import comb, factorial @cache def indices(p): return tuple((p-j-k, j, k) for k in range(p+1) for j in range(p-k+1)) @cache def index_map(p): return {alpha:i for i,alpha in enumerate(indices(p))} def bump(alpha, i, sign=1): out = list(alpha) out[i] += sign return tuple(out) @cache def mass_integer(p): ids = indices(p) den = factorial(2*p+2) // factorial(p)**2 weights = [[comb(a+i,a)*comb(b+j,b)*comb(c+k,c) for i,j,k in ids] for a,b,c in ids] assert all(sum(row)*(p+1)*(p+2)==den for row in weights) return weights,den @cache def derivative_ids(p, dim): target = index_map(p) return [(target[bump(a,dim)],target[bump(a,0)]) for a in indices(p-1)] def gradient(coeff, p): return [[(coeff[i]-coeff[j])*p for i,j in derivative_ids(p,dim)] for dim in (1,2)] def elevate(coeff, p): lookup = index_map(p) return [sum((a[i]*coeff[lookup[bump(a,i,-1)]] for i in range(3) if a[i]),0)/(p+1) for a in indices(p+1)] def local_particular(source, fluxes, p): """Piola flux with prescribed constant boundary density and divergence source. Edges are traversed 0->1, 1->2, 2->0. The three constants integrate to the integral of the source. All operations also apply to interval objects. """ pi, mi, ni = index_map(p), index_map(p+1), index_map(p+2) m = p+1 n = p+2 zero = source[0]*0 g = [zero]*len(mi) for a,j,k in indices(m): if k: g[mi[a,j,k]] = g[mi[a+1,j,k-1]] + source[pi[a,j,k-1]]/m # Curl of a scalar changes normal density by its tangential derivative. psi = [zero]*len(ni) for edge in range(3): q = [0,0,0] q[edge] = n vertex_value = psi[ni[tuple(q)]] for j in range(m+1): raw = g[mi[0,m-j,j]] if edge == 1 else zero vertex_value = vertex_value + (fluxes[edge]-raw)/n q[edge] -= 1 q[(edge+1)%3] += 1 if edge != 2 or j != m: psi[ni[tuple(q)]] = vertex_value gx,gy = gradient(psi,n) return gy, [b-a for a,b in zip(gx,g)] class Mesh: def __init__(self, depth): self.depth = depth self.den = 1 << (depth+2) vs = [tuple(self.den if i == j else 0 for j in range(4)) for i in range(4)] mid = lambda a,b:tuple((x+y)//2 for x,y in zip(a,b)) center = (self.den//4,)*4 side_mids = [mid(vs[i],vs[(i+1)%4]) for i in range(4)] self.vertices = [] vertex_ids = {} self.tris = [] def add_triangle(a,b,c): vertex_idx = [] for v in (a,b,c): if v not in vertex_ids: vertex_ids[v] = len(self.vertices) self.vertices.append(v) vertex_idx.append(vertex_ids[v]) self.tris.append(tuple(vertex_idx)) for i,corner in enumerate(vs): for a,b in ((side_mids[i],center),(center,side_mids[(i-1)%4])): for _ in range(depth): aa,bb = mid(corner,a),mid(corner,b) add_triangle(a,b,bb) add_triangle(a,bb,aa) a,b = aa,bb add_triangle(corner,a,b) assert len(self.tris)==8*(2*depth+1) self.support = [frozenset(i for i,w in enumerate(v) if w) for v in self.vertices] self.axis = frozenset((0,3)) self.top = tuple(frozenset((i,i+1)) for i in range(3)) self.edges = {} for it,tri in enumerate(self.tris): for k in range(3): a,b = tri[k],tri[(k+1)%3] self.edges.setdefault(tuple(sorted((a,b))),[]).append((it,k)) self.axis_roots = [] neighbors = [[] for _ in self.tris] for (a,b),inc in self.edges.items(): if len(inc)==2: (t,i),(s,j) = inc assert self.tris[t][i]==self.tris[s][(j+1)%3] assert self.tris[t][(i+1)%3]==self.tris[s][j] neighbors[t].append((s,i,j)) neighbors[s].append((t,j,i)) else: assert len(inc)==1 if (self.support[a] | self.support[b]) <= self.axis: self.axis_roots.append(inc[0]) else: assert any((self.support[a] | self.support[b])<=side for side in self.top) self.parent = {t:(-1,e,-1) for t,e in self.axis_roots} queue = deque(t for t,_ in self.axis_roots) self.order = [] while queue: t = queue.popleft() self.order.append(t) for s,i,j in neighbors[t]: if s not in self.parent: self.parent[s] = (t,j,i) queue.append(s) assert len(self.order)==len(self.tris) def flows(self, loads): total = list(loads) fluxes = [[0,0,0] for _ in self.tris] for t in reversed(self.order): s,j,i = self.parent[t] fluxes[t][j] = total[t] if s >= 0: total[s] = total[s]+total[t] fluxes[s][i] = -total[t] return fluxes def dofs(self, p, dirichlet): records = {} cells = [] fixed = [] for tri in self.tris: cell = [] for alpha in indices(p): key = tuple(sorted((v,e) for v,e in zip(tri,alpha) if e)) if key not in records: number = len(records) records[key] = number supp = frozenset().union(*(self.support[v] for v,e in key)) if any(supp<=boundary for boundary in dirichlet): fixed.append(number) cell.append(records[key]) cells.append(cell) return cells, fixed, len(records) def geometry(self, t, sqrt5): # Use Cartesian (X,Y) with physical (x,y)=(X,sY), s=sin(2*pi/5). # B has columns vertex1-vertex0 and vertex2-vertex0. c = (sqrt5-1)/4 a = (sqrt5+1)/4 s2 = (5+sqrt5)/8 v0,v1,v2 = (self.vertices[v] for v in self.tris[t]) def vector(v): u,b,g,d = (x-y for x,y in zip(v,v0)) return (u+b*c-(g+d)*a)/self.den, (b+2*g*c)/self.den x1,y1 = vector(v1) x2,y2 = vector(v2) jac = x1*y2-x2*y1 h11 = (y2*y2+x2*x2/s2)/jac h12 = -(y1*y2+x1*x2/s2)/jac h22 = (y1*y1+x1*x1/s2)/jac return jac,(h11,h12,h22)