Graph diffusion and metric network pde numerics

The product is a Hilbert space: if a sequence is Cauchy in the finite sum-of-squares norm, each edge coordinate is Cauchy in its $H^1$ norm and converges by [F1]; the finitely many coordinate limits form an element of the product and the sum of the finitely many squared errors tends to zero. The product inner product is the sum of the edge inner products.

For each edge $e$, choose ${ϵ}_e={\mathrm{\ell }}_e\mathrm{/}2$, which satisfies the hypothesis of [F2]. For either endpoint, [F2] then gives $\max \{\mathrm{\mid }{w}_e(0){\mathrm{\mid }}^2,\mathrm{\mid }{w}_e({\mathrm{\ell }}_e){\mathrm{\mid }}^2\}\le \frac{4}{{\mathrm{\ell }}_e}\mathrm{\parallel }{w}_e{\mathrm{\parallel }}_{L^2(0,{\mathrm{\ell }}_e)}^2+{\mathrm{\ell }}_e\mathrm{\parallel }{w}_e^{\mathrm{\prime }}{\mathrm{\parallel }}_{L^2(0,{\mathrm{\ell }}_e)}^2\le C_e\mathrm{\parallel }{w}_e{\mathrm{\parallel }}_{H^1(0,{\mathrm{\ell }}_e)}^2,$ where $C_e:=\max \{4\mathrm{/}{\mathrm{\ell }}_e,{\mathrm{\ell }}_e\}<\mathrm{\infty }$. Thus each endpoint evaluation is a bounded linear functional on its edge $H^1$ space. For every vertex, the difference of two incident endpoint evaluations is therefore continuous; its kernel is closed. Each anchor endpoint evaluation is also continuous and its zero set is closed. There are finitely many vertices, incidences, and anchors, so the intersection of these kernels, namely the trace-matching space and then $V_D$, is closed in the product.

A Cauchy sequence in either constrained space converges in the product by step 1.1. Continuity of every endpoint functional from step 1.2 passes all matching equalities and zero anchor values to the limit, so the limit remains in the same constrained space. The restricted edge-product inner product is positive definite and complete there. Hence both constrained spaces are Hilbert.

If $E=\mathrm{\varnothing }$, then $H=\{0\}$ and the inequality is $0\le 0$. Otherwise fix an edge $e$ in a component containing an anchor. If $e$ is a loop, deleting its interior leaves the component connected because any path that traverses the loop can omit that closed excursion. If its endpoints are distinct, every original path that uses $e$ reaches one endpoint before traversing it; after deleting $e$, vertices are therefore connected to one of its two endpoints. Thus removing $e$ either leaves the component connected or separates it into two components, one containing each endpoint. In the connected case choose either endpoint; in the separated case choose the endpoint in the component containing an anchor. By [F3] there is a finite path from an anchor to that endpoint avoiding $e$. Deleting the portions between repeated vertices gives a simple path, so no edge is traversed twice. For a loop choose its tail incidence; otherwise use the incidence at the chosen endpoint. For any $x$ on $e$, append the segment from that incidence to $x$. The total length is at most $L_{\mathrm{\Gamma }}$, and the common vertex traces agree along the path by [F1]. Since $w=0$ at the anchor, [F1] and [F2] imply $\mathrm{\mid }{w}_e(x){\mathrm{\mid }}^2\le L_{\mathrm{\Gamma }}{\sum }_{a\text{ on the concatenated path}}{\int }_a\mathrm{\mid }{w}_a^{\mathrm{\prime }}{\mathrm{\mid }}^2\le L_{\mathrm{\Gamma }}{\sum }_{a\in E}\mathrm{\parallel }{w}_a^{\mathrm{\prime }}{\mathrm{\parallel }}_{L^2(a)}^2\mathrm{.}$

Integrate the pointwise bound of step 1.1 over every edge and sum. The total measure of the disjoint edge interiors is ${\sum }_e{\mathrm{\ell }}_e=L_{\mathrm{\Gamma }}$, so $\mathrm{\parallel }w{\mathrm{\parallel }}_{L^2(\mathrm{\Gamma })}^2\le L_{\mathrm{\Gamma }}^2{\sum }_{e\in E}\mathrm{\parallel }{w}_e^{\mathrm{\prime }}{\mathrm{\parallel }}_{L^2(e)}^2\mathrm{.}$ Taking nonnegative square roots proves the statement.

If $E=\mathrm{\varnothing }$, both sides are empty sums and the identity is $0=0$. Otherwise fix an edge $e$ and first suppose $u_e$ is real-valued. By [F1] and [F4], $u_e^{\mathrm{\prime }}$ and $v_e$ have absolutely continuous representatives on $[0,{\mathrm{\ell }}_e]$. They are bounded there. The product $u_e^{\mathrm{\prime }}{v}_e$ is absolutely continuous: for any disjoint intervals $[a_j,b_j]$, ${\sum }_j\mathrm{\mid }{u}_e^{\mathrm{\prime }}(b_j)v_e(b_j)-u_e^{\mathrm{\prime }}(a_j)v_e(a_j)\mathrm{\mid }\le \mathrm{\parallel }{u}_e^{\mathrm{\prime }}{\mathrm{\parallel }}_{\mathrm{\infty }}{\sum }_j\mathrm{\mid }{v}_e(b_j)-v_e(a_j)\mathrm{\mid }+\mathrm{\parallel }{v}_e{\mathrm{\parallel }}_{\mathrm{\infty }}{\sum }_j\mathrm{\mid }{u}_e^{\mathrm{\prime }}(b_j)-u_e^{\mathrm{\prime }}(a_j)\mathrm{\mid },$ so the defining absolute-continuity condition follows from that of the two factors. At almost every point both derivatives exist, and [F3] gives $(u_e^{\mathrm{\prime }}{v}_e{)}^{\mathrm{\prime }}=u_e^{\mathrm{\prime }\mathrm{\prime }}{v}_e+u_e^{\mathrm{\prime }}{v}_e^{\mathrm{\prime }}$. Both terms are integrable because $u_e^{\mathrm{\prime }\mathrm{\prime }},v_e^{\mathrm{\prime }}$ are integrable derivatives of absolutely continuous functions and $u_e^{\mathrm{\prime }},v_e$ are bounded. Applying [F2] to the product therefore yields ${\int }_0^{{\mathrm{\ell }}_e}{u}_e^{\mathrm{\prime }}{v}_e^{\mathrm{\prime }}d{x}_e=-{\int }_0^{{\mathrm{\ell }}_e}{u}_e^{\mathrm{\prime }\mathrm{\prime }}{v}_{e}d{x}_e+u_e^{\mathrm{\prime }}({\mathrm{\ell }}_e)v_e({\mathrm{\ell }}_e)-u_e^{\mathrm{\prime }}(0)v_e(0)\mathrm{.}$ If $u_e$ is complex-valued, write the absolutely continuous representative $u_e^{\mathrm{\prime }}=p+iq$. By [F1], $p,q$ are real absolutely continuous functions with derivatives $\mathrm{Re}{u}_e^{\mathrm{\prime }\mathrm{\prime }},\mathrm{Im}{u}_e^{\mathrm{\prime }\mathrm{\prime }}$ almost everywhere; these derivatives lie in $L^2$ since their absolute values are bounded by $\mathrm{\mid }{u}_e^{\mathrm{\prime }\mathrm{\prime }}\mathrm{\mid }$. The test function $v_e$ is real by definition of $V_D$. Apply the preceding product-rule and fundamental-theorem calculation separately to $p{v}_e$ and $q{v}_e$ and combine the two identities, using componentwise complex integration. This proves the same displayed identity for complex $u_e$. The endpoint terms are the head and tail outward derivatives paired with their traces.

Multiply the identity of step 1.1 by ${\kappa }_e$ and sum over the finite edge set. At each vertex, all endpoint-incidence values of $v$ equal the common trace $v(z)$ by definition of $V_D$; this includes both incidences of a loop. Regrouping the finite endpoint sum by vertices gives the displayed identity. If $z\in D$, then $v(z)=0$; if $z\mathrm{\notin }D$, the stated Kirchhoff sum is zero. Hence the boundary contribution vanishes under those conditions.

Reversing an edge orientation replaces its incidence column $b_e$ by $-b_e$, but the contribution $c_e{b}_e{b}_e^{\mathsf{T}}$ to $BC{B}^{\mathsf{T}}$ does not change. For the zero extension $\bar{x}$, [F1] gives $b_e^{\mathsf{T}}\bar{x}={\bar{x}}_{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}(e)}-{\bar{x}}_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}(e)}$. Expanding ${\bar{x}}^{\mathsf{T}}BC{B}^{\mathsf{T}}\bar{x}={\sum }_e{c}_e(b_e^{\mathsf{T}}\bar{x}{)}^2$ proves the displayed energy identity. It is nonnegative term by term, so $L_D$ is symmetric positive semidefinite.

If $L_{D}x=0$, step 1.1 gives a sum of nonnegative terms equal to $x^{\mathsf{T}}{L}_{D}x=0$. For every $e\in E_{+}$ its endpoint difference must therefore be zero. Along every path in $G_{+}$, $\bar{x}$ has equal values at successive vertices, hence is constant on each positive-conductance component; it is zero on any such component meeting $D$ because $\bar{x}=0$ there. Conversely, if these componentwise conditions hold, every edge with $c_e>0$ has zero endpoint difference, while an edge with $c_e=0$ contributes zero regardless of its difference. Thus $BC{B}^{\mathsf{T}}\bar{x}=0$ and $L_{D}x=0$.

Suppose $D=\mathrm{\varnothing }$. From [F1], every column of $B$ sums to zero, so ${\mathbf{1}}^{\mathsf{T}}B=0$ and therefore ${\mathbf{1}}^{\mathsf{T}}{L}_C=0$. Multiplying $M{u}^{\mathrm{\prime }}+L_{C}u=f$ on the left by ${\mathbf{1}}^{\mathsf{T}}$ gives ${\mathbf{1}}^{\mathsf{T}}M{u}^{\mathrm{\prime }}+{\mathbf{1}}^{\mathsf{T}}{L}_{C}u={\mathbf{1}}^{\mathsf{T}}f$. The second term vanishes, and the first is the derivative of ${\mathbf{1}}^{\mathsf{T}}Mu$, proving the balance law and its homogeneous conservation case.

For every outgoing index $j$, $q_j^{\mathrm{o}\mathrm{u}\mathrm{t}}={\sum }_i{P}_{ji}{q}_i^{\mathrm{i}\mathrm{n}}$ is a sum of nonnegative terms by [F1] and the assumption $q^{\mathrm{i}\mathrm{n}}\ge 0$. Hence $q^{\mathrm{o}\mathrm{u}\mathrm{t}}\ge 0$.

All sums are finite, so they may be interchanged: ${\sum }_j{q}_j^{\mathrm{o}\mathrm{u}\mathrm{t}}={\sum }_j{\sum }_i{P}_{ji}{q}_i^{\mathrm{i}\mathrm{n}}={\sum }_i\left({\sum }_j{P}_{ji}\right)q_i^{\mathrm{i}\mathrm{n}}={\sum }_i{q}_i^{\mathrm{i}\mathrm{n}},$ where the final equality uses the unit column sums of [F1].

Under the grounded condition, suppose $x\in {\mathbb{R}}^I$ and $x^{\mathsf{T}}{L}_{D}x=0$. By [F1], the zero extension of $x$ is constant on each positive-conductance component and zero on each such component meeting $D$. The grounded condition says every component containing a free vertex meets $D$, so every free coordinate is zero. Thus $L_D$ has trivial kernel; it is symmetric positive semidefinite by [F1], hence positive definite.

In the closed case, let $K=\ker L_C$. Symmetry implies $L_C(K^{\perp })\subseteq K^{\perp }$: for $x\in K^{\perp }$ and $k\in K$, $k^{\mathsf{T}}{L}_{C}x=(L_{C}k{)}^{\mathsf{T}}x=0$. If a vector $x\in K^{\perp }$ has $x^{\mathsf{T}}{L}_{C}x=0$, [F1] puts $x$ in $K$; hence $x=0$. Therefore the restriction $L_C{\mathrm{\mid }}_{K^{\perp }}$ is positive definite. It has trivial kernel and is an endomorphism of the finite-dimensional space $K^{\perp }$, so [F2] makes it onto. Thus each $b\in K^{\perp }$ has one gauged solution $u\in K^{\perp }$. By [F5], an orthonormal basis of $K^{\perp }$ identifies this restriction with a real symmetric positive definite matrix, including the zero-dimensional case.

For $\tau >0$ and any nonzero $x$, [F1] and [F4] give $x^{\mathsf{T}}(M+\tau L_D)x=x^{\mathsf{T}}Mx+\tau x^{\mathsf{T}}{L}_{D}x\ge {\sum }_i{m}_i{x}_i^2>0$. Thus $M+\tau L_D$ is positive definite.

The grounded matrix from step 1.1, the restricted Neumann matrix in the orthonormal coordinates constructed in the preceding argument, and the shifted mass matrix from step 1.3 are all real symmetric positive definite on their stated spaces. Each therefore has trivial kernel and is onto by [F2] on its finite-dimensional domain, so each right-hand side has a unique solution. Applying [F3] gives the exact-arithmetic CG Krylov Galerkin and energy-minimization conclusions.

Fix an edge cell $K=[a,b]$ of length $h_K=b-a$. By [F1] and [F2], the continuous representative of $u_e$ has endpoint values and the representative of $u_e^{\mathrm{\prime }}$ is absolutely continuous. Thus the slope of the nodal interpolant on $K$ is $s_K=\frac{u_e(b)-u_e(a)}{h_K}=\frac{1}{h_K}{\int }_a^b{u}_e^{\mathrm{\prime }}(y)dy\mathrm{.}$ The fundamental theorem in [F2] justifies this equality.

For any $x\in K$, [F2] and [F3] give $\mathrm{\mid }{u}_e^{\mathrm{\prime }}(x)-s_K\mathrm{\mid }\le \frac{1}{h_K}{\int }_a^b\mathrm{\mid }{u}_e^{\mathrm{\prime }}(x)-u_e^{\mathrm{\prime }}(y)\mathrm{\mid }dy\le \frac{1}{h_K}{\int }_a^b\sqrt{h_K}\mathrm{\parallel }{u}_e^{\mathrm{\prime }\mathrm{\prime }}{\mathrm{\parallel }}_{L^2(K)}dy=\sqrt{h_K}\mathrm{\parallel }{u}_e^{\mathrm{\prime }\mathrm{\prime }}{\mathrm{\parallel }}_{L^2(K)}\mathrm{.}$ Squaring and integrating over $x\in K$ yields $\mathrm{\parallel }(u_e-I_h{u}_e{)}^{\mathrm{\prime }}{\mathrm{\parallel }}_{L^2(K)}^2=\mathrm{\parallel }{u}_e^{\mathrm{\prime }}-s_K{\mathrm{\parallel }}_{L^2(K)}^2\le h_K^2\mathrm{\parallel }{u}_e^{\mathrm{\prime }\mathrm{\prime }}{\mathrm{\parallel }}_{L^2(K)}^2\mathrm{.}$ The first equality holds because the derivative of the nodal interpolant is the constant slope $s_K$ on K.

Multiply the cell estimate in step 2.1 by ${\kappa }_e$, sum over all cells, and use $h_K\le h$. The cells partition the edge interiors and their finitely many endpoints have measure zero. Hence ${\sum }_e{\kappa }_e\mathrm{\parallel }(u_e-I_h{u}_e{)}^{\mathrm{\prime }}{\mathrm{\parallel }}_{L^2(e)}^2\le h^2{\sum }_e{\kappa }_e\mathrm{\parallel }{u}_e^{\mathrm{\prime }\mathrm{\prime }}{\mathrm{\parallel }}_{L^2(e)}^2\mathrm{.}$ Taking square roots proves the displayed error estimate.

At an original vertex, the endpoint nodal value at every incident endpoint incidence is the common trace of $u$, so all interpolant traces agree, including both ends of a loop. At each anchor the nodal value is zero. The interpolant is real-valued, continuous and piecewise affine on each finite edge partition, so its weak derivative is its piecewise constant slope in $L^2$ (the internal endpoint terms cancel when testing against a smooth compactly supported function). Hence it belongs to the edge-product real $H^1$ space. Thus $I_{h}u\in V_D$ and it is affine on every cell by construction, which is exactly membership in $V_h$.

The canonical inclusion $i:V_D\to H$ is continuous because $\mathrm{\parallel }v{\mathrm{\parallel }}_H\le \mathrm{\parallel }v{\mathrm{\parallel }}_{V_D}$. It is injective because $V_D$ consists of Sobolev classes included in the edge-product $L^2$ classes. To prove density, fix $g=(g_e)\in H$ and $ϵ>0$. By [F2] and finite choice, choose for each of the finitely many edges a ${\varphi }_e\in C_c^{\mathrm{\infty }}(0,{\mathrm{\ell }}_e)$ with $\mathrm{\parallel }{g}_e-{\varphi }_e{\mathrm{\parallel }}_{L^2(e)}<ϵ\mathrm{/}\sqrt{\mathrm{\mid }E\mathrm{\mid }}$. The edge-product function $\varphi =({\varphi }_e)$ has zero endpoint traces, hence belongs to $V_D$, and $\mathrm{\parallel }g-\varphi {\mathrm{\parallel }}_H^2={\sum }_e\mathrm{\parallel }{g}_e-{\varphi }_e{\mathrm{\parallel }}_{L^2(e)}^2<{ϵ}^2$. Thus the range of i is dense in H.

By [F1] and [F3], H and V_D are real Hilbert spaces with dense continuous inclusion. With V_D^* as its continuous real dual, these spaces form the evolution triple of Evolution triples and the parabolic energy space. The mesh has finitely many cells, and a P1 function is determined by its finite list of nodal values; the vertex matching and anchor conditions are linear. Therefore V_h is a finite-dimensional subspace of V_D by [F8].

By [F4] and [F6], the form a is bounded by M=κmax and coercive by α on V_D, hence also on V_h. The restriction F_h(t):=f(t)|{V_h} is a bounded functional and its norm is at most |f(t)|{V^}; restriction is a continuous linear map from V_D^ to V_h^*, so F_h is strongly measurable and square-integrable. Thus all hypotheses of [F5] hold for the evolution triple and finite P1 subspace of step 1.2.

Applying [F5] gives the unique semidiscrete solution and its energy estimate for every t in [0,T]. No spatial approximation rate is part of [F5], so none follows here.

The form $a$ is symmetric and bilinear. By Cauchy–Schwarz on the finite edge product, $\mathrm{\mid }a(w,v)\mathrm{\mid }\le {\kappa }_{\max }\mathrm{\parallel }{w}^{\mathrm{\prime }}{\mathrm{\parallel }}_H\mathrm{\parallel }{v}^{\mathrm{\prime }}{\mathrm{\parallel }}_H\le {\kappa }_{\max }\mathrm{\parallel }w{\mathrm{\parallel }}_{V_D}\mathrm{\parallel }v{\mathrm{\parallel }}_{V_D}\mathrm{.}$ Thus it is bounded with constant $M={\kappa }_{\max }$.

By [F2], $\mathrm{\parallel }v{\mathrm{\parallel }}_{V_D}^2=\mathrm{\parallel }v{\mathrm{\parallel }}_H^2+\mathrm{\parallel }{v}^{\mathrm{\prime }}{\mathrm{\parallel }}_H^2\le (1+L_{\mathrm{\Gamma }}^2)\mathrm{\parallel }{v}^{\mathrm{\prime }}{\mathrm{\parallel }}_H^2\mathrm{.}$ Consequently $a(v,v)\ge {\kappa }_{\min }\mathrm{\parallel }{v}^{\mathrm{\prime }}{\mathrm{\parallel }}_H^2\ge \frac{{\kappa }_{\min }}{1+L_{\mathrm{\Gamma }}^2}\mathrm{\parallel }v{\mathrm{\parallel }}_{V_D}^2\mathrm{.}$ The form is coercive with $\alpha ={\kappa }_{\min }\mathrm{/}(1+L_{\mathrm{\Gamma }}^2)>0$.

The load $F(v)={\sum }_e\int f_e{v}_e$ is linear and satisfies $\mathrm{\mid }F(v)\mathrm{\mid }\le \mathrm{\parallel }f{\mathrm{\parallel }}_H\mathrm{\parallel }v{\mathrm{\parallel }}_H\le L_{\mathrm{\Gamma }}\mathrm{\parallel }f{\mathrm{\parallel }}_H\mathrm{\parallel }{v}^{\mathrm{\prime }}{\mathrm{\parallel }}_H\le L_{\mathrm{\Gamma }}\mathrm{\parallel }f{\mathrm{\parallel }}_H\mathrm{\parallel }v{\mathrm{\parallel }}_{V_D}$ by [F5] and [F2]. Hence $F$ is bounded on $V_D$.

Apply [F3] to the real Hilbert space [F1], the bounded coercive form from steps 1.1–1.2, and the bounded functional from step 1.3. It gives exactly one $u\in V_D$ satisfying $a(u,v)=F(v)$ for all $v\in V_D$. If this $u$ is edgewise H2, [F6] and the weak equation give, for every $v\in V_D$, ${\sum }_e{\int }_0^{{\mathrm{\ell }}_e}(-{\kappa }_e{u}_e^{\mathrm{\prime }\mathrm{\prime }}-f_e)v_{e}d{x}_e+{\sum }_{z\mathrm{\notin }D}v(z){\sum }_{\iota \in \mathcal{I}(z)}{\kappa }_{e(\iota )}{\mathrm{\partial }}_{{\nu }_{\iota }}{u}_{e(\iota )}(z)=0.$