#!/usr/bin/env python3
# verify-pde.py
# Companion script to "Partial Differential Equations in Higher Categories" (Higher Categorical Semantics, 2026; byline Anonymous).
# 107 computational checks of the numerical and finite statements in the book. Python standard library only; fixed seed.
# Usage: python3 verify-pde.py      (under half a minute; exit status 0 iff every check passes)
# The checks recompute examples and test instances of structural statements. They are evidence, not proofs.
# Written and run with AI assistance (Anthropic's Claude).
import math, cmath, random, sys, itertools
from fractions import Fraction as Fr

random.seed(20261117)
_n = [0, 0]
PI = math.pi


def sec(title):
    print('\n== ' + title + ' ==')


def check(name, ok, detail=''):
    _n[0] += 1
    _n[1] += 0 if ok else 1
    print(('PASS  ' if ok else 'FAIL  ') + name + (('\n      [' + detail + ']') if detail else ''))


def footer():
    print('\n%d checks, %d passed, %d failed' % (_n[0], _n[0] - _n[1], _n[1]))
    sys.exit(1 if _n[1] else 0)


def close(a, b, tol=1e-9):
    return abs(a - b) <= tol * (1 + abs(a) + abs(b))


# ---------- linear algebra (lists of lists) ----------
def eye(n):
    return [[1.0 if i == j else 0.0 for j in range(n)] for i in range(n)]


def tr(A):
    return [list(r) for r in zip(*A)]


def mm(A, B):
    Bt = list(zip(*B))
    return [[sum(a * b for a, b in zip(r, c)) for c in Bt] for r in A]


def mv(A, x):
    return [sum(a * b for a, b in zip(r, x)) for r in A]


def dot(x, y):
    return sum(a * b for a, b in zip(x, y))


def axpy(a, x, y):
    return [a * xi + yi for xi, yi in zip(x, y)]


def solve(A, b):
    n = len(A)
    M = [list(A[i]) + [b[i]] for i in range(n)]
    for c in range(n):
        p = max(range(c, n), key=lambda r: abs(M[r][c]))
        M[c], M[p] = M[p], M[c]
        piv = M[c][c]
        for r in range(c + 1, n):
            f = M[r][c] / piv
            if f:
                Mr, Mc = M[r], M[c]
                for k in range(c, n + 1):
                    Mr[k] -= f * Mc[k]
    x = [0.0] * n
    for i in range(n - 1, -1, -1):
        x[i] = (M[i][n] - sum(M[i][k] * x[k] for k in range(i + 1, n))) / M[i][i]
    return x


def inv(A):
    n = len(A)
    cols = [solve(A, [1.0 if i == j else 0.0 for i in range(n)]) for j in range(n)]
    return tr(cols)


def rank_exact(rows):
    M = [[Fr(v) for v in r] for r in rows]
    rk, ncol = 0, (len(M[0]) if M else 0)
    for c in range(ncol):
        p = next((r for r in range(rk, len(M)) if M[r][c] != 0), None)
        if p is None:
            continue
        M[rk], M[p] = M[p], M[rk]
        for r in range(rk + 1, len(M)):
            if M[r][c] != 0:
                f = M[r][c] / M[rk][c]
                M[r] = [a - f * b for a, b in zip(M[r], M[rk])]
        rk += 1
        if rk == len(M):
            break
    return rk


def inertia(A):
    """signature (positive, negative, zero) of a rational symmetric matrix by exact congruence"""
    n = len(A)
    M = [[Fr(v) for v in r] for r in A]
    pos = neg = zero = 0
    for k in range(n):
        if M[k][k] == 0:
            j = next((j for j in range(k + 1, n) if M[j][j] != 0), None)
            if j is not None:
                M[k], M[j] = M[j], M[k]
                for r in M:
                    r[k], r[j] = r[j], r[k]
            else:
                j = next((j for j in range(k + 1, n) if M[k][j] != 0), None)
                if j is None:
                    zero += 1
                    continue
                for c in range(n):
                    M[k][c] += M[j][c]
                for r in range(n):
                    M[r][k] += M[r][j]
        d = M[k][k]
        pos, neg = pos + (d > 0), neg + (d < 0)
        for i in range(k + 1, n):
            f = M[i][k] / d
            if f:
                for c in range(n):
                    M[i][c] -= f * M[k][c]
                for r in range(n):
                    M[r][i] -= f * M[r][k]
    return pos, neg, zero


def jacobi_eig(A, sweeps=60):
    """eigenvalues (ascending) and orthonormal eigenvectors (rows) of a real symmetric matrix"""
    n = len(A)
    a = [list(r) for r in A]
    v = eye(n)
    for _ in range(sweeps):
        off = sum(a[i][j] ** 2 for i in range(n) for j in range(i + 1, n))
        if off < 1e-22:
            break
        for p in range(n - 1):
            for q in range(p + 1, n):
                if abs(a[p][q]) < 1e-300:
                    continue
                th = (a[q][q] - a[p][p]) / (2 * a[p][q])
                t = (1 if th >= 0 else -1) / (abs(th) + math.sqrt(th * th + 1))
                c = 1 / math.sqrt(t * t + 1)
                s = t * c
                for k in range(n):
                    akp, akq = a[k][p], a[k][q]
                    a[k][p], a[k][q] = c * akp - s * akq, s * akp + c * akq
                for k in range(n):
                    apk, aqk = a[p][k], a[q][k]
                    a[p][k], a[q][k] = c * apk - s * aqk, s * apk + c * aqk
                for k in range(n):
                    vkp, vkq = v[k][p], v[k][q]
                    v[k][p], v[k][q] = c * vkp - s * vkq, s * vkp + c * vkq
    order = sorted(range(n), key=lambda i: a[i][i])
    return [a[i][i] for i in order], [[v[k][i] for k in range(n)] for i in order]


def tri_eigs(d, e, k):
    """the k smallest eigenvalues of the symmetric tridiagonal matrix (diagonal d, off-diagonal e) by Sturm bisection"""
    n = len(d)
    lo = min(d[i] - (abs(e[i - 1]) if i else 0) - (abs(e[i]) if i < n - 1 else 0) for i in range(n))
    hi = max(d[i] + (abs(e[i - 1]) if i else 0) + (abs(e[i]) if i < n - 1 else 0) for i in range(n))

    def count(x):
        c, q = 0, 1.0
        for i in range(n):
            q = d[i] - x - ((e[i - 1] ** 2) / q if i else 0.0)
            if q == 0:
                q = 1e-300
            if q < 0:
                c += 1
        return c
    out = []
    for j in range(k):
        a, b = lo, hi
        for _ in range(200):
            m = 0.5 * (a + b)
            if count(m) > j:
                b = m
            else:
                a = m
            if b - a < 1e-13 * (1 + abs(a)):
                break
        out.append(0.5 * (a + b))
    return out


def kron_sum(A, B):
    n, m = len(A), len(B)
    K = [[0.0] * (n * m) for _ in range(n * m)]
    for i in range(n):
        for j in range(n):
            for k in range(m):
                K[i * m + k][j * m + k] += A[i][j]
    for i in range(n):
        for k in range(m):
            for l in range(m):
                K[i * m + k][i * m + l] += B[k][l]
    return K


def lap1(n, bc='D'):
    """n x n matrix of -d^2/dx^2 with unit spacing: Dirichlet, Neumann (reflecting) or periodic"""
    L = [[0.0] * n for _ in range(n)]
    for i in range(n):
        L[i][i] = 2.0
        if i:
            L[i][i - 1] = -1.0
        if i < n - 1:
            L[i][i + 1] = -1.0
    if bc == 'N':
        L[0][0] = L[n - 1][n - 1] = 1.0
    if bc == 'P':
        L[0][n - 1] += -1.0
        L[n - 1][0] += -1.0
    return L


# ---------- calculus ----------
def simpson(f, a, b, n=2000):
    n += n % 2
    h = (b - a) / n
    s = f(a) + f(b)
    for i in range(1, n):
        s += (4 if i % 2 else 2) * f(a + i * h)
    return s * h / 3


def rk4(F, y, h):
    k1 = F(y)
    k2 = F([a + 0.5 * h * b for a, b in zip(y, k1)])
    k3 = F([a + 0.5 * h * b for a, b in zip(y, k2)])
    k4 = F([a + h * b for a, b in zip(y, k3)])
    return [a + h * (p + 2 * q + 2 * r + s) / 6 for a, p, q, r, s in zip(y, k1, k2, k3, k4)]


def d1(f, x, h=1e-4):
    return (f(x - 2 * h) - 8 * f(x - h) + 8 * f(x + h) - f(x + 2 * h)) / (12 * h)


def d2(f, x, h=1e-3):
    return (-f(x - 2 * h) + 16 * f(x - h) - 30 * f(x) + 16 * f(x + h) - f(x + 2 * h)) / (12 * h * h)


def d3(f, x, h=2e-3):
    return (f(x - 3 * h) - 8 * f(x - 2 * h) + 13 * f(x - h) - 13 * f(x + h) + 8 * f(x + 2 * h) - f(x + 3 * h)) / (8 * h ** 3)


def bisect(f, a, b, it=200):
    fa = f(a)
    for _ in range(it):
        m = 0.5 * (a + b)
        fm = f(m)
        if (fa < 0) == (fm < 0):
            a, fa = m, fm
        else:
            b = m
    return 0.5 * (a + b)


# ---------- polynomials in several variables: dict {exponent tuple: coefficient} ----------
def padd(p, q, c=1):
    r = dict(p)
    for k, v in q.items():
        r[k] = r.get(k, 0) + c * v
        if r[k] == 0:
            del r[k]
    return r


def pmul(p, q):
    r = {}
    for k1, v1 in p.items():
        for k2, v2 in q.items():
            k = tuple(a + b for a, b in zip(k1, k2))
            r[k] = r.get(k, 0) + v1 * v2
    return {k: v for k, v in r.items() if v != 0}


def pdiff(p, i):
    r = {}
    for k, v in p.items():
        if k[i]:
            kk = k[:i] + (k[i] - 1,) + k[i + 1:]
            r[kk] = r.get(kk, 0) + v * k[i]
    return {k: v for k, v in r.items() if v != 0}


def pvar(i, n):
    return {tuple(1 if j == i else 0 for j in range(n)): Fr(1)}


def pscale(p, c):
    return {k: v * c for k, v in p.items() if v * c != 0}


def peval(p, x):
    return sum(v * math.prod(xi ** e for xi, e in zip(x, k)) for k, v in p.items())


def plap(p, sig=None):
    n = len(next(iter(p))) if p else 0
    sig = sig or [1] * n
    r = {}
    for i in range(n):
        r = padd(r, pdiff(pdiff(p, i), i), sig[i])
    return r


def monomials(n, k):
    return [e for e in itertools.product(range(k + 1), repeat=n) if sum(e) == k]


def kernel_dim(op, n, k):
    """dimension of the kernel of a linear operator on homogeneous polynomials of degree k in n variables"""
    src = monomials(n, k)
    imgs = [op({m: Fr(1)}) for m in src]
    tgt = sorted({key for im in imgs for key in im})
    if not tgt:
        return len(src)
    return len(src) - rank_exact([[im.get(t, 0) for t in tgt] for im in imgs])


# ---------- special functions ----------
def besselj(n, x, m=400):
    return sum(math.cos(n * (PI * (j + 0.5) / m) - x * math.sin(PI * (j + 0.5) / m)) for j in range(m)) / m


def legendre(l):
    """coefficients (Fractions, ascending powers) of the Legendre polynomial P_l"""
    p0, p1 = [Fr(1)], [Fr(0), Fr(1)]
    if l == 0:
        return p0
    for k in range(1, l):
        nxt = [Fr(0)] * (k + 2)
        for i, c in enumerate(p1):
            nxt[i + 1] += Fr(2 * k + 1, k + 1) * c
        for i, c in enumerate(p0):
            nxt[i] -= Fr(k, k + 1) * c
        p0, p1 = p1, nxt
    return p1


def heat(x, t, k=1.0):
    return math.exp(-x * x / (4 * k * t)) / math.sqrt(4 * PI * k * t)


def charpoly_int(A):
    n = len(A)
    M = [[int(i == j) for j in range(n)] for i in range(n)]
    cs = [1]
    for k in range(1, n + 1):
        AM = [[sum(A[i][l] * M[l][j] for l in range(n)) for j in range(n)] for i in range(n)]
        c = -sum(AM[i][i] for i in range(n)) // k
        cs.append(c)
        M = [[AM[i][j] + (c if i == j else 0) for j in range(n)] for i in range(n)]
    return tuple(cs)


# ######################## CHECKS FOR THE BOOK ########################
sec('1. Equations: symbol, type, characteristics, formal solutions')


def kind(sig):
    p, q, z = sig
    n = p + q + z
    if z == 0 and (p == 0 or q == 0):
        return 'elliptic'
    if z == 0 and min(p, q) == 1:
        return 'hyperbolic'
    if z == 1 and (p == 0 or q == 0):
        return 'parabolic'
    return 'other'


ok = True
for _ in range(300):
    n = random.choice([2, 3, 4])
    A = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i, n):
            A[i][j] = A[j][i] = random.randint(-3, 3)
    while True:
        B = [[random.randint(-3, 3) for _ in range(n)] for _ in range(n)]
        if rank_exact(B) == n:
            break
    BAB = [[sum(B[k][i] * A[k][l] * B[l][j] for k in range(n) for l in range(n)) for j in range(n)] for i in range(n)]
    ok = ok and inertia(BAB) == inertia(A)
arch = (kind(inertia([[1, 0], [0, 1]])), kind(inertia([[1, 0], [0, -1]])), kind(inertia([[1, 0], [0, 0]])))
ok2 = True
for _ in range(300):
    a11, a12, a22 = (random.randint(-4, 4) for _ in range(3))
    if a11 == a12 == a22 == 0:
        continue
    d = a12 * a12 - a11 * a22
    ok2 = ok2 and kind(inertia([[a11, a12], [a12, a22]])) == ('elliptic' if d < 0 else 'hyperbolic' if d > 0 else 'parabolic')
check('E1 the type of a second-order operator is the inertia of its symbol: invariant under 300 random linear changes of variables,'
      ' and equal to the source\'s discriminant test in two variables', ok and ok2 and arch == ('elliptic', 'hyperbolic', 'parabolic'), 'Laplace, wave, heat: %s, %s, %s' % arch)
pts = [(Fr(2), Fr(3)), (Fr(-2), Fr(-3)), (Fr(1, 2), Fr(1)), (Fr(-1), Fr(4)), (Fr(2), Fr(1, 2)), (Fr(0), Fr(0))]
kinds = [kind(inertia([[y, -1], [-1, x]])) for x, y in pts]
check('E2 the source\'s example y u_xx - 2 u_xy + x u_yy: elliptic where xy > 1, hyperbolic where xy < 1, parabolic on xy = 1',
      kinds == ['elliptic', 'elliptic', 'hyperbolic', 'hyperbolic', 'parabolic', 'hyperbolic'], ', '.join(kinds))
f = lambda s: math.sin(s) + s * s
r1 = max(abs(4 * d1(lambda x: f(-3 * x - 4 * y), x) - 3 * d1(lambda yy: f(-3 * x - 4 * yy), y)) for x, y in [(0.3, -0.7), (1.1, 0.4), (-2.0, 0.9)])
r2 = max(abs(d1(lambda xx: f(math.exp(-xx) * y), x) + y * d1(lambda yy: f(math.exp(-x) * yy), y)) for x, y in [(0.3, -0.7), (1.1, 0.4), (-2.0, 0.9)])
check('E3 first-order equations are solved by pulling back along the quotient by the characteristics: f(-3x-4y) solves 4u_x - 3u_y = 0,'
      ' f(e^{-x} y) solves u_x + y u_y = 0, and the line y = 0 is a characteristic, on which every solution is constant',
      r1 < 1e-8 and r2 < 1e-8 and all(math.exp(-x) * 0.0 == 0.0 for x in (-1.0, 0.5, 3.0)), 'residuals %.1e, %.1e' % (r1, r2))
ok, rows = True, []
for n in (2, 3, 4):
    for k in range(0, 6):
        want = math.comb(n + k - 1, k) - (math.comb(n + k - 3, k - 2) if k >= 2 else 0)
        got = (kernel_dim(plap, n, k), kernel_dim(lambda p: plap(p, [1] * (n - 1) + [-1]), n, k), kernel_dim(lambda p: pdiff(pdiff(p, 0), 0), n, k))
        ok = ok and got == (want, want, want)
    rows.append('n=%d: %s' % (n, [math.comb(n + k - 1, k) - (math.comb(n + k - 3, k - 2) if k >= 2 else 0) for k in range(6)]))
check('E4 formal solutions do not see the type: homogeneous polynomial solutions of degree k of the Laplace, wave and degenerate'
      ' operators have the same dimension C(n+k-1,k) - C(n+k-3,k-2) (exact ranks)', ok, '; '.join(rows))
c = Fr(3, 2)
ok = True
for _ in range(20):
    p = {(random.randint(0, 4), random.randint(0, 4)): Fr(random.randint(-5, 5)) for _ in range(6)}
    p = {k: v for k, v in p.items() if v != 0}
    if not p:
        continue
    A1 = padd(pdiff(p, 0), pdiff(p, 1), c)                       # (d_t + c d_x) p, variables (t, x)
    lhs = padd(pdiff(A1, 0), pdiff(A1, 1), -c)                   # (d_t - c d_x)(d_t + c d_x) p
    rhs = padd(pdiff(pdiff(p, 0), 0), pdiff(pdiff(p, 1), 1), -c * c)
    ok = ok and lhs == rhs
nreal = lambda a11, a12, a22: (0 if a12 * a12 < a11 * a22 else 1 if a12 * a12 == a11 * a22 else 2)
check('E5 the type is visible in the real characteristics: none for Laplace, one double for heat, two for wave; and the wave operator'
      ' factors exactly into two transport operators', ok and (nreal(1, 0, 1), nreal(1, 0, 0), nreal(1, 0, -1)) == (0, 1, 2))
ok = True
for k in range(0, 9):
    v = {(k - 2 * j, j): Fr(math.factorial(k), math.factorial(j) * math.factorial(k - 2 * j)) for j in range(k // 2 + 1)}
    ok = ok and padd(pdiff(v, 1), pdiff(pdiff(v, 0), 0), -1) == {}
ratios = [Fr(math.factorial(2 * j + 2), math.factorial(j + 1)) / Fr(math.factorial(2 * j), math.factorial(j)) for j in range(6)]
check('E6 prolongation: the heat polynomials solve u_t = u_xx exactly for degrees 0..8; for the analytic datum 1/(1+x^2) the formal series'
      ' in t at x = 0 has coefficients (2j)!/j! and radius of convergence zero (Kovalevskaya)', ok and ratios == [2 * (2 * j + 1) for j in range(6)],
      'successive ratios %s' % [int(r) for r in ratios])

sec('2. Archetypes and well-posedness')
un = lambda n: (lambda x, y: math.exp(-math.sqrt(n)) * math.sin(n * x) * math.sinh(n * y) / n)
res = max(abs(d2(lambda x: un(5)(x, 0.3), 0.7, 1e-3) + d2(lambda y: un(5)(0.7, y), 0.3, 1e-3)) for _ in range(1))
data = [math.exp(-math.sqrt(n)) for n in (25, 100, 400)]
sol = [math.exp(-math.sqrt(n)) * math.sinh(n) / n for n in (25, 100, 400)]
check('W1 Hadamard: Cauchy data for Laplace\'s equation tending to zero with solutions tending to infinity at y = 1',
      res < 1e-6 and data[0] > data[1] > data[2] and sol[0] < sol[1] < sol[2], 'n = 25, 100, 400: data %.1e, %.1e, %.1e; solution %.1e, %.1e, %.1e' % (*data, *sol))
amp = [math.exp(n * n * 0.1) for n in (1, 10, 30)]
check('W2 the heat semigroup is not a group: mode n is damped by exp(-n^2 t) forwards and amplified by exp(n^2 t) backwards', amp[2] > 1e38,
      't = 0.1, n = 1, 10, 30: %.3f, %.3e, %.3e' % tuple(amp))
n = 7
D = [[(-1 if j == i else 1 if j == i + 1 else 0) for j in range(n)] for i in range(n - 1)]
DtD = mm(tr(D), D)
check('W3 conservation plus a constitutive law: the Neumann Laplacian of a path is D^T D for the incidence matrix D, and its columns sum to zero'
      ' (mass is conserved)', all(DtD[i][j] == lap1(n, 'N')[i][j] for i in range(n) for j in range(n)) and all(abs(sum(DtD[i][j] for i in range(n))) < 1e-12 for j in range(n)))
L = lap1(20)
u = [random.uniform(-1, 1) for _ in range(20)]
mono, uu = True, list(u)
for _ in range(200):
    e0 = dot(uu, uu)
    uu = rk4(lambda y: [-z for z in mv(L, y)], uu, 0.01)
    mono = mono and dot(uu, uu) <= e0
st = u + [random.uniform(-1, 1) for _ in range(20)]
energy = lambda s: 0.5 * dot(s[20:], s[20:]) + 0.5 * dot(s[:20], mv(L, s[:20]))
E0 = energy(st)
for _ in range(1000):
    st = rk4(lambda s: s[20:] + [-z for z in mv(L, s[:20])], st, 0.005)
check('W4 the two energy laws on a grid of 20 points: the square norm decreases along the diffusion flow, and the wave energy is conserved',
      mono and abs(energy(st) - E0) < 1e-8 * E0, 'relative drift of the wave energy over time 5: %.1e' % (abs(energy(st) - E0) / E0))
LN = [[int(v) for v in r] for r in lap1(6, 'N')]
f_ok, f_bad = [1, -2, 3, 0, -1, -1], [1, -2, 3, 0, -1, 0]
check('W5 the Neumann problem: kernel the constants, solvable exactly when the source has mean zero (exact ranks)',
      rank_exact(LN) == 5 and rank_exact([r + [b] for r, b in zip(LN, f_ok)]) == 5 and rank_exact([r + [b] for r, b in zip(LN, f_bad)]) == 6)
check('W6 the source\'s first example of non-uniqueness: u\'\' + u = 0, u(0) = u(L) = 0 has a non-zero solution exactly when sin L = 0',
      abs(math.sin(PI)) < 1e-15 and abs(math.sin(2.0)) > 0.5)

sec('3. Waves')
c = 2.0
phi = lambda x: math.exp(-x * x)
psi = lambda x: x * math.exp(-x * x)
Psi = lambda x: -0.5 * math.exp(-x * x)                     # antiderivative of psi
dal = lambda x, t, ph=phi, PS=Psi: 0.5 * (ph(x + c * t) + ph(x - c * t)) + (PS(x + c * t) - PS(x - c * t)) / (2 * c)
pts = [(0.3, 0.2), (-1.1, 0.7), (2.0, 1.3)]
res = max(abs(d2(lambda t: dal(x, t), t) - c * c * d2(lambda xx: dal(xx, t), x)) for x, t in pts)
ini = max(abs(dal(x, 0.0) - phi(x)) + abs(d1(lambda t: dal(x, t), 0.0) - psi(x)) for x in (-1.0, 0.2, 0.9))
check('V1 d\'Alembert\'s formula solves the wave equation with the given data', res < 1e-6 and ini < 1e-9, 'residual %.1e' % res)
par = 0.0
for _ in range(50):
    xi, eta, h, kk = random.uniform(-2, 2), random.uniform(-2, 2), random.uniform(0.1, 1), random.uniform(0.1, 1)
    U = lambda a, b: dal((a + b) / 2, (a - b) / (2 * c))
    par = max(par, abs(U(xi + h, eta + kk) - U(xi + h, eta) - U(xi, eta + kk) + U(xi, eta)))
check('V2 in light-cone coordinates the equation is u_{xi eta} = 0: the sum over opposite corners of every characteristic parallelogram agrees',
      par < 1e-14, 'largest defect %.1e' % par)
x0, t0 = 0.4, 0.5
bump = lambda x, a: (math.exp(-1 / (1 - (x - a) ** 2)) if abs(x - a) < 1 else 0.0)
out_ = dal(x0, t0, lambda x: phi(x) + bump(x, x0 + c * t0 + 1.5)) - dal(x0, t0)
in_ = dal(x0, t0, lambda x: phi(x) + bump(x, x0 + c * t0 - 0.5)) - dal(x0, t0)
check('V3 causality: data changed outside the interval of dependence do not change the solution; data changed inside do', out_ == 0.0 and abs(in_) > 1e-3)
ut = lambda x, t: d1(lambda s: dal(x, s), t)
ux = lambda x, t: d1(lambda s: dal(s, t), x)
En = [simpson(lambda x: 0.5 * (ut(x, t) ** 2 + c * c * ux(x, t) ** 2), -12, 12, 1200) for t in (0.0, 0.7, 1.9)]
check('V4 energy is conserved', max(En) - min(En) < 1e-7, 'E = %.8f, %.8f, %.8f' % tuple(En))
odd = lambda g: (lambda x: g(x) if x > 0 else -g(-x) if x < 0 else 0.0)
ph2 = lambda x: x * math.exp(-(x - 2) ** 2)
ps2 = lambda x: math.sin(x) * math.exp(-x)
Iq = lambda g, a, b: simpson(g, a, b, 400)
vodd = lambda x, t: 0.5 * (odd(ph2)(x + c * t) + odd(ph2)(x - c * t)) + Iq(odd(ps2), x - c * t, x + c * t) / (2 * c)
vsrc = lambda x, t: (0.5 * (ph2(x + c * t) + ph2(x - c * t)) + Iq(ps2, x - c * t, x + c * t) / (2 * c) if x > c * t else
                     0.5 * (ph2(c * t + x) - ph2(c * t - x)) + Iq(ps2, c * t - x, c * t + x) / (2 * c))
dv = max(abs(vodd(x, t) - vsrc(x, t)) for x, t in [(0.5, 0.1), (0.5, 1.0), (3.0, 0.4), (1.0, 2.0)])
check('V5 reflection: the Dirichlet problem on the half-line is the odd part of the problem on the line; the result is the source\'s'
      ' two-region formula and vanishes at the boundary', dv < 1e-6 and abs(vodd(0.0, 0.8)) < 1e-12, 'largest difference %.1e' % dv)
l = 1.0
ph3 = lambda x: x * (1 - x)


def ext(x):
    x = (x + l) % (2 * l) - l
    return ph3(x) if x >= 0 else -ph3(-x)


vim = lambda x, t: 0.5 * (ext(x + c * t) + ext(x - c * t))
vfs = lambda x, t: sum(8 / (n * PI) ** 3 * math.cos(n * PI * c * t / l) * math.sin(n * PI * x / l) for n in range(1, 4001, 2))
dv = max(abs(vim(x, t) - vfs(x, t)) for x, t in [(0.3, 0.2), (0.7, 1.4), (0.1, 3.3)])
check('V6 the finite interval: the sum over the reflection group (the infinite dihedral group) equals the sum over eigenfunctions,'
      ' and the motion has period 2l/c', dv < 1e-7 and abs(vim(0.3, 0.2 + 2 * l / c) - vim(0.3, 0.2)) < 1e-14, 'largest difference %.1e' % dv)
duh = lambda x, t: simpson(lambda s: simpson(lambda y: math.cos(y), x - c * (t - s), x + c * (t - s), 200), 0.0, t, 400) / (2 * c)
dd = max(abs(duh(x, t) - math.cos(x) * (1 - math.cos(c * t)) / c ** 2) for x, t in [(0.3, 0.9), (1.7, 2.2)])
check('V7 Duhamel: the source\'s formula for the forced wave equation, against the closed form for the force cos x', dd < 1e-7, 'difference %.1e' % dd)
dal2 = lambda x, t: dal(x, t, lambda z: math.exp(-(z - 1) ** 2), lambda z: 0.3 * math.exp(-z * z) * z)
Om = [simpson(lambda x: dal(x, t) * d1(lambda s: dal2(x, s), t) - d1(lambda s: dal(x, s), t) * dal2(x, t), -12, 12, 1200) for t in (0.0, 1.3)]
check('V8 the solution space is symplectic: the Wronskian form of two solutions does not depend on the time at which it is computed',
      abs(Om[0] - Om[1]) < 1e-7 and abs(Om[0]) > 1e-3, 'Omega = %.8f, %.8f' % tuple(Om))

sec('4. Diffusions')
kd = 0.7
S = lambda x, t: heat(x, t, kd)
res = max(abs(d1(lambda t: S(x, t), t) - kd * d2(lambda xx: S(xx, t), x)) for x, t in [(0.3, 0.5), (-1.2, 1.1)])
ck = abs(simpson(lambda y: S(0.4 - y, 0.3) * S(y - (-0.2), 0.9), -15, 15, 3000) - S(0.6, 1.2))
check('D1 the heat kernel is a Markov semigroup: it solves the equation, has total mass one, and composes (Chapman-Kolmogorov)',
      res < 1e-7 and abs(simpson(lambda y: S(y, 0.4), -15, 15, 3000) - 1) < 1e-12 and ck < 1e-12, 'residual %.1e, composition defect %.1e' % (res, ck))
dq = max(abs(simpson(lambda y: S(x - y, t), 0, 30, 6000) - 0.5 * (1 + math.erf(x / math.sqrt(4 * kd * t)))) for x, t in [(0.3, 0.2), (-1.0, 0.8)])
check('D2 a unit step diffuses into (1 + erf(x / sqrt(4kt)))/2', dq < 1e-9)


def step_matrix(n, s, bc='D'):
    Lm = lap1(n, bc)
    return [[(1.0 if i == j else 0.0) - s * Lm[i][j] for j in range(n)] for i in range(n)]


P5, P6 = step_matrix(12, 0.5), step_matrix(12, 0.6)
u = [random.uniform(-1, 1) for _ in range(12)]
grow, alt = True, [(-1.0) ** i for i in range(12)]
for _ in range(30):
    un_ = mv(P5, u)
    grow = grow and max(map(abs, un_)) <= max(map(abs, u)) + 1e-15
    u = un_
a1 = mv(P6, alt)
check('D3 the explicit scheme is a (sub)Markov kernel exactly when s <= 1/2, and then it obeys the maximum principle; at s = 0.6 the'
      ' alternating mode grows by |1 - 4s| in the interior', min(min(r) for r in P5) >= 0 and min(min(r) for r in P6) < 0 and grow and abs(abs(a1[5]) - 1.4) < 1e-12)
Pp = step_matrix(16, 0.3, 'P')
ent = lambda p: -sum(x * math.log(x) for x in p if x > 0)
okH = True
for _ in range(50):
    p = [random.random() for _ in range(16)]
    sp = sum(p)
    p = [x / sp for x in p]
    q = mv(Pp, p)
    okH = okH and ent(q) >= ent(p) - 1e-13 and dot(q, q) <= dot(p, p) + 1e-15 and abs(sum(q) - 1) < 1e-12
check('D4 irreversibility: under a doubly stochastic step entropy does not decrease and the square norm does not increase', okH)
surv = lambda x, t: simpson(lambda y: S(x - y, t) - S(x + y, t), 0, 40, 8000)
neu = lambda x, t: simpson(lambda y: (S(x - y, t) + S(x + y, t)) * math.exp(-(y - 1) ** 2), 0, 40, 8000)
dq = max(abs(surv(x, t) - math.erf(x / math.sqrt(4 * kd * t))) for x, t in [(0.5, 0.3), (2.0, 1.5)])
check('D5 images on the half-line: the odd kernel S(x-y) - S(x+y) vanishes at the wall and gives the survival probability erf(x/sqrt(4kt));'
      ' the even kernel has zero slope there', dq < 1e-9 and abs(surv(0.0, 0.3)) < 1e-15 and abs(d1(lambda x: neu(x, 0.4), 0.0)) < 1e-8)
l = 1.0


def K_img(x, y, t, M):
    return sum(S(x - y - 2 * m * l, t) - S(x + y - 2 * m * l, t) for m in range(-M, M + 1))


def K_eig(x, y, t, N):
    return (2 / l) * sum(math.exp(-kd * (n * PI / l) ** 2 * t) * math.sin(n * PI * x / l) * math.sin(n * PI * y / l) for n in range(1, N + 1))


def terms(fn, x, y, t, ref):
    for M in range(0, 400):
        if abs(fn(x, y, t, M) - ref) < 1e-10:
            return M
    return None


rows, okK = [], True
for t in (0.001, 0.05, 1.0):
    ref = K_img(0.3, 0.45, t, 60)
    okK = okK and abs(ref - K_eig(0.3, 0.45, t, 2000)) < 1e-10
    rows.append('t=%g: %d image shells, %d modes' % (t, terms(K_img, 0.3, 0.45, t, ref), terms(K_eig, 0.3, 0.45, t, ref)))
check('D6 the heat kernel of an interval two ways: the sum over the reflection group and the sum over eigenfunctions agree'
      ' (Poisson summation); terms needed for accuracy 1e-10', okK, '; '.join(rows))
check('D7 scaling: S(x, t) = t^{-1/2} S(x / sqrt t, 1)', all(abs(S(x, t) - S(x / math.sqrt(t), 1.0) / math.sqrt(t)) < 1e-15 for x, t in [(0.3, 0.2), (2.0, 5.0)]))
far = 0.5 * (math.erfc((10 - 1) / math.sqrt(4 * 0.1)) - math.erfc((10 + 1) / math.sqrt(4 * 0.1)))
check('D8 infinite speed: data supported in [-1, 1] give a positive value at x = 10 after time 0.1 (unit diffusivity)', 0 < far < 1e-80, 'u = %.2e' % far)
S1 = lambda x, t: heat(x, t, 1.0)
inner = simpson(lambda y: S1(0.8 - y, 0.37) * math.sin(y), -14, 15, 4000)
duh = simpson(lambda s: math.exp(-(1.2 - s)), 0.0, 1.2, 200) * math.sin(0.8)
check('D9 Duhamel for diffusion: the semigroup maps sin to e^{-t} sin, and the forced solution is (1 - e^{-t}) sin x',
      abs(inner - math.exp(-0.37) * math.sin(0.8)) < 1e-11 and abs(duh - (1 - math.exp(-1.2)) * math.sin(0.8)) < 1e-10)

sec('5. Boundary conditions and Fourier series')
l = 1.3
og = max(abs(simpson(lambda x: math.sin(n * PI * x / l) * math.sin(m * PI * x / l), 0, l, 400) - (l / 2 if n == m else 0)) for n in range(1, 5) for m in range(1, 5))
check('F1 the Dirichlet eigenfunctions sin(n pi x / l) are orthogonal with square norm l/2', og < 1e-9)


def robin_F(lam, a0, al, l):
    if lam > 1e-12:
        b = math.sqrt(lam)
        X, dX = math.cos(b * l) + a0 * math.sin(b * l) / b, -b * math.sin(b * l) + a0 * math.cos(b * l)
    elif lam < -1e-12:
        g = math.sqrt(-lam)
        X, dX = math.cosh(g * l) + a0 * math.sinh(g * l) / g, g * math.sinh(g * l) + a0 * math.cosh(g * l)
    else:
        X, dX = 1 + a0 * l, a0
    return dX + al * X


def neg_roots(a0, al, l):
    grid = [-60 + 0.01 * i for i in range(5990)]             # lambda in (-60, -0.1)
    vals = [robin_F(x, a0, al, l) for x in grid]
    return [bisect(lambda x: robin_F(x, a0, al, l), grid[i], grid[i + 1]) for i in range(len(grid) - 1) if (vals[i] < 0) != (vals[i + 1] < 0)]


nr = [len(neg_roots(1, 1, 1.0)), len(neg_roots(-1, -1, 1.0)), len(neg_roots(-1, -1, 3.0))]
lam1 = neg_roots(-1, -1, 1.0)[0]
check('F2 Robin conditions X\' - a0 X = 0, X\' + al X = 0: a zero eigenvalue exactly when a0 + al = -a0 al l (the source\'s criterion);'
      ' with a0 = al = -1 there is one negative eigenvalue for l = 1 and two for l = 3; none for a0 = al = 1',
      nr == [0, 1, 2] and abs(robin_F(0.0, -1, -1, 2.0)) < 1e-15 and abs(robin_F(0.0, -1, -1, 1.0)) > 0.5, 'negative eigenvalue for l = 1: %.6f' % lam1)
om = lambda u, v: u[3] * v[2] - u[2] * v[3] - u[1] * v[0] + u[0] * v[1]       # [f'g - fg'] from a to b on (f(a), f'(a), f(b), f'(b))
bcs = {'Dirichlet': ((0, 1, 0, 0), (0, 0, 0, 1)), 'Neumann': ((1, 0, 0, 0), (0, 0, 1, 0)), 'Robin': ((1, 0.7, 0, 0), (0, 0, 1, -2.5)),
       'periodic': ((1, 0, 1, 0), (0, 1, 0, 1)), 'source\'s fifth': ((1, 0, 1, 0), (0, 2, 0, 1))}
vals = {k: om(*v) for k, v in bcs.items()}
check('F3 a boundary condition is a plane in the space of boundary values, and it is symmetric exactly when the plane is Lagrangian for'
      ' the form of Green\'s second identity: true for Dirichlet, Neumann, Robin, periodic; false for X(a) = X(b), X\'(a) = 2X\'(b)',
      all(abs(vals[k]) < 1e-15 for k in ('Dirichlet', 'Neumann', 'Robin', 'periodic')) and abs(vals['source\'s fifth'] - 1) < 1e-15)
N = 200000
ps = sum(1.0 / (n * n) for n in range(1, N + 1)) + 1.0 / N - 1.0 / (2 * N * N)
check('F4 Parseval for the sine series of x gives sum 1/n^2 = pi^2/6', abs(ps - PI ** 2 / 6) < 1e-12)
Si = simpson(lambda th: math.sin(th) / th if th else 1.0, 0, PI, 2000) / PI
SN = lambda N, x: (2 / PI) * sum(math.sin(n * x) / n for n in range(1, N + 1, 2))
peaks = [SN(N, PI / (N + 1)) for N in (51, 201, 801)]
check('F5 Gibbs: partial sums of a unit jump overshoot to (1/pi) Si(pi) = 0.58949 on the side where the value is 1/2: 8.95 per cent of the jump',
      abs(Si - 0.5894899) < 1e-6 and abs(peaks[2] - Si) < 1e-5, 'peaks at N = 51, 201, 801: %.6f, %.6f, %.6f' % tuple(peaks))
co = lambda f, n, kind: simpson(lambda x: f(x) * (math.cos(n * x) if kind == 'c' else math.sin(n * x)), -PI, PI, 4000) / PI
st = [n * abs(co(lambda x: (1 if x > 0 else -1), n, 's')) for n in (5, 25, 125)]
ab = [n * n * abs(co(abs, n, 'c')) for n in (5, 25, 125)]
an = [co(lambda x: 1 / (5 - 4 * math.cos(x)), n, 'c') / co(lambda x: 1 / (5 - 4 * math.cos(x)), n + 1, 'c') for n in (2, 5, 9)]
check('F6 smoothness is decay: coefficients of a jump fall like 1/n, of a corner like 1/n^2, of an analytic function geometrically',
      all(abs(v - 4 / PI) < 1e-3 for v in st) and all(abs(v - 4 / PI) < 1e-3 for v in ab) and all(abs(v - 2) < 1e-6 for v in an))
n = 9
okc = True
for k in range(n):
    lamP = 4 * math.sin(PI * k / n) ** 2
    v = [math.cos(2 * PI * j * k / n) for j in range(n)]
    okc = okc and max(abs(a - lamP * b) for a, b in zip(mv(lap1(n, 'P'), v), v)) < 1e-12
    lamN = 4 * math.sin(PI * k / (2 * n)) ** 2
    v = [math.cos(PI * k * (j + 0.5) / n) for j in range(n)]
    okc = okc and max(abs(a - lamN * b) for a, b in zip(mv(lap1(n, 'N'), v), v)) < 1e-12
    lamD = 4 * math.sin(PI * (k + 1) / (2 * (n + 1))) ** 2
    v = [math.sin(PI * (k + 1) * (j + 1) / (n + 1)) for j in range(n)]
    okc = okc and max(abs(a - lamD * b) for a, b in zip(mv(lap1(n), v), v)) < 1e-12
check('F7 finite Fourier analysis: characters of Z/n diagonalize the periodic Laplacian; their even and odd parts under reflection are the'
      ' Neumann (cosine) and Dirichlet (sine) eigenvectors', okc)
useries = lambda x, t, N: x + sum(2 * (-1) ** n / (n * PI) * math.exp(-n * n * PI * PI * t) * math.sin(n * PI * x) for n in range(1, N + 1))
check('F8 inhomogeneous boundary values are removed by subtracting the steady state: u_t = u_xx, u(0) = 0, u(1) = 1 from zero data',
      abs(useries(0.3, 0.0, 200000)) < 1e-5 and abs(useries(0.3, 0.5, 50) - 0.3) < 1e-2 and
      abs(d1(lambda t: useries(0.3, t, 60), 0.05) - d2(lambda x: useries(x, 0.05, 60), 0.3)) < 1e-6)

sec('6. Harmonic functions')
uh = lambda x, y: x ** 3 - 3 * x * y * y + 2 * x - y
avg = lambda f, x0, y0, r: simpson(lambda th: f(x0 + r * math.cos(th), y0 + r * math.sin(th)), 0, 2 * PI, 400) / (2 * PI)
check('H1 mean value property: holds for a harmonic polynomial; for x^2 the circle average exceeds the central value by r^2/2',
      abs(avg(uh, 0.3, -0.2, 0.8) - uh(0.3, -0.2)) < 1e-12 and abs(avg(lambda x, y: x * x, 0.3, -0.2, 0.8) - 0.09 - 0.32) < 1e-12)


def grid_dirichlet(m, bval):
    """solve the five-point Laplace equation on the m x m interior of a square; bval(i, j) gives boundary values"""
    idx = {(i, j): i * m + j for i in range(m) for j in range(m)}
    A = [[0.0] * (m * m) for _ in range(m * m)]
    b = [0.0] * (m * m)
    for (i, j), r in idx.items():
        A[r][r] = 4.0
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            p = (i + di, j + dj)
            if p in idx:
                A[r][idx[p]] = -1.0
            else:
                b[r] += bval(*p)
    return solve(A, b), A, b, idx


bv = {}
rb = lambda i, j: bv.setdefault((i, j), random.uniform(-1, 1))
sol_, A_, b_, idx_ = grid_dirichlet(6, rb)
check('H2 maximum principle on a grid: a discrete harmonic function with random boundary values stays strictly between their extremes',
      min(bv.values()) < min(sol_) and max(sol_) < max(bv.values()))
a_ = 2.0
hb = lambda ph: (a_ * math.cos(ph)) ** 2 - (a_ * math.sin(ph)) ** 2 + 3 * a_ * math.cos(ph)
xr, yr = 0.7, -0.4
rr, th = math.hypot(xr, yr), math.atan2(yr, xr)
pf = (a_ * a_ - rr * rr) / (2 * PI) * simpson(lambda ph: hb(ph) / (a_ * a_ - 2 * a_ * rr * math.cos(th - ph) + rr * rr), 0, 2 * PI, 400)
check('H3 Poisson\'s formula recovers x^2 - y^2 + 3x inside the disk of radius 2 from its boundary values', abs(pf - (xr * xr - yr * yr + 3 * xr)) < 1e-12)


def ppow(p, e, n):
    r = {tuple([0] * n): Fr(1)}
    for _ in range(e):
        r = pmul(r, p)
    return r


def pcomp(p, subs):
    n = len(next(iter(subs[0])))
    r = {}
    for k, v in p.items():
        term = {tuple([0] * n): Fr(v)}
        for i, e in enumerate(k):
            term = pmul(term, ppow(subs[i], e, n))
        r = padd(r, term)
    return r


X_, Y_ = pvar(0, 2), pvar(1, 2)
rot = [padd(pscale(X_, Fr(3, 5)), pscale(Y_, Fr(-4, 5))), padd(pscale(X_, Fr(4, 5)), pscale(Y_, Fr(3, 5)))]
shear = [padd(X_, Y_), Y_]
sq = [padd(pmul(X_, X_), pmul(Y_, Y_), -1), pscale(pmul(X_, Y_), 2)]            # z -> z^2
p_ = {(4, 1): Fr(2), (1, 2): Fr(-3), (0, 3): Fr(1), (2, 0): Fr(5)}
u3 = {(3, 0): Fr(1), (1, 2): Fr(-3)}
jac = pscale(padd(pmul(X_, X_), pmul(Y_, Y_)), 4)                               # |f'|^2 = 4|z|^2
check('H4 the Laplacian is natural for isometries and, in the plane, for conformal maps up to the factor |f\'|^2 (exact polynomial identities);'
      ' it is not natural for a shear', plap(pcomp(p_, rot)) == pcomp(plap(p_), rot) and plap(pcomp(p_, shear)) != pcomp(plap(p_), shear)
      and plap(pcomp(u3, sq)) == {} and plap(pcomp(p_, sq)) == pmul(jac, pcomp(plap(p_), sq)))


def period(f, r=1.5):
    g = lambda th: (-d1(lambda y: f(r * math.cos(th), y), r * math.sin(th)) * (-r * math.sin(th)) + d1(lambda x: f(x, r * math.sin(th)), r * math.cos(th)) * (r * math.cos(th)))
    return simpson(g, 0, 2 * PI, 400)


pers = [period(lambda x, y: 0.5 * math.log(x * x + y * y)), period(lambda x, y: x * x - y * y), period(lambda x, y: x / (x * x + y * y))]
check('H5 the annulus has first cohomology: the conjugate differential of log r has period 2 pi, so log r has no harmonic conjugate there;'
      ' the periods of r^2 cos 2theta and r^{-1} cos theta vanish', abs(pers[0] - 2 * PI) < 1e-8 and abs(pers[1]) < 1e-8 and abs(pers[2]) < 1e-8)
beta = 1.5 * PI


def wedge(x, y):
    r, th = math.hypot(x, y), math.atan2(y, x) % (2 * PI)
    return r ** (PI / beta) * math.sin(PI * th / beta)


lapw = d2(lambda x: wedge(x, 0.4), -0.3) + d2(lambda y: wedge(-0.3, y), 0.4)
gradr = lambda r: math.hypot(d1(lambda x: wedge(x, r * math.sin(1.0)), r * math.cos(1.0), r * 1e-3), d1(lambda y: wedge(r * math.cos(1.0), y), r * math.sin(1.0), r * 1e-3))
check('H6 a re-entrant corner of angle 3 pi / 2: r^{2/3} sin(2 theta / 3) is harmonic and vanishes on both edges, and its gradient grows like r^{-1/3}',
      abs(lapw) < 1e-6 and abs(wedge(1.0, 0.0)) < 1e-15 and abs(wedge(0.0, -1.0)) < 1e-12 and abs(gradr(1e-3) / gradr(1e-6) - 0.1) < 1e-6)
m = 7
top = lambda i, j: 1.0 if i == -1 else 0.0
hp, A7, b7, idx7 = grid_dirichlet(m, top)
pcur = [0.0] * (m * m)
for _ in range(1500):                                         # run the absorbing walk: p <- (neighbours + boundary hits) / 4
    pcur = [(b7[r] - sum(A7[r][c] * pcur[c] for c in range(m * m) if c != r)) / 4.0 for r in range(m * m)]
check('H7 Dirichlet\'s problem is a hitting problem: the probability that a random walk on a 7 x 7 grid leaves through the top side solves the'
      ' five-point equation, and from the centre it is 1/4', max(abs(a - b) for a, b in zip(hp, pcur)) < 1e-10 and abs(hp[idx7[(3, 3)]] - 0.25) < 1e-12)

sec('7. Green\'s identities and Green\'s functions')
n = 8
Dm = [[(1.0 if j == i else -1.0 if j == i - 1 else 0.0) for j in range(n)] for i in range(n + 1)]
check('G1 Green\'s first identity on a grid: the Dirichlet Laplacian is D^T D, so (v, Lu) = (Dv, Du)',
      all(abs(mm(tr(Dm), Dm)[i][j] - lap1(n)[i][j]) < 1e-15 for i in range(n) for j in range(n)))
z = [random.uniform(-1, 1) for _ in range(36)]
en = lambda w, bv_: sum((w[idx_[(i, j)]] - (w[idx_[(i + di, j + dj)]] if (i + di, j + dj) in idx_ else bv_[(i + di, j + dj)])) ** 2 * (0.5 if (i + di, j + dj) in idx_ else 1.0)
                        for (i, j) in idx_ for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)))
zero_b = {k: 0.0 for k in bv}
Eu, Ew, Ez = en(sol_, bv), en([a + b for a, b in zip(sol_, z)], bv), en(z, zero_b)
check('G2 Dirichlet\'s principle: the harmonic function minimizes the energy among functions with its boundary values, and the excess energy'
      ' of a competitor is the energy of the difference', abs(Ew - Eu - Ez) < 1e-10 and Ez > 0)
Gm = inv(lap1(n))
check('G3 the Green\'s function is symmetric and positive: the inverse of the Dirichlet Laplacian on 8 points is min(i,j)(9 - max(i,j))/9',
      all(abs(Gm[i][j] - min(i + 1, j + 1) * (n + 1 - max(i + 1, j + 1)) / (n + 1)) < 1e-12 for i in range(n) for j in range(n)))
dist = lambda p, q: math.sqrt(sum((a - b) ** 2 for a, b in zip(p, q)))
Ghs = lambda x, x0: -1 / (4 * PI * dist(x, x0)) + 1 / (4 * PI * dist(x, (x0[0], x0[1], -x0[2])))
z0 = 0.7
mass = simpson(lambda s: (lambda rho: rho * z0 / (rho * rho + z0 * z0) ** 1.5 * z0 / (1 - s) ** 2)(z0 * s / (1 - s)) if s < 1 else 1.0, 0, 1, 2000)
check('G4 the half-space by reflection: the Green\'s function vanishes on the plane, is symmetric, and its normal derivative has total mass one',
      abs(Ghs((0.3, -1.2, 0.0), (0.1, 0.2, z0))) < 1e-16 and abs(Ghs((0.3, -1.2, 0.4), (0.1, 0.2, z0)) - Ghs((0.1, 0.2, z0), (0.3, -1.2, 0.4))) < 1e-16 and abs(mass - 1) < 1e-9)
a_ = 1.0


def Gball(x, x0):
    r0 = math.sqrt(sum(v * v for v in x0))
    xs = tuple(v * (a_ / r0) ** 2 for v in x0)
    return -1 / (4 * PI * dist(x, x0)) + (a_ / r0) / (4 * PI * dist(x, xs))


r0 = 0.6
pk = lambda th: (a_ * a_ - r0 * r0) / (4 * PI * a_ * (a_ * a_ + r0 * r0 - 2 * a_ * r0 * math.cos(th)) ** 1.5) * 2 * PI * a_ * a_ * math.sin(th)
onb = (math.sin(1.1) * math.cos(0.4), math.sin(1.1) * math.sin(0.4), math.cos(1.1))
check('G5 the ball by inversion: the Green\'s function vanishes on the sphere; the Poisson kernel has mass one and returns the value r0 of the'
      ' harmonic function z at distance r0 from the centre', abs(Gball(onb, (0.2, -0.3, 0.5))) < 1e-15 and
      abs(simpson(pk, 0, PI, 2000) - 1) < 1e-10 and abs(simpson(lambda th: pk(th) * a_ * math.cos(th), 0, PI, 2000) - r0) < 1e-10)


def rand_lap(nv, dens=0.7):
    Lr = [[0.0] * nv for _ in range(nv)]
    for i in range(nv):
        for j in range(i + 1, nv):
            if random.random() < dens:
                w = random.uniform(0.5, 2.0)
                Lr[i][j] -= w
                Lr[j][i] -= w
                Lr[i][i] += w
                Lr[j][j] += w
    return Lr


def kron_red(Lr, keep):
    rest = [i for i in range(len(Lr)) if i not in keep]
    if not rest:
        return [[Lr[i][j] for j in keep] for i in keep]
    Lii = [[Lr[i][j] for j in rest] for i in rest]
    Lib = [[Lr[i][j] for j in keep] for i in rest]
    sol = tr([solve(Lii, [Lib[r][c] for r in range(len(rest))]) for c in range(len(keep))])     # Lii^{-1} Lib
    return [[Lr[keep[a]][keep[b]] - sum(Lr[keep[a]][rest[r]] * sol[r][b] for r in range(len(rest))) for b in range(len(keep))] for a in range(len(keep))]


okg = True
for _ in range(10):
    # network 1 on vertices A(2) + M(2) + interior(3); network 2 on M(2) + C(2) + interior(3)
    L1, L2 = rand_lap(7), rand_lap(7)
    big = [[0.0] * 12 for _ in range(12)]                    # order: A0 A1 M0 M1 C0 C1 | I1(3) | I2(3)
    map1 = [0, 1, 2, 3, 6, 7, 8]
    map2 = [2, 3, 4, 5, 9, 10, 11]
    for Lr, mp in ((L1, map1), (L2, map2)):
        for i in range(7):
            for j in range(7):
                big[mp[i]][mp[j]] += Lr[i][j]
    direct = kron_red(big, [0, 1, 4, 5])
    K1, K2 = kron_red(L1, [0, 1, 2, 3]), kron_red(L2, [0, 1, 2, 3])
    mid = [[0.0] * 6 for _ in range(6)]
    for i in range(4):
        for j in range(4):
            mid[[0, 1, 2, 3][i]][[0, 1, 2, 3][j]] += K1[i][j]
            mid[[2, 3, 4, 5][i]][[2, 3, 4, 5][j]] += K2[i][j]
    comp = kron_red(mid, [0, 1, 4, 5])
    okg = okg and max(abs(direct[i][j] - comp[i][j]) for i in range(4) for j in range(4)) < 1e-10
ser = kron_red([[2.0, -2.0, 0.0], [-2.0, 5.0, -3.0], [0.0, -3.0, 3.0]], [0, 2])
check('G6 gluing is composition: the Dirichlet-to-Neumann matrix of two random networks glued along shared terminals is the composite of'
      ' their Dirichlet-to-Neumann matrices (ten trials); conductances 2 and 3 in series give 6/5', okg and abs(ser[0][1] + 1.2) < 1e-12)
uex = lambda x: x * (1 - x) / 2
coef = [simpson(lambda x: 1.0 * math.sin(k * PI * x), 0, 1, 400) / ((k * PI) ** 2 * 0.5) for k in (1, 2, 3)]
ug = lambda x: sum(c_ * math.sin((k + 1) * PI * x) for k, c_ in enumerate(coef))
orth = max(abs(simpson(lambda x: (d1(uex, x) - d1(ug, x)) * (k * PI) * math.cos(k * PI * x), 0, 1, 4000)) for k in (1, 2, 3))
check('G7 Galerkin approximation is orthogonal projection in the energy inner product: the error of the three-mode approximation to x(1-x)/2 is'
      ' energy-orthogonal to the trial space', orth < 1e-8, 'coefficients %.6f, %.6f, %.6f' % tuple(coef))
G1d = lambda x, y: x * (1 - y) if x < y else y * (1 - x)
gq = lambda f, x: simpson(lambda y: G1d(x, y) * f(y), 0, x, 400) + simpson(lambda y: G1d(x, y) * f(y), x, 1, 400)
check('G8 in one dimension the Green\'s function of -d^2/dx^2 on (0,1) is x(1-y) for x < y: it inverts the operator on 1 and on sin(pi x)',
      abs(gq(lambda y: 1.0, 0.3) - 0.105) < 1e-12 and abs(gq(lambda y: math.sin(PI * y), 0.3) - math.sin(0.3 * PI) / PI ** 2) < 1e-9)

sec('8. Waves and quanta in space')
c = 1.5
urad = lambda r, t: math.exp(-(r - c * t - 3) ** 2) / r
res = abs(d2(lambda t: urad(2.0, t), 0.4) - c * c * (d2(lambda r: urad(r, 0.4), 2.0) + 2 * d1(lambda r: urad(r, 0.4), 2.0) / 2.0))
pw = lambda nv: (lambda x, y, z, t: math.sin(3 * (t - (nv[0] * x + nv[1] * y + nv[2] * z) / c)))
def wres(u):
    return abs(d2(lambda t: u(0.2, 0.1, -0.3, t), 0.5) - c * c * (d2(lambda x: u(x, 0.1, -0.3, 0.5), 0.2) + d2(lambda y: u(0.2, y, -0.3, 0.5), 0.1) + d2(lambda z: u(0.2, 0.1, z, 0.5), -0.3)))
check('S1 waves in space: F(r - ct)/r solves the wave equation, and f(t - gamma(x)) does for a plane phase exactly when |grad gamma| = 1/c'
      ' (the source\'s characteristic condition)', res < 1e-6 and wres(pw((0.6, 0.0, 0.8))) < 1e-5 and wres(pw((0.6, 0.0, 0.9))) > 0.1)
c = 1.0
bumpr = lambda r: (math.exp(-1 / (1 - r * r)) if r < 1 else 0.0)
R = 5.0
kir = lambda t: t * 0.5 * simpson(lambda mu: bumpr(math.sqrt(R * R + t * t + 2 * R * t * mu)), -1, 1, 4000)
tot = simpson(lambda r: 2 * PI * r * bumpr(r), 0, 1, 2000)
def flat(t):
    f = lambda rho, th: bumpr(rho) * rho / math.sqrt(t * t - (R * R + rho * rho - 2 * R * rho * math.cos(th)))
    return simpson(lambda rho: simpson(lambda th: f(rho, th), 0, 2 * PI, 60), 0, 1, 60) / (2 * PI)
tails = [t * flat(t) * 2 * PI / tot for t in (8.0, 80.0, 800.0)]
check('S2 Huygens: in three dimensions a source in the unit ball is heard at distance 5 only for 4 < ct < 6; in two dimensions the signal'
      ' has a tail decaying like 1/t for ever', kir(3.0) == 0.0 and kir(5.0) > 1e-3 and kir(6.5) == 0.0 and all(v > 0 for v in tails) and abs(tails[2] - 1) < 1e-3,
      'three dimensions, ct = 3, 5, 6.5: %.4f, %.4f, %.4f; two dimensions, t u(t) relative to its limit at t = 8, 80, 800: %.4f, %.4f, %.4f' % (kir(3.0), kir(5.0), kir(6.5), *tails))
K = lambda x, t: cmath.exp(1j * x * x / (2 * t)) / cmath.sqrt(2j * PI * t)
resK = abs(1j * d1(lambda t: K(0.7, t), 0.9) + 0.5 * d2(lambda x: K(x, 0.9), 0.7))
heatc = lambda x, tau: cmath.exp(-x * x / (2 * tau)) / cmath.sqrt(2 * PI * tau)       # heat kernel with diffusivity 1/2 at complex time
pk_ = lambda x, t: cmath.exp(-x * x / (2 * (1 + 1j * t))) / cmath.sqrt(1 + 1j * t)
norms = [simpson(lambda x: abs(pk_(x, t)) ** 2, -40, 40, 8000) for t in (0.0, 2.0, 5.0)]
widths = [simpson(lambda x: x * x * abs(pk_(x, t)) ** 2, -60, 60, 12000) / norms[i] for i, t in enumerate((0.0, 2.0, 5.0))]
check('S3 the Schroedinger kernel is the heat kernel at imaginary time; the flow is unitary where the heat flow is a contraction, and a Gaussian'
      ' packet spreads with mean square width (1 + t^2)/2', resK < 1e-6 and abs(K(0.7, 0.9) - heatc(0.7, 0.9j)) < 1e-15
      and max(norms) - min(norms) < 1e-10 and all(abs(w - (1 + t * t) / 2) < 1e-8 for w, t in zip(widths, (0.0, 2.0, 5.0))))
okh, polys = True, []
for nq in (1, 2, 3, 4):
    be = Fr(1, nq)
    a = [Fr(1)]
    for k in range(1, 8):
        a.append((be * k - 1) * a[-1] / Fr(k * (k + 1), 2))
    okh = okh and all(v == 0 for v in a[nq:]) and a[nq - 1] != 0
    Rf = lambda r, a=a, be=float(be): sum(float(v) * r ** k for k, v in enumerate(a)) * math.exp(-be * r)
    for r in (0.7, 2.3, 6.0):
        okh = okh and abs(-d2(Rf, r) - 2 * d1(Rf, r) / r - 2 * Rf(r) / r + float(be) ** 2 * Rf(r)) < 1e-7
    polys.append([str(v) for v in a[:nq]])
check('S4 the hydrogen atom in the source\'s units: the series terminates exactly when beta = 1/n, the radial states satisfy the equation with'
      ' eigenvalue -1/n^2, and level n has multiplicity n^2', okh and all(sum(2 * l + 1 for l in range(nq)) == nq * nq for nq in range(1, 6)), 'polynomials %s' % polys)
h = 0.02
xs = [-10 + h * (i + 1) for i in range(999)]
ho = tri_eigs([2 / h ** 2 + x * x for x in xs], [-1 / h ** 2] * 998, 4)
check('S5 the harmonic oscillator -v\'\' + x^2 v = lambda v has eigenvalues 1, 3, 5, 7', all(abs(v - (2 * k + 1)) < 2e-3 for k, v in enumerate(ho)), '%.5f, %.5f, %.5f, %.5f' % tuple(ho))

sec('9. Symmetry and special functions')
X1, X2, X3 = pvar(0, 3), pvar(1, 3), pvar(2, 3)
Lop = [lambda p: padd(pmul(X2, pdiff(p, 2)), pmul(X3, pdiff(p, 1)), -1),
       lambda p: padd(pmul(X3, pdiff(p, 0)), pmul(X1, pdiff(p, 2)), -1),
       lambda p: padd(pmul(X1, pdiff(p, 1)), pmul(X2, pdiff(p, 0)), -1)]
Eul = lambda p: {k: v * sum(k) for k, v in p.items() if sum(k)}
r2 = padd(padd(pmul(X1, X1), pmul(X2, X2)), pmul(X3, X3))
oky = all(kernel_dim(plap, 3, l) == 2 * l + 1 for l in range(8))
okc = True
for _ in range(6):
    p = {(random.randint(0, 3), random.randint(0, 3), random.randint(0, 3)): Fr(random.randint(-4, 4)) for _ in range(5)}
    p = {k: v for k, v in p.items() if v != 0} or {(1, 1, 0): Fr(1)}
    L2p = {}
    for Lo in Lop:
        L2p = padd(L2p, Lo(Lo(p)), -1)                                  # L^2 = -(L1^2 + L2^2 + L3^2)
    EEp = padd(Eul(Eul(p)), Eul(p))
    okc = okc and pmul(r2, plap(p)) == padd(EEp, L2p, -1)               # r^2 Laplace = E(E+1) - L^2
    okc = okc and padd(Lop[0](Lop[1](p)), Lop[1](Lop[0](p)), -1) == pscale(Lop[2](p), -1)       # [L1, L2] = -L3
    okc = okc and all(plap(Lo(p)) == Lo(plap(p)) for Lo in Lop)
check('Y1 rotations: harmonic homogeneous polynomials of degree l in three variables form a space of dimension 2l+1; the rotation fields'
      ' satisfy [L1, L2] = -L3 and commute with the Laplacian; and r^2 Laplace = E(E+1) - L^2, so L^2 = l(l+1) on that space (exact)', oky and okc)


def pol_mul(a, b):
    r = [Fr(0)] * (len(a) + len(b) - 1)
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            r[i + j] += x * y
    return r


pol_int = lambda a: sum(c * (Fr(1) - Fr(-1) ** (k + 1)) / (k + 1) for k, c in enumerate(a))
pol_d = lambda a: [k * c for k, c in enumerate(a)][1:] or [Fr(0)]
okl = True
for l in range(8):
    P = legendre(l)
    dP = pol_d(P)
    t = pol_d(pol_mul([Fr(1), Fr(0), Fr(-1)], dP))                      # ((1 - s^2) P')'
    lhs = [(t[k] if k < len(t) else 0) + l * (l + 1) * (P[k] if k < len(P) else 0) for k in range(max(len(t), len(P)))]
    okl = okl and all(v == 0 for v in lhs) and sum(P) == 1
    for m_ in range(8):
        okl = okl and pol_int(pol_mul(P, legendre(m_))) == (Fr(2, 2 * l + 1) if l == m_ else 0)
check('Y2 Legendre polynomials: the zonal equation ((1-s^2)P\')\' + l(l+1)P = 0, P(1) = 1, and orthogonality with square norm 2/(2l+1) (exact, l < 8)', okl)
jz = lambda n, a, b: bisect(lambda x: besselj(n, x), a, b)
zeros = [jz(0, 2, 3), jz(1, 3, 4.5), jz(2, 4.5, 5.4), jz(0, 5.4, 6), jz(0, 8, 9)]
bes = max(abs(x * x * d2(lambda s: besselj(n, s), x) + x * d1(lambda s: besselj(n, s), x) + (x * x - n * n) * besselj(n, x)) for n, x in [(0, 1.3), (1, 2.7), (3, 4.1)])
check('Y3 Bessel functions: the equation, and the zeros that give the frequencies of a circular drum',
      bes < 1e-6 and all(abs(a - b) < 1e-6 for a, b in zip(zeros, [2.404826, 3.831706, 5.135622, 5.520078, 8.653728])),
      'zeros %.6f, %.6f, %.6f, %.6f; frequency ratios %.4f, %.4f, %.4f' % (*zeros[:4], zeros[1] / zeros[0], zeros[2] / zeros[0], zeros[3] / zeros[0]))
ea, eb = jacobi_eig(lap1(4))[0], jacobi_eig(lap1(5))[0]
es = jacobi_eig(kron_sum(lap1(4), lap1(5)))[0]
check('Y4 separation of variables: the spectrum of a product is the set of sums (a 4 x 5 grid)',
      max(abs(a - b) for a, b in zip(es, sorted(x + y for x in ea for y in eb))) < 1e-10)


def nodal_domains(vec, m, n):
    sgn = [0 if abs(v) < 1e-9 else (1 if v > 0 else -1) for v in vec]
    seen, cnt = set(), 0
    for s in range(m * n):
        if sgn[s] == 0 or s in seen:
            continue
        cnt += 1
        st = [s]
        seen.add(s)
        while st:
            q = st.pop()
            i, j = divmod(q, n)
            for a, b in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                if 0 <= a < m and 0 <= b < n and a * n + b not in seen and sgn[a * n + b] == sgn[s]:
                    seen.add(a * n + b)
                    st.append(a * n + b)
    return cnt


_, vp = jacobi_eig(lap1(12))
changes = [sum(1 for i in range(11) if v[i] * v[i + 1] < 0) for v in vp]
ev56, vec56 = jacobi_eig(kron_sum(lap1(5), lap1(6)))
nd = [nodal_domains(v, 5, 6) for v in vec56[:8]]
sq_ev = sorted(a * a + b * b for a in range(1, 5) for b in range(1, 5))[:6]
check('Y5 nodes: the k-th eigenvector of an interval has k-1 sign changes; on a 5 x 6 grid, whose eigenvalues are simple, the k-th has at most'
      ' k nodal domains; and the square has eigenvalues 2, 5, 5, 8, 10, 10 as the source lists', changes == list(range(12)) and all(d <= k + 1 for k, d in enumerate(nd))
      and nd[0] == 1 and nd[1] == 2 and sq_ev == [2, 5, 5, 8, 10, 10], 'nodal domains of the first eight: %s' % nd)
e55 = jacobi_eig(kron_sum(lap1(5), lap1(5)))[0]
L55 = kron_sum(lap1(5), lap1(5))
Rq = [[1.0 if (j // 5, j % 5) == (i % 5, 4 - i // 5) else 0.0 for j in range(25)] for i in range(25)]      # quarter turn of the grid
comm = max(abs(a - b) for ra, rb in zip(mm(Rq, L55), mm(L55, Rq)) for a, b in zip(ra, rb))
check('Y6 symmetry forces degeneracy: the Laplacian of a square grid commutes with the quarter turn and its second eigenvalue is double;'
      ' on the 5 x 6 grid the second eigenvalue is simple', comm < 1e-12 and abs(e55[1] - e55[2]) < 1e-10 and abs(ev56[1] - ev56[2]) > 1e-3)

sec('10. Eigenvalues')
w1, w2 = [Fr(0), Fr(1), Fr(-1)], pol_mul([Fr(0), Fr(1), Fr(-1)], [Fr(0), Fr(1), Fr(-1)])
i01 = lambda a: sum(c / (k + 1) for k, c in enumerate(a))
Am = [[i01(pol_mul(pol_d(p), pol_d(q))) for q in (w1, w2)] for p in (w1, w2)]
Bm = [[i01(pol_mul(p, q)) for q in (w1, w2)] for p in (w1, w2)]
qa = float(Bm[0][0] * Bm[1][1] - Bm[0][1] ** 2)
qb = float(-(Am[0][0] * Bm[1][1] + Am[1][1] * Bm[0][0] - 2 * Am[0][1] * Bm[0][1]))
qc = float(Am[0][0] * Am[1][1] - Am[0][1] ** 2)
ritz = sorted([(-qb - math.sqrt(qb * qb - 4 * qa * qc)) / (2 * qa), (-qb + math.sqrt(qb * qb - 4 * qa * qc)) / (2 * qa)])
check('L1 Rayleigh-Ritz gives upper bounds: on (0,1) the trial function x(1-x) gives 10, and adding x^2(1-x)^2 gives 9.86975 against pi^2 = 9.86960;'
      ' the second Ritz value bounds the third eigenvalue 9 pi^2', Am[0][0] / Bm[0][0] == 10 and 0 < ritz[0] - PI ** 2 < 2e-4 and ritz[1] > 9 * PI ** 2,
      'Ritz values %.6f, %.4f' % tuple(ritz))
okI = True
for _ in range(10):
    Ar = [[0.0] * 8 for _ in range(8)]
    for i in range(8):
        for j in range(i, 8):
            Ar[i][j] = Ar[j][i] = random.uniform(-1, 1)
    ea_, eb_ = jacobi_eig(Ar)[0], jacobi_eig([r[:7] for r in Ar[:7]])[0]
    okI = okI and all(ea_[k] <= eb_[k] + 1e-12 and eb_[k] <= ea_[k + 1] + 1e-12 for k in range(7))
check('L2 the minimax principle in its finite form: eigenvalues of a compression interlace those of the matrix (ten random cases)', okI)
cells = [(i, j) for i in range(6) for j in range(6)]
Lsh = [(i, j) for (i, j) in cells if not (i >= 3 and j >= 3)]


def region_lap(cs):
    ix = {c_: k for k, c_ in enumerate(cs)}
    Lr = [[0.0] * len(cs) for _ in cs]
    for (i, j), k in ix.items():
        Lr[k][k] = 4.0
        for p in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
            if p in ix:
                Lr[k][ix[p]] = -1.0
    return Lr


eS, eL = jacobi_eig(region_lap(cells))[0], jacobi_eig(region_lap(Lsh))[0]
corner = 0.5 + (0.65 + 0.05) / math.sqrt(2)
check('L3 enlarging a domain lowers every Dirichlet eigenvalue (an L-shaped region inside a 6 x 6 square); for Neumann conditions this fails:'
      ' a 1.3 x 0.1 rectangle fits inside the unit square along its diagonal and has the smaller second eigenvalue',
      all(eL[k] >= eS[k] - 1e-12 for k in range(len(eL))) and corner < 1 and PI ** 2 / 1.69 < PI ** 2, 'first eigenvalues: square %.4f, L-shape %.4f; Neumann: %.3f < %.3f' % (eS[0], eL[0], PI ** 2 / 1.69, PI ** 2))
ar, br = 1.0, math.sqrt(2.0)
Area, Per = ar * br, 2 * (ar + br)


def count(lam):
    c_, m_ = 0, 1
    while PI ** 2 * m_ * m_ / ar ** 2 < lam:
        rest = lam - PI ** 2 * m_ * m_ / ar ** 2
        c_ += int(math.floor(math.sqrt(rest) * br / PI - 1e-12))
        m_ += 1
    return c_


rows = []
okW = True
for lam in (2000.0, 8000.0, 32000.0):
    Nn = count(lam)
    two = Area * lam / (4 * PI) - Per * math.sqrt(lam) / (4 * PI)
    okW = okW and abs(Nn - two) / Nn < 0.02
    rows.append('lambda=%g: N=%d, two-term Weyl %.1f, lambda/N=%.3f' % (lam, Nn, two, lam / Nn))
check('L4 Weyl\'s law for a 1 x sqrt 2 rectangle: N(lambda) against A lambda/(4 pi) - P sqrt(lambda)/(4 pi), and lambda_n/n tending to 4 pi/A = 8.886',
      okW and abs(32000.0 / count(32000.0) - 4 * PI / Area) < 0.25, '; '.join(rows))
ztrace = lambda t: sum(math.exp(-PI ** 2 * m_ * m_ * t / ar ** 2) for m_ in range(1, 400)) * sum(math.exp(-PI ** 2 * n_ * n_ * t / br ** 2) for n_ in range(1, 400))
hk = [ztrace(t) - (Area / (4 * PI * t) - Per / (8 * math.sqrt(PI * t)) + 0.25) for t in (0.02, 0.01, 0.005)]
check('L5 the heat trace of a rectangle is A/(4 pi t) - P/(8 sqrt(pi t)) + 1/4 up to exponentially small terms: one can hear the area, the perimeter'
      ' and the four corners', all(abs(v) < 1e-9 for v in hk), 'differences at t = 0.02, 0.01, 0.005: %.1e, %.1e, %.1e' % tuple(hk))
a7, t7 = 1.7, 0.3
lhs = sum(math.exp(-PI ** 2 * m_ * m_ * t7 / a7 ** 2) for m_ in range(1, 200))
rhs = a7 / (2 * math.sqrt(PI * t7)) - 0.5 + a7 / math.sqrt(PI * t7) * sum(math.exp(-(2 * a7 * k) ** 2 / (4 * t7)) for k in range(1, 200))
check('L6 a trace formula: the sum over the spectrum of an interval equals a sum over its closed geodesics, of lengths 2ak (Poisson summation)', abs(lhs - rhs) < 1e-14)


def cospectral_search(n):
    prs = [(i, j) for i in range(n) for j in range(i + 1, n)]
    by = {}
    for mask in range(1 << len(prs)):
        deg = [0] * n
        Lg = [[0] * n for _ in range(n)]
        for b, (i, j) in enumerate(prs):
            if mask >> b & 1:
                Lg[i][j] = Lg[j][i] = -1
                deg[i] += 1
                deg[j] += 1
        if min(deg) == 0:
            continue
        for i in range(n):
            Lg[i][i] = deg[i]
        cp = charpoly_int(Lg)
        if cp[n - 1] == 0:
            continue                                         # disconnected
        by.setdefault(cp, {}).setdefault(tuple(sorted(deg)), [prs[b] for b in range(len(prs)) if mask >> b & 1])
    return {cp: d for cp, d in by.items() if len(d) > 1}


c5, c6 = cospectral_search(5), cospectral_search(6)
first = c6.get((1, -14, 73, -176, 192, -72, 0), {})
check('L7 one cannot hear the shape of a graph: among connected graphs on at most five vertices no two with different degree sequences share a'
      ' Laplacian spectrum; on six vertices two spectra are shared, the first by graphs with seven edges',
      len(c5) == 0 and len(c6) == 2 and sorted(first) == [(1, 2, 2, 3, 3, 3), (2, 2, 2, 2, 2, 4)], '; '.join('%s: %s' % (k, v) for k, v in sorted(first.items())))
U8 = [1, 3, 5, 7]
G8 = [(a, u) for a in range(8) for u in U8]
gmul = lambda g, h_: ((g[0] + g[1] * h_[0]) % 8, (g[1] * h_[1]) % 8)
ginv = lambda g: next(h_ for h_ in G8 if gmul(g, h_) == (0, 1))
H1, H2 = [(0, 1), (0, 3), (0, 5), (0, 7)], [(0, 1), (4, 3), (4, 5), (0, 7)]
classes = {frozenset(gmul(gmul(x, g), ginv(x)) for x in G8) for g in G8}
almost = all(len(cl & set(H1)) == len(cl & set(H2)) for cl in classes)
conj = any({gmul(gmul(x, h_), ginv(x)) for h_ in H1} == set(H2) for x in G8)


def schreier(H, Sg):
    cos, reps = {}, []
    for g in G8:
        cl = frozenset(gmul(g, h_) for h_ in H)
        if cl not in cos:
            cos[cl] = len(reps)
            reps.append(g)
    Ad = [[0] * len(reps) for _ in reps]
    for i, g in enumerate(reps):
        for s_ in Sg:
            for t_ in (s_, ginv(s_)):
                Ad[i][cos[frozenset(gmul(gmul(t_, g), h_) for h_ in H)]] += 1
    return Ad


Sg = [(0, 3), (0, 5), (1, 7)]
A1, A2 = schreier(H1, Sg), schreier(H2, Sg)
loops = (sorted(A1[i][i] for i in range(8)), sorted(A2[i][i] for i in range(8)))
check('L8 Sunada\'s method in the smallest case: in the group of order 32 of affine maps of Z/8 two subgroups of order 4 meet every conjugacy class'
      ' equally and are not conjugate; the two quotient graphs on 8 vertices have the same spectrum and are not isomorphic',
      len(classes) == 11 and almost and not conj and charpoly_int(A1) == charpoly_int(A2) and loops[0] != loops[1], 'loops at the vertices: %s and %s' % loops)
ev10, vec10 = jacobi_eig(lap1(10))
comp = max(abs(sum(v[i] * v[j] for v in vec10) - (1.0 if i == j else 0.0)) for i in range(10) for j in range(10))
check('L9 completeness in finite dimensions: the eigenvectors resolve the identity', comp < 1e-12)

sec('11. Distributions and transforms')
phi_t = lambda x: math.exp(-x * x) * math.cos(x)                 # phi(0) = 1, phi''(0) = -3
rt = [(simpson(lambda x: heat(x, t) * phi_t(x), -12, 12, 20000) - 1) / t for t in (1e-2, 1e-3)]
check('T1 the delta function as a limit: (S(.,t), phi) = phi(0) + t phi\'\'(0) + O(t^2)', abs(rt[0] + 3) < 0.2 and abs(rt[1] + 3) < 0.02, 'difference quotients %.4f, %.5f against -3' % tuple(rt))
tf = lambda x: bump(x, 0.3)
check('T2 derivatives by duality: H\' = delta and |x|\'\' = 2 delta against a test function supported in (-0.7, 1.3)',
      abs(-simpson(lambda x: d1(tf, x), 0, 1.3, 4000) - tf(0.0)) < 1e-8 and abs(simpson(lambda x: abs(x) * d2(tf, x, 2e-3), -0.7, 0, 4000) + simpson(lambda x: abs(x) * d2(tf, x, 2e-3), 0, 1.3, 4000) - 2 * tf(0.0)) < 1e-6)
fund = simpson(lambda r: (-1 / (4 * PI * r)) * (4 * r * r - 6) * math.exp(-r * r) * 4 * PI * r * r if r else 0.0, 0, 12, 4000)
check('T3 the fundamental solution: the Laplacian of -1/(4 pi r) is delta in three dimensions (tested against exp(-r^2))', abs(fund - 1) < 1e-9)
FT = lambda f, k, R=12, n=6000: simpson(lambda x: f(x) * cmath.exp(-1j * k * x), -R, R, n)
gauss = lambda x: math.exp(-x * x / 2) / math.sqrt(2 * PI)
f4 = lambda x: x * math.exp(-x * x) + math.exp(-(x - 1) ** 2)
df4 = lambda x: (1 - 2 * x * x) * math.exp(-x * x) - 2 * (x - 1) * math.exp(-(x - 1) ** 2)
pl = simpson(lambda k: abs(FT(f4, k, 10, 1000)) ** 2, -12, 12, 600) / (2 * PI) - simpson(lambda x: f4(x) ** 2, -10, 10, 2000)
xp = {(3,): Fr(2), (1,): Fr(-1), (0,): Fr(5)}
weyl = padd(pdiff(pmul(pvar(0, 1), xp), 0), pmul(pvar(0, 1), pdiff(xp, 0)), -1) == xp
check('T4 the Fourier transform: Gaussians to Gaussians, differentiation to multiplication by ik, Plancherel; and the relation [d/dx, x] = 1'
      ' that it preserves', all(abs(FT(gauss, k) - math.exp(-k * k / 2)) < 1e-10 for k in (0.0, 0.7, 2.5)) and all(abs(FT(df4, k) - 1j * k * FT(f4, k)) < 1e-9 for k in (0.4, 1.9))
      and abs(pl) < 1e-8 and weyl)
inv5 = max(abs(simpson(lambda k: math.exp(-k * k * t) * math.cos(k * x), -40, 40, 8000) / (2 * PI) - heat(x, t)) for x, t in [(0.3, 0.5), (1.5, 0.2)])
check('T5 the source function from the transform: the inverse transform of exp(-k^2 t) is the heat kernel', inv5 < 1e-10)
ev3, vec3 = jacobi_eig(lap1(3))
s_ = 0.8
Rm = inv([[(s_ if i == j else 0.0) + lap1(3)[i][j] for j in range(3)] for i in range(3)])
sem = lambda t, i, j: sum(math.exp(-lam * t) * v[i] * v[j] for lam, v in zip(ev3, vec3))
check('T6 the Laplace transform of a semigroup is its resolvent: the integral of exp(-st) exp(-tL) is (s + L)^{-1} (3 x 3 check)',
      max(abs(simpson(lambda t: math.exp(-s_ * t) * sem(t, i, j), 0, 30, 12000) - Rm[i][j]) for i in range(3) for j in range(3)) < 1e-9)
pv = lambda x: 1 / (1 + (x - 0.5) ** 2)
errs = [abs(simpson(lambda x: (1 / (x - 1j * eps)).imag / PI * pv(x), -400, 400, 400000) - pv(0.0)) for eps in (0.1, 0.01)]
check('T7 boundary values: the imaginary part of 1/(pi(x - i eps)) is the Poisson kernel of the half-plane and tends to delta, with error of order eps',
      abs((1 / (0.3 - 0.02j)).imag / PI - 0.02 / (PI * (0.09 + 0.0004))) < 1e-15 and errs[1] < errs[0] / 5 and errs[1] < 0.01, 'errors %.4f, %.5f' % tuple(errs))

sec('12. Discretization')


def run_explicit(s, J, steps, u0):
    P = step_matrix(J, s)
    u_, norms = list(u0), []
    for _ in range(steps):
        u_ = mv(P, u_)
        norms.append(math.sqrt(dot(u_, u_)))
    return u_, norms


J = 20
u0 = [random.uniform(-1, 1) for _ in range(J)]
_, nb = run_explicit(0.52, J, 400, u0)
pred = abs(1 - 2 * 0.52 * (1 + math.cos(PI / (J + 1))))
_, ns = run_explicit(0.5, J, 400, u0)
check('N1 von Neumann: the explicit diffusion scheme has amplification 1 - 2s(1 - cos k dx); at s = 0.52 the computed growth per step equals'
      ' the predicted maximum; at s = 0.5 nothing grows', abs(nb[-1] / nb[-2] - pred) < 1e-9 and pred > 1 and ns[-1] < ns[0], 'growth per step %.6f' % pred)


def exp_err(s, J):
    dx = 1.0 / J
    steps = round(0.1 / (s * dx * dx))
    P = step_matrix(J - 1, s)
    u_ = [math.sin(PI * (j + 1) * dx) for j in range(J - 1)]
    for _ in range(steps):
        u_ = mv(P, u_)
    return max(abs(u_[j] - math.exp(-PI * PI * 0.1) * math.sin(PI * (j + 1) * dx)) for j in range(J - 1))


r2_, r6_ = exp_err(0.5, 10) / exp_err(0.5, 20), exp_err(1 / 6, 10) / exp_err(1 / 6, 20)
check('N2 consistency: halving the mesh divides the error by 4 at s = 1/2 and by 16 at the special ratio s = 1/6', abs(r2_ - 4) < 0.2 and abs(r6_ - 16) < 1.0, 'ratios %.2f, %.2f' % (r2_, r6_))
cn = lambda s, th: (1 - s * (1 - math.cos(th))) / (1 + s * (1 - math.cos(th)))
lamh = 2 * (1 - math.cos(PI / 40)) * 1600
cn_err = lambda dt: abs(((1 - lamh * dt / 2) / (1 + lamh * dt / 2)) ** round(0.1 / dt) - math.exp(-lamh * 0.1))
check('N3 Crank-Nicolson is stable for every s and of second order in time', all(abs(cn(s, th)) <= 1 for s in (0.1, 1, 10, 100, 1e4) for th in (0.1, 1.0, PI))
      and abs(cn_err(0.01) / cn_err(0.005) - 4) < 0.1, 'error ratio %.3f' % (cn_err(0.01) / cn_err(0.005)))
c = 1.0
exact = lambda x, t: math.exp(-(x - c * t - 1) ** 2) + 0.5 * math.sin(x + c * t)
dx = 0.1
old = [exact(j * dx, 0.0) for j in range(-80, 81)]
cur = [exact(j * dx, dx) for j in range(-80, 81)]
dev = 0.0
for n_ in range(2, 40):
    new = [cur[j + 1] + cur[j - 1] - old[j] for j in range(1, len(cur) - 1)]
    off = n_ - 1
    dev = max(dev, max(abs(new[j] - exact((j - 80 + off) * dx, n_ * dx)) for j in range(len(new))))
    old, cur = cur[1:-1], new
Np = 32
gr = []
for s in (1.1,):
    o_, c_ = [(-1.0) ** j for j in range(Np)], [(-1.0) ** j * 1.3 for j in range(Np)]
    for _ in range(60):
        n_ = [s * (c_[(j + 1) % Np] + c_[j - 1]) + 2 * (1 - s) * c_[j] - o_[j] for j in range(Np)]
        o_, c_ = c_, n_
    gr.append(abs(c_[0] / o_[0]))
pfac = -2 * 1.1
check('N4 the wave scheme: at c dt = dx it is the parallelogram identity and reproduces exact solutions to rounding; at (c dt/dx)^2 = 1.1 the'
      ' sawtooth grows by the predicted factor per step', dev < 1e-12 and abs(gr[0] - abs(1 + pfac - math.sqrt(pfac * pfac + 2 * pfac))) < 1e-9, 'deviation %.1e; growth %.4f' % (dev, gr[0]))


def wave_num(phi_, J, ratio, nsteps, dxx):
    s = ratio * ratio
    o_ = [phi_(j * dxx) for j in range(-J, J + 1)]
    c_ = [o_[j] + 0.5 * s * (o_[j + 1] - 2 * o_[j] + o_[j - 1]) if 0 < j < 2 * J else o_[j] for j in range(2 * J + 1)]
    for _ in range(nsteps - 1):
        n_ = [0.0] * (2 * J + 1)
        for j in range(1, 2 * J):
            n_[j] = s * (c_[j + 1] + c_[j - 1]) + 2 * (1 - s) * c_[j] - o_[j]
        o_, c_ = c_, n_
    return c_[J]


base = lambda x: math.exp(-x * x)
pert = lambda x: base(x) + (math.exp(-1 / (1 - ((x - 1.0) / 0.2) ** 2)) if abs(x - 1.0) < 0.2 else 0.0)
same = all(wave_num(base, 200, 2.0, n_, 1.0 / (2 * n_)) == wave_num(pert, 200, 2.0, n_, 1.0 / (2 * n_)) for n_ in (10, 20, 40))
true_diff = 0.5 * (pert(1.0) + pert(-1.0)) - 0.5 * (base(1.0) + base(-1.0))
check('N5 the stability condition is causality: at c dt = 2 dx the scheme at (0, 1) reads data only from [-1/2, 1/2], so it returns the same'
      ' number for two data sets that differ near x = 1, at every refinement, while the exact solutions differ there by 1/(2e)',
      same and abs(true_diff - 0.5 / math.e) < 1e-15)
Ng = 16
mgrid = Ng - 1


def sweeps(method, omega=1.0, tol=1e-6, cap=5000):
    e_ = [[random.uniform(-1, 1) if 0 < i < Ng and 0 < j < Ng else 0.0 for j in range(Ng + 1)] for i in range(Ng + 1)]
    n0 = math.sqrt(sum(v * v for r in e_ for v in r))
    for it in range(1, cap):
        if method == 'J':
            e_ = [[0.25 * (e_[i + 1][j] + e_[i - 1][j] + e_[i][j + 1] + e_[i][j - 1]) if 0 < i < Ng and 0 < j < Ng else 0.0 for j in range(Ng + 1)] for i in range(Ng + 1)]
        else:
            for i in range(1, Ng):
                for j in range(1, Ng):
                    e_[i][j] += omega * (0.25 * (e_[i + 1][j] + e_[i - 1][j] + e_[i][j + 1] + e_[i][j - 1]) - e_[i][j])
        if math.sqrt(sum(v * v for r in e_ for v in r)) < tol * n0:
            return it
    return cap


random.seed(7)
itJ, itG = sweeps('J'), sweeps('G')
om = 2 / (1 + math.sin(PI / Ng))
itS = sweeps('S', om)
random.seed(20261118)
rhoJ = math.cos(PI / Ng)
check('N6 iteration for Laplace\'s equation on a 16 x 16 grid: Jacobi contracts by cos(pi/N) per sweep, Gauss-Seidel by its square (twice as fast,'
      ' as the source says), and over-relaxation with omega = 2/(1 + sin(pi/N)) is an order of magnitude faster still',
      abs(itJ / itG - 2) < 0.15 and itS < itG / 5 and 0.7 * math.log(1e-6) / math.log(rhoJ) < itJ <= math.log(1e-6) / math.log(rhoJ), 'sweeps to reduce a random error by 1e-6: %d, %d, %d; bound for Jacobi %d; omega = %.4f' % (itJ, itG, itS, math.log(1e-6) / math.log(rhoJ), om))


def fem1d(N, f):
    h = 1.0 / N
    Kf = [[0.0] * (N - 1) for _ in range(N - 1)]
    b_ = [0.0] * (N - 1)
    for e in range(N):                                           # element [e h, (e+1) h]
        for a in (0, 1):
            ia = e + a - 1
            if not 0 <= ia < N - 1:
                continue
            hat = (lambda x, e=e, a=a: (x - e * h) / h if a else ((e + 1) * h - x) / h)
            b_[ia] += simpson(lambda x: f(x) * hat(x), e * h, (e + 1) * h, 40)
            for bb in (0, 1):
                ib = e + bb - 1
                if 0 <= ib < N - 1:
                    Kf[ia][ib] += (1.0 if a == bb else -1.0) / h
    return solve(Kf, b_), Kf


u8, K8 = fem1d(8, lambda x: PI ** 2 * math.sin(PI * x))
u16, _ = fem1d(16, lambda x: PI ** 2 * math.sin(PI * x))
nod = max(abs(u8[i] - math.sin(PI * (i + 1) / 8)) for i in range(7))


def en_err(uh, N):
    h = 1.0 / N
    vals = [0.0] + uh + [0.0]
    return math.sqrt(sum(simpson(lambda x: (PI * math.cos(PI * x) - (vals[e + 1] - vals[e]) / h) ** 2, e * h, (e + 1) * h, 40) for e in range(N)))


check('N7 finite elements in one dimension: the stiffness matrix of hat functions is the difference Laplacian divided by h; the Galerkin solution'
      ' is exact at the nodes; the energy error halves with h', all(abs(K8[i][j] - lap1(7)[i][j] * 8) < 1e-12 for i in range(7) for j in range(7))
      and nod < 1e-9 and abs(en_err(u8, 8) / en_err(u16, 16) - 2) < 0.02, 'nodal error %.1e; energy errors %.4f, %.4f' % (nod, en_err(u8, 8), en_err(u16, 16)))


def p1_stiffness(tri):
    (x1, y1), (x2, y2), (x3, y3) = tri
    area = abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) / 2
    g = [((y2 - y3), (x3 - x2)), ((y3 - y1), (x1 - x3)), ((y1 - y2), (x2 - x1))]
    return [[(g[a][0] * g[b][0] + g[a][1] * g[b][1]) / (4 * area) for b in range(3)] for a in range(3)]


Kg = {}
for i in range(4):
    for j in range(4):
        for tri in (((i, j), (i + 1, j), (i, j + 1)), ((i + 1, j), (i + 1, j + 1), (i, j + 1))):
            ke = p1_stiffness(tri)
            for a in range(3):
                for b in range(3):
                    Kg[(tri[a], tri[b])] = Kg.get((tri[a], tri[b]), 0.0) + ke[a][b]
row = {q: Kg.get(((2, 2), q), 0.0) for q in [(2, 2), (3, 2), (1, 2), (2, 3), (2, 1), (3, 3), (1, 1), (3, 1), (1, 3)]}
check('N8 finite elements in the plane: linear elements on a uniform triangulation of the square give the five-point scheme',
      [round(v, 12) for v in row.values()] == [4, -1, -1, -1, -1, 0, 0, 0, 0])
mr = 6
Vn = [('i', k) for k in range(mr)] + [('o', k) for k in range(mr)]
vid = {v: k for k, v in enumerate(Vn)}
tris = []
for k in range(mr):
    k1 = (k + 1) % mr
    tris += [(('i', k), ('i', k1), ('o', k)), (('i', k1), ('o', k1), ('o', k))]
edges = sorted({tuple(sorted((vid[t[a]], vid[t[b]]))) for t in tris for a, b in ((0, 1), (1, 2), (0, 2))})
eid = {e: k for k, e in enumerate(edges)}
d0 = [[(1 if v == e[1] else -1 if v == e[0] else 0) for v in range(len(Vn))] for e in edges]
d1m = []
for t in tris:
    a, b, c3 = (vid[v] for v in t)
    rowt = [0] * len(edges)
    for (p, q) in ((a, b), (b, c3), (c3, a)):
        rowt[eid[tuple(sorted((p, q)))]] += 1 if p < q else -1
    d1m.append(rowt)
dd0 = all(sum(d1m[t][e] * d0[e][v] for e in range(len(edges))) == 0 for t in range(len(tris)) for v in range(len(Vn)))
rk0, rk1 = rank_exact(d0), rank_exact(d1m)
betti = (len(Vn) - rk0, len(edges) - rk0 - rk1, len(tris) - rk1)
check('N9 a discrete de Rham complex: on a triangulated annulus d d = 0 and the Betti numbers are (1, 1, 0); the one harmonic 1-cochain is the'
      ' discrete counterpart of the class of d theta', dd0 and betti == (1, 1, 0), 'cells %d, %d, %d' % (len(Vn), len(edges), len(tris)))
rich = lambda s, th: max(abs(-2 * s * (1 - math.cos(th)) + sg * math.sqrt((2 * s * (1 - math.cos(th))) ** 2 + 1)) for sg in (1, -1))
check('N10 consistency is not enough (Lax): the centred three-level scheme for the heat equation is second-order accurate and has an amplification'
      ' factor larger than one for every s > 0', all(rich(s, th) > 1 for s in (0.001, 0.1, 0.5) for th in (0.3, PI)), 'at s = 0.1, k dx = pi: %.4f' % rich(0.1, PI))

sec('13. Fields')


def torus_complex(n):
    V = [(i, j, k) for i in range(n) for j in range(n) for k in range(n)]
    vi = {v: a for a, v in enumerate(V)}
    sh = lambda v, d: tuple((v[q] + (1 if q == d else 0)) % n for q in range(3))
    E = [(v, d) for v in V for d in range(3)]
    ei = {e: a for a, e in enumerate(E)}
    Fc = [(v, d) for v in V for d in range(3)]                   # face at v normal to direction d
    fi = {f_: a for a, f_ in enumerate(Fc)}
    d0_ = [[0] * len(V) for _ in E]
    for (v, d), a in ei.items():
        d0_[a][vi[sh(v, d)]] += 1
        d0_[a][vi[v]] -= 1
    d1_ = [[0] * len(E) for _ in Fc]
    for (v, d), a in fi.items():
        p, q = (d + 1) % 3, (d + 2) % 3
        d1_[a][ei[(v, p)]] += 1
        d1_[a][ei[(sh(v, p), q)]] += 1
        d1_[a][ei[(sh(v, q), p)]] -= 1
        d1_[a][ei[(v, q)]] -= 1
    d2_ = [[0] * len(Fc) for _ in V]
    for v, a in vi.items():
        for d in range(3):
            d2_[a][fi[(sh(v, d), d)]] += 1
            d2_[a][fi[(v, d)]] -= 1
    return d0_, d1_, d2_


def zero_prod(A, B):
    Bt = list(zip(*B))
    return all(sum(a * b for a, b in zip(r, c_)) == 0 for r in A for c_ in Bt)


e0, e1, e2 = torus_complex(3)
t0, t1, t2 = torus_complex(2)
rk = (rank_exact(t0), rank_exact(t1), rank_exact(t2))
bt = (8 - rk[0], 24 - rk[0] - rk[1], 24 - rk[1] - rk[2], 8 - rk[2])
Apot = [random.randint(-3, 3) for _ in range(81)]
chi = [random.randint(-3, 3) for _ in range(27)]
F1 = [sum(a * b for a, b in zip(r, Apot)) for r in e1]
F2 = [sum(a * b for a, b in zip(r, [x + sum(p * q for p, q in zip(rr, chi)) for x, rr in zip(Apot, e0)])) for r in e1]
check('P1 on a cubical 3-torus curl grad = 0 and div curl = 0 exactly; the field strength dA is unchanged by a gauge transformation;'
      ' the Betti numbers are (1, 3, 3, 1), so there are closed potentials that are not gradients', zero_prod(e1, e0) and zero_prod(e2, e1) and F1 == F2 and bt == (1, 3, 3, 1))
cl = 2.0
fw = lambda s: math.exp(-s * s) * math.sin(2 * s)
Ey = lambda x, t: fw(x - cl * t)
Bz = lambda x, t: fw(x - cl * t)
mres = max(abs(d1(lambda t: Ey(0.3, t), 0.2) - cl * (-d1(lambda x: Bz(x, 0.2), 0.3))), abs(d1(lambda t: Bz(0.3, t), 0.2) + cl * d1(lambda x: Ey(x, 0.2), 0.3)))
check('P2 Maxwell\'s equations in the source\'s form: the transverse plane wave E = (0, f(x - ct), 0), B = (0, 0, f(x - ct)) solves them', mres < 1e-8)
gam, rho0 = 1.4, 1.2
cs = math.sqrt(gam * rho0 ** (gam - 1))
trA, detA = 0.0, -(gam * rho0 ** (gam - 1))
eigs = sorted([(trA - math.sqrt(trA * trA - 4 * detA)) / 2, (trA + math.sqrt(trA * trA - 4 * detA)) / 2])
check('P3 acoustics is the tangent of fluid dynamics: the linearization of the one-dimensional Euler equations at rest has characteristic speeds'
      ' plus and minus the sound speed', abs(eigs[0] + cs) < 1e-12 and abs(eigs[1] - cs) < 1e-12, 'sound speed %.5f' % cs)
c1, c2 = 1.0, 3.0
Rr, Tt = (c2 - c1) / (c2 + c1), 2 * c2 / (c2 + c1)
fin = lambda s: math.exp(-(s + 4) ** 2)
uL = lambda x, t: fin(x - c1 * t) + Rr * fin(-x - c1 * t)
uR = lambda x, t: Tt * fin((c1 / c2) * (x - c2 * t))
jump = max(abs(uL(0.0, t) - uR(0.0, t)) + abs(d1(lambda x: uL(x, t), 0.0) - d1(lambda x: uR(x, t), 0.0)) for t in (3.0, 4.0, 4.6))
check('P4 scattering on a string of two materials: reflection (c2-c1)/(c2+c1), transmission 2c2/(c2+c1); the solution and its slope are continuous,'
      ' and the energy flux balances', jump < 1e-9 and abs(Rr ** 2 + (c1 / c2) * Tt ** 2 - 1) < 1e-15)


def prop(k, V, w):
    """transfer matrix of -psi'' + V psi = k^2 psi across a segment of constant potential, in the basis (psi, psi')"""
    q2 = k * k - V
    if abs(q2) < 1e-14:
        return [[1.0, w], [0.0, 1.0]]
    q = cmath.sqrt(q2)
    return [[cmath.cos(q * w), cmath.sin(q * w) / q], [-q * cmath.sin(q * w), cmath.cos(q * w)]]


def mm2(A, B):
    return [[A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]], [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]]


def RT(Pm, k):
    # P (1 + R, ik(1 - R)) = (T, ikT)
    a = [[Pm[0][0] - 1j * k * Pm[0][1], -1.0], [Pm[1][0] - 1j * k * Pm[1][1], -1j * k]]
    b = [-(Pm[0][0] + 1j * k * Pm[0][1]), -(Pm[1][0] + 1j * k * Pm[1][1])]
    det_ = a[0][0] * a[1][1] - a[0][1] * a[1][0]
    return (b[0] * a[1][1] - a[0][1] * b[1]) / det_, (a[0][0] * b[1] - b[0] * a[1][0]) / det_


segs = [(2.0, 0.7), (0.0, 0.5), (-1.5, 0.9), (3.0, 0.4)]
oku, okd, okf = True, True, True
for k in (0.6, 1.3, 2.4):
    Pm = [[1.0, 0.0], [0.0, 1.0]]
    for V, w in segs:
        Pm = mm2(prop(k, V, w), Pm)
    R_, T_ = RT(Pm, k)
    oku = oku and abs(abs(R_) ** 2 + abs(T_) ** 2 - 1) < 1e-12
    okd = okd and abs(Pm[0][0] * Pm[1][1] - Pm[0][1] * Pm[1][0] - 1) < 1e-12
    # the same matrix by integrating the equation across the whole potential
    cols = []
    for y0 in ([1.0, 0.0], [0.0, 1.0]):
        y, x = list(y0), 0.0
        for V, w in segs:
            hstep = w / 400
            for _ in range(400):
                y = rk4(lambda yy, V=V: [yy[1], (V - k * k) * yy[0]], y, hstep)
        cols.append(y)
    okf = okf and max(abs(cols[j][i] - Pm[i][j]) for i in range(2) for j in range(2)) < 1e-8
check('P5 scattering by a potential: transfer matrices compose under concatenation (a functor to SL(2)), and the resulting reflection and transmission'
      ' coefficients satisfy |R|^2 + |T|^2 = 1, the source\'s theorem', oku and okd and okf)
mK, kK = 0.8, 1.7
wK = math.sqrt(cl * cl * kK * kK + mK * mK)
ukg = lambda x, t: math.cos(kK * x - wK * t)
check('P6 the Klein-Gordon equation: plane waves with omega^2 = c^2 k^2 + m^2; the group velocity is below c, the phase velocity above, and their product is c^2',
      abs(d2(lambda t: ukg(0.3, t), 0.4) - cl * cl * d2(lambda x: ukg(x, 0.4), 0.3) + mK * mK * ukg(0.3, 0.4)) < 1e-6 and cl * cl * kK / wK < cl < wK / kK)
sig = [[[0, 1], [1, 0]], [[0, -1j], [1j, 0]], [[1, 0], [0, -1]]]
g0 = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, -1, 0], [0, 0, 0, -1]]
gs = [g0] + [[[0, 0, s_[0][0], s_[0][1]], [0, 0, s_[1][0], s_[1][1]], [-s_[0][0], -s_[0][1], 0, 0], [-s_[1][0], -s_[1][1], 0, 0]] for s_ in sig]
cm = lambda A, B: [[sum(A[i][k] * B[k][j] for k in range(4)) for j in range(4)] for i in range(4)]
eta = [1, -1, -1, -1]
okc = all(all(abs(cm(gs[a], gs[b])[i][j] + cm(gs[b], gs[a])[i][j] - (2 * eta[a] if a == b and i == j else 0)) < 1e-15 for i in range(4) for j in range(4)) for a in range(4) for b in range(4))
pvec = [0.7, -0.3, 1.1, 0.4]
slash = [[sum(pvec[a] * gs[a][i][j] for a in range(4)) for j in range(4)] for i in range(4)]
sq_ = cm(slash, slash)
m2 = pvec[0] ** 2 - sum(v * v for v in pvec[1:])
check('P7 the Dirac matrices of the source satisfy the Clifford relations, so the Dirac operator squares to the Klein-Gordon operator',
      okc and all(abs(sq_[i][j] - (m2 if i == j else 0)) < 1e-14 for i in range(4) for j in range(4)))
Lk = [[lap1(6)[i][j] + (0.5 if i == j else 0.0) for j in range(6)] for i in range(6)]
dt = 0.3
I6 = eye(6)
half = [[I6[i][j] - 0.5 * dt * dt * Lk[i][j] for j in range(6)] for i in range(6)]
# velocity Verlet: u' = (I - dt^2 L/2) u + dt v ; v' = v - dt/2 (L u + L u')
Muu, Muv = half, [[dt * I6[i][j] for j in range(6)] for i in range(6)]
LM = mm(Lk, Muu)
Mvu = [[-0.5 * dt * (Lk[i][j] + LM[i][j]) for j in range(6)] for i in range(6)]
LMv = mm(Lk, Muv)
Mvv = [[I6[i][j] - 0.5 * dt * LMv[i][j] for j in range(6)] for i in range(6)]
Mfull = [Muu[i] + Muv[i] for i in range(6)] + [Mvu[i] + Mvv[i] for i in range(6)]
Jm = [[(1.0 if j == i + 6 else -1.0 if j == i - 6 else 0.0) for j in range(12)] for i in range(12)]
sympl = mm(tr(Mfull), mm(Jm, Mfull))
Eu = [I6[i] + Muv[i] for i in range(6)] + [[-dt * Lk[i][j] for j in range(6)] + I6[i] for i in range(6)]
sympE = mm(tr(Eu), mm(Jm, Eu))
check('P8 the solution space of a wave equation is symplectic and a good scheme keeps it so: the leapfrog step satisfies M^T J M = J; the Euler'
      ' step does not', max(abs(sympl[i][j] - Jm[i][j]) for i in range(12) for j in range(12)) < 1e-12 and max(abs(sympE[i][j] - Jm[i][j]) for i in range(12) for j in range(12)) > 1e-2)

sec('14. Nonlinear equations')
tb = math.sqrt(math.e / 2)
mono = lambda t: min(1 + t * (-2 * z * math.exp(-z * z)) for z in [i * 0.001 for i in range(-4000, 4001)])
check('X1 characteristics of u_t + u u_x = 0 first cross at t = -1/min phi\'; for phi = exp(-x^2) this is sqrt(e/2)', mono(tb - 1e-3) > 0 > mono(tb + 1e-3), 'breaking time %.5f' % tb)
ust = lambda x, t: (1 + 2 * t * x - math.sqrt(1 + 4 * t * x)) / (2 * t * t)
check('X2 the source\'s example with phi = x^2: u = (1 + 2tx - sqrt(1 + 4tx))/(2t^2) solves the equation and tends to x^2 as t -> 0',
      max(abs(d1(lambda t: ust(x, t), t) + ust(x, t) * d1(lambda xx: ust(xx, t), x)) for x, t in [(0.5, 0.3), (2.0, 1.0)]) < 1e-8 and abs(ust(0.7, 1e-3) - 0.49) < 2e-3)


def burgers(u0, conservative, T, dxx, lam=0.5):
    u_ = list(u0)
    for _ in range(round(T / (lam * dxx))):
        if conservative:
            Fl = [0.5 * v * v for v in u_]
            u_ = [u_[0]] + [u_[j] - lam * (Fl[j] - Fl[j - 1]) for j in range(1, len(u_))]
        else:
            u_ = [u_[0]] + [u_[j] - lam * u_[j] * (u_[j] - u_[j - 1]) for j in range(1, len(u_))]
    return u_


dxx = 0.01
xs_ = [-1 + dxx * (j + 0.5) for j in range(400)]
shock0 = [1.0 if x < 0 else 0.0 for x in xs_]
front = lambda u_: next(xs_[j] for j in range(len(u_)) if u_[j] < 0.5)
fc, fn = front(burgers(shock0, True, 2.0, dxx)), front(burgers(shock0, False, 2.0, dxx))
rare = burgers([0.0 if x < 0 else 1.0 for x in xs_], True, 2.0, dxx)
mid = rare[min(range(400), key=lambda j: abs(xs_[j] - 1.0))]
check('X3 weak solutions are fixed by the conservation form: for the step from 1 to 0 a conservative scheme moves the shock at the Rankine-Hugoniot'
      ' speed 1/2, a non-conservative one leaves it where it was; the step from 0 to 1 opens into the fan x/t',
      abs(fc - 1.0) < 0.02 and abs(fn) < 0.02 and abs(mid - 0.5) < 0.05, 'front after time 2: conservative %.3f, non-conservative %.3f; fan value at x = t/2: %.3f' % (fc, fn, mid))
eps = 0.05
terms_ = [(0.6, 1.3), (-0.4, 0.7), (1.5, 0.2)]
ph_ = lambda x, t: sum(w * math.exp(a * x + eps * a * a * t) for a, w in terms_)
uch = lambda x, t: -2 * eps * d1(lambda xx: ph_(xx, t), x) / ph_(x, t)
uch2 = lambda x, t: -2 * eps * sum(w * a * math.exp(a * x + eps * a * a * t) for a, w in terms_) / ph_(x, t)
rb_ = max(abs(d1(lambda t: uch2(x, t), t) + uch2(x, t) * d1(lambda xx: uch2(xx, t), x) - eps * d2(lambda xx: uch2(xx, t), x)) for x, t in [(0.2, 0.3), (-1.0, 1.0)])
prof = lambda x, t, e: 1 / (1 + math.exp((x - t / 2) / (2 * e)))
check('X4 Cole-Hopf is a morphism of equations: u = -2 eps phi_x/phi carries solutions of the heat equation to solutions of the viscous Burgers'
      ' equation; the viscous profile from 1 to 0 travels at speed 1/2 and steepens to the shock as eps -> 0', rb_ < 1e-7 and prof(0.9, 2.0, 0.01) > 0.99 and prof(1.1, 2.0, 0.01) < 0.01, 'residual %.1e' % rb_)
cK = 1.7
sol1 = lambda x, t: 0.5 * cK / math.cosh(0.5 * math.sqrt(cK) * (x - cK * t)) ** 2
rk_ = max(abs(d1(lambda t: sol1(x, t), t) + d3(lambda xx: sol1(xx, t), x) + 6 * sol1(x, t) * d1(lambda xx: sol1(xx, t), x)) for x, t in [(0.3, 0.2), (2.0, 1.0), (-1.0, 0.0)])
check('X5 the soliton of the source solves the Korteweg-de Vries equation; its mass is 2 sqrt c and its momentum (2/3) c^{3/2}', rk_ < 1e-6
      and abs(simpson(lambda x: sol1(x, 0.0), -40, 40, 8000) - 2 * math.sqrt(cK)) < 1e-9 and abs(simpson(lambda x: sol1(x, 0.0) ** 2, -40, 40, 8000) - 2 / 3 * cK ** 1.5) < 1e-9, 'residual %.1e' % rk_)
k1, k2 = 1.6, 1.0
Ak = ((k1 - k2) / (k1 + k2)) ** 2


def two(x, t):
    e1_, e2_ = math.exp(k1 * x - k1 ** 3 * t), math.exp(k2 * x - k2 ** 3 * t)
    F = 1 + e1_ + e2_ + Ak * e1_ * e2_
    Fx = k1 * e1_ + k2 * e2_ + Ak * (k1 + k2) * e1_ * e2_
    Fxx = k1 * k1 * e1_ + k2 * k2 * e2_ + Ak * (k1 + k2) ** 2 * e1_ * e2_
    return 2 * (F * Fxx - Fx * Fx) / (F * F)


r2s = max(abs(d1(lambda t: two(x, t), t) + d3(lambda xx: two(xx, t), x) + 6 * two(x, t) * d1(lambda xx: two(xx, t), x)) for x, t in [(0.3, 0.2), (2.0, 1.0), (-1.0, -0.7), (0.0, 0.0)])
masses = [simpson(lambda x: two(x, t), -80, 120, 20000) for t in (-6.0, 0.0, 6.0)]


def peak(t, guess):
    a, b = guess - 1.5, guess + 1.5
    for _ in range(80):
        m1, m2_ = a + (b - a) * 0.382, a + (b - a) * 0.618
        if two(m1, t) < two(m2_, t):
            a = m1
        else:
            b = m2_
    return 0.5 * (a + b)


Tl = 12.0
shift1 = (peak(Tl, k1 * k1 * Tl - math.log(Ak) / k1) - k1 * k1 * Tl) - (peak(-Tl, -k1 * k1 * Tl) + k1 * k1 * Tl)
shift2 = (peak(Tl, k2 * k2 * Tl) - k2 * k2 * Tl) - (peak(-Tl, -k2 * k2 * Tl - math.log(Ak) / k2) + k2 * k2 * Tl)
check('X6 two solitons: the exact solution solves the equation, conserves mass 2(k1 + k2), and after the collision the fast soliton is ahead by'
      ' (2/k1) log((k1+k2)/(k1-k2)) and the slow one behind by (2/k2) log((k1+k2)/(k1-k2))', r2s < 1e-5 and max(abs(m_ - 2 * (k1 + k2)) for m_ in masses) < 1e-8
      and abs(shift1 + math.log(Ak) / k1) < 1e-5 and abs(shift2 - math.log(Ak) / k2) < 1e-5, 'residual %.1e; shifts %.5f, %.5f' % (r2s, shift1, shift2))
hq = 0.025
xq = [-30 + hq * (i + 1) for i in range(2799)]
spec = [tri_eigs([2 / hq ** 2 - two(x, t) for x in xq], [-1 / hq ** 2] * 2798, 2) for t in (0.0, 1.5)]
check('X7 the flow is isospectral: the operator -d^2/dx^2 - u(., t) with the two-soliton potential has the eigenvalues -k1^2/4 and -k2^2/4 at'
      ' every time', all(abs(sp[0] + k1 * k1 / 4) < 1e-3 and abs(sp[1] + k2 * k2 / 4) < 1e-3 for sp in spec), 'at t = 0: %.5f, %.5f; at t = 1.5: %.5f, %.5f' % (*spec[0], *spec[1]))
cat = lambda x: 1.3 * math.cosh((x - 0.2) / 1.3)
check('X8 calculus of variations: the catenary satisfies the Euler-Lagrange equation u u\'\' = 1 + u\'^2 of the area functional, and u/sqrt(1+u\'^2) is constant',
      all(abs(cat(x) * d2(cat, x) - 1 - d1(cat, x) ** 2) < 1e-6 and abs(cat(x) / math.sqrt(1 + d1(cat, x) ** 2) - 1.3) < 1e-9 for x in (-0.8, 0.1, 1.4)))


def ellK(m):
    a, b = 1.0, math.sqrt(1 - m * m)
    for _ in range(40):
        a, b = 0.5 * (a + b), math.sqrt(a * b)
    return PI / (2 * a)


lb = 2.0
okb, lams = True, []
for Amp in (0.2, 1.0, 2.0):
    lam = (2 * ellK(math.sin(Amp / 2)) / lb) ** 2
    y = [Amp, 0.0]
    for _ in range(4000):
        y = rk4(lambda yy: [yy[1], -lam * math.sin(yy[0])], y, lb / 4000)
    okb = okb and abs(y[1]) < 1e-8 and abs(y[0] + Amp) < 1e-8
    lams.append(lam / (PI / lb) ** 2)
check('X9 buckling, u\'\' + lambda sin u = 0 with u\' = 0 at both ends: the first branch leaves the trivial solution at lambda = pi^2/l^2 and bends'
      ' to the right, with lambda/lambda_1 = (2K(sin(A/2))/pi)^2 = 1 + A^2/8 + ...', okb and lams[0] < lams[1] < lams[2] and abs(lams[0] - 1 - 0.2 ** 2 / 8) < 1e-4,
      'lambda/lambda_1 at amplitude 0.2, 1, 2: %.5f, %.5f, %.5f' % tuple(lams))
gg, hh = 9.81, 3.0


def ww(kk):
    om_ = math.sqrt(gg * kk * math.tanh(kk * hh))
    pot = lambda x, z, t: math.cosh(kk * (z + hh)) * math.sin(kk * x - om_ * t)
    harm = d2(lambda x: pot(x, -0.7, 0.3), 0.4) + d2(lambda z: pot(0.4, z, 0.3), -0.7)
    surf = d2(lambda t: pot(0.4, 0.0, t), 0.3) + gg * d1(lambda z: pot(0.4, z, 0.3), 0.0)
    bott = d1(lambda z: pot(0.4, z, 0.3), -hh)
    return max(abs(harm), abs(surf), abs(bott)) / math.cosh(kk * hh), om_ / kk


r1_, cmid = ww(0.9)
cshal, cdeep = math.sqrt(gg * math.tanh(0.003 * hh) / 0.003), math.sqrt(gg * math.tanh(20.0 * hh) / 20.0)
check('X10 linear water waves: the potential cosh(k(z+h)) sin(kx - omega t) is harmonic, has no flow through the bottom, and satisfies the surface'
      ' condition exactly when omega^2 = g k tanh(kh); the speed is sqrt(gh) in shallow water and sqrt(g/k) in deep water',
      r1_ < 1e-5 and abs(cshal - math.sqrt(gg * hh)) < 1e-3 and abs(cdeep - math.sqrt(gg / 20.0)) < 1e-12)

footer()
