"""The figures of the note S2, from the data written by figdata (pandsysroots 0.18.0) and from the result files of the comparison. python figures.py""" import itertools, math, os, re import numpy as np import matplotlib matplotlib.use("Agg") import matplotlib.pyplot as plt from matplotlib.colors import ListedColormap, hsv_to_rgb from matplotlib.patches import Polygon from matplotlib.lines import Line2D HERE = os.path.dirname(os.path.abspath(__file__)) DATA = os.path.join(HERE, "data") OUT = os.path.join(HERE, "..", "paper") VERSUS = os.path.expanduser("~/pandroots-work/versus-hc") INK = "#1b2333" BLUE = "#27458f" ORANGE = "#e2793a" TEAL = "#1f9e8f" RED = "#c22f3d" GOLD = "#e0a72e" GREY = "#9aa3b2" PALE = "#eef1f6" plt.rcParams.update({ "font.family": "cmr10", "axes.formatter.use_mathtext": True, "axes.unicode_minus": False, "mathtext.fontset": "cm", "font.size": 8.5, "axes.titlesize": 9, "axes.labelsize": 8.5, "axes.edgecolor": INK, "axes.labelcolor": INK, "text.color": INK, "xtick.color": INK, "ytick.color": INK, "axes.linewidth": 0.6, "xtick.major.width": 0.5, "ytick.major.width": 0.5, "xtick.labelsize": 7.5, "ytick.labelsize": 7.5, "legend.fontsize": 7.5, "legend.frameon": False, "savefig.bbox": "tight", "savefig.pad_inches": 0.03, "pdf.fonttype": 42, }) def clean(ax, grid=None): for s in ("top", "right"): ax.spines[s].set_visible(False) if grid: ax.grid(axis=grid, color="#d9dee8", lw=0.5, zorder=0) ax.set_axisbelow(True) def read(name): with open(os.path.join(DATA, name)) as f: return [l.split() for l in f.read().strip().split("\n")] # ------------------------------------------------------------------ gallery def gallery(): items = [("gallery_cyclic7.txt", "cyclic-7", "924 solutions"), ("gallery_noon6.txt", "noon-6", "717 solutions"), ("gallery_katsura10.txt", "Katsura-10", "1024 solutions"), ("gallery_dense2x30.txt", "degree 30, two unknowns", "900 solutions")] fig, axes = plt.subplots(1, 4, figsize=(7.2, 1.95)) for ax, (file, name, count) in zip(axes, items): rows = np.array(read(file), dtype=float) real = rows[:, 0] > 0 z = rows[:, 1] + 1j * rows[:, 2] w = rows[:, 3] + 1j * rows[:, 4] # colour: the argument of the second coordinate; size: fixed hue = (np.angle(w) / (2 * np.pi)) % 1.0 col = hsv_to_rgb(np.stack([hue, 0.78 * np.ones_like(hue), 0.80 * np.ones_like(hue)], axis=1)) lim = np.percentile(np.abs(z), 99.5) * 1.12 ax.scatter(z.real, z.imag, s=3.2, c=col, lw=0, alpha=0.9, zorder=3) ax.scatter(z.real[real], z.imag[real], s=5, facecolors="none", edgecolors=INK, lw=0.3, alpha=0.7, zorder=4) ax.axhline(0, color="#c9cfdb", lw=0.4, zorder=1) ax.axvline(0, color="#c9cfdb", lw=0.4, zorder=1) ax.set_xlim(-lim, lim); ax.set_ylim(-lim, lim); ax.set_aspect("equal") ax.set_xticks([]); ax.set_yticks([]) for s in ax.spines.values(): s.set_color("#c9cfdb"); s.set_linewidth(0.5) ax.set_title(name, pad=3) ax.text(0.5, -0.07, count, transform=ax.transAxes, ha="center", va="top", fontsize=7.5, color="#59647a") fig.subplots_adjust(wspace=0.06) fig.savefig(os.path.join(OUT, "fig_gallery.pdf")) plt.close(fig) # ------------------------------------------------------------------ sweeps def sweeps(): rows = read("sweeps.txt") seed, m, n, steps, r = int(rows[0][0]), int(rows[0][1]), int(rows[0][2]), int(rows[0][3]), float(rows[0][4]) hist = np.array(rows[1:1 + steps], dtype=float).reshape(steps, m, n, 2) z = hist[..., 0] + 1j * hist[..., 1] sizes = np.array(rows[1 + steps:], dtype=float) cols = plt.cm.turbo(np.linspace(0.06, 0.94, m)) fig, axes = plt.subplots(1, 3, figsize=(7.2, 2.45), gridspec_kw={"width_ratios": [1, 1, 1.12]}) for c in range(2): ax = axes[c] th = np.linspace(0, 2 * np.pi, 400) ax.plot(r * np.cos(th), r * np.sin(th), color="#cfd5e0", lw=0.6, ls=(0, (3, 2)), zorder=1) for k in range(m): path = z[:, k, c] ax.plot(path.real, path.imag, color=cols[k], lw=0.9, alpha=0.85, zorder=2) ax.scatter(path.real[1:-1], path.imag[1:-1], s=4, color=cols[k], lw=0, zorder=3) ax.scatter([path.real[0]], [path.imag[0]], s=22, facecolors="white", edgecolors=cols[k], lw=0.9, zorder=4) ax.scatter([path.real[-1]], [path.imag[-1]], s=20, color=cols[k], edgecolors=INK, lw=0.5, zorder=5) lim = max(np.abs(z[:, :, c]).max(), r) * 1.1 ax.set_xlim(-lim, lim); ax.set_ylim(-lim, lim); ax.set_aspect("equal") ax.set_title(f"coordinate $x_{c + 1}$", pad=3) ax.set_xlabel("real part") if c == 0: ax.set_ylabel("imaginary part") clean(ax) ax = axes[2] for k in range(m): ax.semilogy(np.arange(1, len(sizes) + 1), np.maximum(sizes[:, k], 1e-17), color=cols[k], lw=1.0, marker="o", ms=2.3) ax.set_xlabel("sweep"); ax.set_title("size of the Newton displacement", pad=3) ax.set_xticks(range(2, len(sizes) + 1, 2)) ax.set_ylim(1e-17, 10) clean(ax, "y") fig.subplots_adjust(wspace=0.3) fig.savefig(os.path.join(OUT, "fig_sweeps.pdf")) plt.close(fig) return steps - 1 # ------------------------------------------------------------------ basins def basins(): roots = np.array(read("basins_roots.txt"), dtype=float) # one hue per solution, placed by its position so that neighbours contrast order = np.lexsort((roots[:, 0], roots[:, 2])) hues = np.zeros(len(roots)) base = [0.60, 0.08, 0.36, 0.95, 0.50, 0.16, 0.76, 0.27, 0.02] for rank, k in enumerate(order): hues[k] = base[rank % len(base)] fig, axes = plt.subplots(1, 2, figsize=(7.2, 3.62)) stats = {} for ax, (file, title) in zip(axes, [("basins_three.txt", "the rectangle step with the three means"), ("basins_newton.txt", "the support $AK$ alone (Newton's iteration)")]): rows = read(file) size, half = int(rows[0][0]), float(rows[0][1]) a = np.array(rows[1:], dtype=int).reshape(size, size, 2) k, it = a[..., 0], a[..., 1] img = np.ones((size, size, 3)) ok = k >= 0 val = np.clip(1.0 - 0.055 * (it - 2), 0.30, 1.0) hsv = np.stack([hues[np.maximum(k, 0)], 0.62 * np.ones_like(val), val], axis=-1) img[ok] = hsv_to_rgb(hsv)[ok] img[~ok] = (0.07, 0.08, 0.11) ax.imshow(img, extent=(-half, half, -half, half), interpolation="lanczos") ax.scatter(roots[:, 0], roots[:, 2], s=13, facecolors="white", edgecolors=INK, lw=0.6, zorder=3) ax.set_title(title, pad=4) ax.set_xlabel("$x$") ax.set_xticks([-2, -1, 0, 1, 2]); ax.set_yticks([-2, -1, 0, 1, 2]) stats[file] = ((~ok).sum(), size * size, it[ok].mean()) axes[0].set_ylabel("$y$") fig.subplots_adjust(wspace=0.12) fig.savefig(os.path.join(OUT, "fig_basins.png"), dpi=330) plt.close(fig) return stats # ------------------------------------------------------------------ mixed cells def cells(): A = [np.array([(0, 0), (3, 0), (0, 2), (2, 2), (1, 1)]), np.array([(0, 0), (2, 0), (0, 3), (1, 2), (2, 1)])] w = [np.array([0.0, 1.3, 0.9, 2.6, 0.2]), np.array([0.1, 0.7, 1.9, 0.5, 1.6])] def lowest(i, g): v = A[i] @ g + w[i] return v, v.min() cells_mixed, cells_other = [], [] eps = 1e-9 # mixed cells: one edge of each support, lowest for a common g for (p1, q1) in itertools.combinations(range(len(A[0])), 2): for (p2, q2) in itertools.combinations(range(len(A[1])), 2): M = np.array([A[0][p1] - A[0][q1], A[1][p2] - A[1][q2]], dtype=float) if abs(np.linalg.det(M)) < eps: continue g = np.linalg.solve(M, np.array([w[0][q1] - w[0][p1], w[1][q2] - w[1][p2]])) v1, m1 = lowest(0, g); v2, m2 = lowest(1, g) if sorted(np.where(v1 < m1 + eps)[0]) == [p1, q1] and sorted(np.where(v2 < m2 + eps)[0]) == [p2, q2]: a, b, c, d = A[0][p1], A[0][q1], A[1][p2], A[1][q2] cells_mixed.append(([a + c, b + c, b + d, a + d], abs(np.linalg.det(M)))) # the other cells: a triangle of one support and a point of the other for i in (0, 1): j = 1 - i for tri in itertools.combinations(range(len(A[i])), 3): P = A[i][list(tri)].astype(float) M = np.array([P[0] - P[1], P[0] - P[2]]) if abs(np.linalg.det(M)) < eps: continue g = np.linalg.solve(M, np.array([w[i][tri[1]] - w[i][tri[0]], w[i][tri[2]] - w[i][tri[0]]])) vi, mi = lowest(i, g); vj, mj = lowest(j, g) if sorted(np.where(vi < mi + eps)[0]) == sorted(tri) and (vj < mj + eps).sum() == 1: b = A[j][int(np.argmin(vj))] cells_other.append(([P[0] + b, P[1] + b, P[2] + b], i)) def hull(points): pts = sorted(set(map(tuple, points))) def half(ps): h = [] for p in ps: while len(h) >= 2 and (h[-1][0] - h[-2][0]) * (p[1] - h[-2][1]) - (h[-1][1] - h[-2][1]) * (p[0] - h[-2][0]) <= 0: h.pop() h.append(p) return h lo, up = half(pts), half(pts[::-1]) return np.array(lo[:-1] + up[:-1]) fig, axes = plt.subplots(1, 3, figsize=(7.2, 2.5), gridspec_kw={"width_ratios": [0.72, 0.72, 1.35]}) for ax, pts, name, col in [(axes[0], A[0], "$A_1$", BLUE), (axes[1], A[1], "$A_2$", ORANGE)]: h = hull(pts) ax.add_patch(Polygon(h, closed=True, facecolor=col, alpha=0.13, edgecolor=col, lw=1.0)) ax.scatter(pts[:, 0], pts[:, 1], s=16, color=col, zorder=3, edgecolors="white", lw=0.5) ax.set_xlim(-0.5, 3.5); ax.set_ylim(-0.5, 3.5); ax.set_aspect("equal") ax.set_xticks(range(4)); ax.set_yticks(range(4)) ax.set_title(f"support {name}", pad=3) clean(ax) ax = axes[2] for poly, i in cells_other: col = BLUE if i == 0 else ORANGE ax.add_patch(Polygon(poly, closed=True, facecolor=col, alpha=0.13, edgecolor="white", lw=1.2)) total = 0.0 for poly, vol in cells_mixed: ax.add_patch(Polygon(poly, closed=True, facecolor=TEAL, alpha=0.78, edgecolor="white", lw=1.2)) c = np.mean(poly, axis=0) ax.text(c[0], c[1], f"{vol:.0f}", ha="center", va="center", color="white", fontsize=8.5, fontweight="bold") total += vol S = hull([a + b for a in A[0] for b in A[1]]) ax.add_patch(Polygon(S, closed=True, facecolor="none", edgecolor=INK, lw=0.9)) sums = np.array([a + b for a in A[0] for b in A[1]]) ax.scatter(sums[:, 0], sums[:, 1], s=5, color=INK, zorder=4, lw=0) ax.set_xlim(-0.5, 5.5); ax.set_ylim(-0.5, 5.5); ax.set_aspect("equal") ax.set_xticks(range(6)); ax.set_yticks(range(6)) ax.set_title(f"the sum $A_1+A_2$ cut by a lifting: mixed volume ${total:.0f}$", pad=3) clean(ax) fig.subplots_adjust(wspace=0.28) fig.savefig(os.path.join(OUT, "fig_cells.pdf")) plt.close(fig) # the mixed volume by areas, as a check: area(P1 + P2) - area(P1) - area(P2) def area(h): return 0.5 * abs(sum(h[i][0] * h[(i + 1) % len(h)][1] - h[(i + 1) % len(h)][0] * h[i][1] for i in range(len(h)))) check = area(S) - area(hull(A[0])) - area(hull(A[1])) assert abs(check - total) < 1e-9, (check, total) return total, len(cells_mixed), len(cells_other) # ------------------------------------------------------------------ residues def residues(): known = np.array(read("residues_known.txt"), dtype=float) missing = np.array(read("residues_missing.txt"), dtype=float) cand = np.array(read("residues_candidates.txt"), dtype=float) fig, axes = plt.subplots(1, 2, figsize=(7.2, 2.75), gridspec_kw={"width_ratios": [1.25, 1]}) ax = axes[0] ax.scatter(known[:, 0], known[:, 1], s=9, color=GREY, lw=0, label=f"found by the sweeps ({len(known)})", zorder=2) ax.scatter(missing[:, 0], missing[:, 1], s=62, facecolors="none", edgecolors=RED, lw=1.1, label=f"missing ({len(missing)})", zorder=3) ax.scatter(cand[:, 0], cand[:, 1], s=30, marker="+", color=INK, lw=1.0, label="computed from the others", zorder=4) lim = np.abs(np.concatenate([known[:, :2], missing[:, :2]])).max() * 1.12 ax.set_xlim(-lim, lim); ax.set_ylim(-lim, lim); ax.set_aspect("equal") ax.set_xlabel("real part of $x_1$"); ax.set_ylabel("imaginary part of $x_1$") ax.legend(loc="upper left", bbox_to_anchor=(1.02, 1.0), handletextpad=0.3) clean(ax) ax = axes[1] d = np.sort(cand[:, 4]) ax.barh(np.arange(len(d)), d, color=TEAL, height=0.62, zorder=3) ax.set_xscale("log") ax.set_yticks([]) ax.set_xlabel("distance from a candidate to its solution") ax.set_title("before any step", pad=3) clean(ax, "x") pos = axes[1].get_position() axes[1].set_position([pos.x0 + 0.06, pos.y0, pos.width - 0.06, pos.height * 0.62]) fig.savefig(os.path.join(OUT, "fig_residues.pdf")) plt.close(fig) return len(known), len(missing), d.min(), d.max() # ------------------------------------------------------------------ comparison def table(file): out = {} for l in open(os.path.join(VERSUS, file)): f = l.split() if len(f) >= 7 and f[-2] in ("true", "false"): out[f[0]] = (float(f[-1]), f[-2] == "true", int(f[-3])) return out def hc(): out = {} for file in ("hc.txt", "hc_more.txt"): for l in open(os.path.join(VERSUS, file)): f = l.split() if len(f) == 9 and f[0] != "system": out[f[0]] = float(f[7]) return out NAMES = [("cyclic-5", "cyclic-5"), ("cyclic-6", "cyclic-6"), ("cyclic-7", "cyclic-7"), ("noon-5", "noon-5"), ("noon-6", "noon-6"), ("noon-7", "noon-7"), ("noon-8", "noon-8"), ("sparse-4x4", "sparse, 4 unknowns"), ("katsura-10", "Katsura-10"), ("katsura-12", "Katsura-12"), ("dense-2x40", "2 unknowns, degree 40"), ("dense-3x16", "3 unknowns, degree 16"), ("cubics-8", "8 cubics"), ("quadrics-12", "12 quadrics"), ("bilinear-6+6", "bilinear 6 + 6"), ("bilinear-7+7", "bilinear 7 + 7"), ("eigen-32", "eigenvalues, order 32"), ("eigen-64", "eigenvalues, order 64")] def versus(): ours, other = table("pandsysroots_0.21.0.txt"), hc() fig, ax = plt.subplots(figsize=(7.2, 4.1)) y = np.arange(len(NAMES))[::-1] floor = 0.006 for (key, label), yy in zip(NAMES, y): a, b = max(ours[key][0], 0.01), max(other[key], 0.01) ax.plot([a, b], [yy, yy], color="#c9cfdb", lw=2.2, zorder=2, solid_capstyle="round") ax.scatter([b], [yy], s=42, color="white", edgecolors=ORANGE, lw=1.5, zorder=3) ax.scatter([a], [yy], s=42, color=BLUE, edgecolors="white", lw=0.6, zorder=4) ratio = b / a txt = f"{ratio:.1f}$\\times$ faster" if ratio >= 1.15 else (f"{1 / ratio:.1f}$\\times$ slower" if ratio <= 1 / 1.15 else "level") ax.text(max(a, b) * 1.35, yy, txt, va="center", ha="left", fontsize=7, color=BLUE if ratio >= 1.15 else (ORANGE if ratio <= 1 / 1.15 else "#59647a")) ax.set_yticks(y); ax.set_yticklabels([l for _, l in NAMES]) ax.set_xscale("log"); ax.set_xlim(floor, 150) ax.set_xticks([0.01, 0.1, 1, 10, 100]); ax.set_xticklabels(["0.01 s", "0.1 s", "1 s", "10 s", "100 s"]) ax.set_ylim(-0.7, len(NAMES) - 0.3) ax.tick_params(axis="y", length=0) clean(ax, "x"); ax.spines["left"].set_visible(False) ax.legend(handles=[Line2D([], [], marker="o", ls="", color=BLUE, ms=6.5, label="this method (pandsysroots 0.21.0), completeness proved"), Line2D([], [], marker="o", ls="", mfc="white", mec=ORANGE, mew=1.5, ms=6.5, label="HomotopyContinuation.jl 2.23, solve and certify")], loc="lower right", bbox_to_anchor=(1.0, 1.0), ncol=2, columnspacing=1.6, handletextpad=0.2) fig.savefig(os.path.join(OUT, "fig_versus.pdf")) plt.close(fig) return {k: (ours[k][0], other[k]) for k, _ in NAMES} def progress(): files = [("0.14", ["pandsysroots.txt", "pandsysroots_rest.txt"]), ("0.15", ["pandsysroots_0.15.0.txt"]), ("0.16", ["pandsysroots_0.16.0.txt"]), ("0.17", ["pandsysroots_0.17.0.txt"]), ("0.18", ["pandsysroots_0.18.0.txt"]), ("0.19", ["pandsysroots_0.19.0.txt"]), ("0.20", ["pandsysroots_0.20.0.txt"]), ("0.21", ["pandsysroots_0.21.0.txt"])] data = [] for v, fs in files: t = {} for f in fs: t.update(table(f)) data.append((v, t)) keys = [("cyclic-7", "cyclic-7", RED), ("noon-6", "noon-6", ORANGE), ("katsura-12", "Katsura-12", TEAL), ("dense-2x40", "2 unknowns, degree 40", BLUE), ("quadrics-12", "12 quadrics", GOLD), ("cubics-8", "8 cubics", "#7a4fa3"), ("dense-3x16", "3 unknowns, degree 16", "#59647a")] other = hc() fig, ax = plt.subplots(figsize=(7.2, 2.9)) x = np.arange(len(data)) ends = sorted(((data[-1][1][key][0], key) for key, _, _ in keys)) place, last = {}, 0.0 for v, key in ends: yv = max(v, last * 1.95) place[key], last = yv, yv for key, label, col in keys: ys = [d[1][key][0] if key in d[1] else np.nan for d in data] done = [d[1][key][1] if key in d[1] else True for d in data] ax.plot(x, ys, color=col, lw=1.4, zorder=2) for xi, yi, ok in zip(x, ys, done): ax.scatter([xi], [yi], s=26, color=col if ok else "white", edgecolors=col, lw=1.2, zorder=3) ax.plot([x[-1] + 0.05, x[-1] + 0.16], [ys[-1], place[key]], color=col, lw=0.5) ax.text(x[-1] + 0.19, place[key], label, color=col, va="center", fontsize=7.5) ax.plot([x[-1] + 2.5, x[-1] + 2.68], [other[key]] * 2, color=col, lw=1.6, solid_capstyle="butt") ax.text(x[-1] + 2.59, 60, "the other\nsolver", ha="center", va="bottom", fontsize=7, color="#59647a") ax.set_yscale("log"); ax.set_ylim(0.012, 700) ax.set_yticks([0.1, 1, 10, 100]); ax.set_yticklabels(["0.1 s", "1 s", "10 s", "100 s"]) ax.set_xticks(x); ax.set_xticklabels([d[0] for d in data]); ax.set_xlabel("version of the crate", loc="left") ax.set_xlim(-0.25, x[-1] + 2.95) clean(ax, "y") fig.savefig(os.path.join(OUT, "fig_progress.pdf")) plt.close(fig) if __name__ == "__main__": gallery() print("sweeps:", sweeps()) print("basins:", basins()) print("cells:", cells()) print("residues:", residues()) print("versus:", versus()) progress()