Semi-Lagrangian characteristic transport

Let $d\ge 1$, let ${\mathrm{\ell }}_1,\dots ,{\mathrm{\ell }}_d>0$, and let $N_1,\dots ,N_d\ge 1$ be integers. The periodic rectangular box is ${\mathbb{T}}_{\mathrm{\ell }}^d:={\mathbb{R}}^d\mathrm{/}({\mathrm{\ell }}_1\mathbb{Z}\times \cdots \times {\mathrm{\ell }}_d\mathbb{Z})\mathrm{.}$ Set $h_j:={\mathrm{\ell }}_j\mathrm{/}{N}_j$. Its uniform tensor grid has nodes $x_{\mathit{i}}=(i_1{h}_1,\dots ,i_d{h}_d)$, indexed by $0\le i_j<N_j$, with indices understood modulo $N_j$.

For node data $V_{\mathit{i}}$ and a lift $x\in {\mathbb{R}}^d$ of a point on the torus, define $q_j:=\lfloor x_j\mathrm{/}{h}_j\rfloor ,{\theta }_j:=x_j\mathrm{/}{h}_j-q_j\in [0,1),$ and for $\mathit{ϵ}\in \{0,1{\}}^d$ define $w_{\mathit{ϵ}}(x):={\prod }_{j=1}^d{\theta }_j^{{ϵ}_j}(1-{\theta }_j{)}^{1-{ϵ}_j}\mathrm{.}$ The tensor-product multilinear interpolant is ${\mathcal{I}}_{h}V(x):={\sum }_{\mathit{ϵ}\in \{0,1{\}}^d}{w}_{\mathit{ϵ}}(x)V_{([q_1+{ϵ}_1{]}_{N_1},\dots ,[q_d+{ϵ}_d{]}_{N_d})},$ where $[k{]}_N$ is the residue in $\{0,\dots ,N-1\}$. The formula is unchanged when a period ${\mathrm{\ell }}_j$ is added to $x_j$, so it defines an interpolant on ${\mathbb{T}}_{\mathrm{\ell }}^d$. If $N_j=1$, the two corner indices in that coordinate coincide; the formula still gives the same node value.

For a continuous periodic function $v$, ${\mathcal{I}}_{h}v$ means the interpolant of its grid samples. Put $h:={\max }_j{h}_j$.

The picture shows one lifted coordinate cell. The weights are $1-\theta$ at the left endpoint and $\theta$ at the right endpoint; periodic wrapping only changes the node indices.

The diagram fixes the coordinate and weight convention only. The multidimensional interpolant is the product of the coordinate weights in the displayed formula.

Let $d\ge 1$, $T>0$, ${\mathrm{\ell }}_j>0$, and let $J\subseteq \mathbb{R}$ be an open interval containing $[0,T]$. Suppose $b:J\times {\mathbb{R}}^d\to {\mathbb{R}}^d$ is $C^1$ and periodic in $x_j$ with period ${\mathrm{\ell }}_j$ for every $j$. Choose a compact interval $K\subset J$ with $[0,T]\subset \mathrm{int}K$, and put $M_K:={\sup }_{K\times [0,{\mathrm{\ell }}_1]\times \cdots \times [0,{\mathrm{\ell }}_d]}\mathrm{\parallel }b{\mathrm{\parallel }}_2$. For every $s\in [0,T]$ and $x\in {\mathbb{R}}^d$, there is a unique solution $X(\cdot ;s,x)$ of $X^{\mathrm{\prime }}(t)=b(t,X(t)),X(s;s,x)=x,$ on the whole interval $[0,T]$. The lifted flow is periodic-equivariant: $X(t;s,x+\mathit{k}\mathbf{\ell })=X(t;s,x)+\mathit{k}\mathbf{\ell }(\mathit{k}\in {\mathbb{Z}}^d),$ where $\mathit{k}\mathbf{\ell }=(k_1{\mathrm{\ell }}_1,\dots ,k_d{\mathrm{\ell }}_d)$. If $M_T:={\sup }_{[0,T]\times [0,{\mathrm{\ell }}_1]\times \cdots \times [0,{\mathrm{\ell }}_d]}\mathrm{\parallel }b{\mathrm{\parallel }}_2$, then $\mathrm{\parallel }X(t;s,x)-x{\mathrm{\parallel }}_2\le M_T\mathrm{\mid }t-s\mathrm{\mid }(t\in [0,T])\mathrm{.}$ Thus each characteristic stays in a compact tube $[0,T]\times \bar{B}(x,M_{T}T+1)$.

Let $J=[a,b]$ be a compact bracket, let $y$ be an exact incoming characteristic on $J$, and let $g(t,x)$ be a boundary guard that is $L_g$-Lipschitz in its state argument on a tube containing the exact path and a dense reconstruction $U$. Suppose $h(t):=g(t,y(t))$ has a root $\tau \in J$ and a declared orientation $\sigma \in \{-1,1\}$ with $\sigma h^{\mathrm{\prime }}(t)\ge \nu >0$ throughout $J$. If ${\sup }_{t\in J}\mathrm{\parallel }y(t)-U(t){\mathrm{\parallel }}_2\le \eta ,\mathrm{\mid }g(\widehat{\tau },U(\widehat{\tau }))\mathrm{\mid }\le \epsilon ,\widehat{\tau }\in J,$ then the matched first-hit time satisfies $\mathrm{\mid }\widehat{\tau }-\tau \mathrm{\mid }\le \mathrm{\Delta }:=\frac{L_g\eta +\epsilon }{\nu }\mathrm{.}$ If the boundary value $\beta (t,x)$ is Lipschitz in time and state with constants $L_t^{\beta },L_x^{\beta }$ on the same tube and $\mathrm{\parallel }{y}^{\mathrm{\prime }}(t){\mathrm{\parallel }}_2\le M$, then $\mathrm{\mid }\beta (\widehat{\tau },U(\widehat{\tau }))-\beta (\tau ,y(\tau ))\mathrm{\mid }\le L_t^{\beta }\mathrm{\Delta }+L_x^{\beta }(\eta +M\mathrm{\Delta })\mathrm{.}$ This is a local one-hit bound. It gives no conclusion at grazing, unresolved, or simultaneous events.

An inflow/exit implementation must use a certified first-hit bracket and return unresolved when the bracket or orientation is not certified. This local result does not propagate errors through resets or an event list; those require the full finite-separated-event hypotheses of Finite separated transverse events give an event-aligned hybrid trajectory error bound.

Inputs are a periodic grid from Periodic tensor grids and multilinear interpolation, a finite horizon $T>0$, a positive integer $M$ of time steps, a periodic $C^1$ velocity $b$, periodic initial data $u_0$, node values $U_{\mathit{i}}^0=u_0(x_{\mathit{i}})$, and a nonnegative integer step budget $B$. Write $\mathrm{\Delta }t=T\mathrm{/}M$ and $t_n=n\mathrm{\Delta }t$. The output is either success with $U^0,\dots ,U^M$, or budget-exhausted with no partial final state.

1. If $B<M$, return budget-exhausted before changing the input data.
2. For $n=0,\dots ,M-1$ and each arrival node $x_{\mathit{i}}$, compute the explicit backward Euler foot lift ${\tilde{x}}_{\mathit{i}}^n:=x_{\mathit{i}}-\mathrm{\Delta }tb(t_{n+1},x_{\mathit{i}})\mathrm{.}$ Reduce each coordinate modulo its period when evaluating the periodic interpolant.
3. Set $U_{\mathit{i}}^{n+1}:={\mathcal{I}}_h{U}^n({\tilde{x}}_{\mathit{i}}^n)\mathrm{.}$
4. After the $M$ finite updates, return success with all node arrays.

The finite step budget counts time updates. Every update evaluates one foot per grid node and a finite sum of $2^d$ interpolation terms. The procedure imposes no bound on $\mathrm{\parallel }b\mathrm{\parallel }\mathrm{\Delta }t\mathrm{/}h$; the floor-and-fraction convention in the interpolation definition applies even when a foot crosses many grid cells.

This algorithm is the periodic-box branch. It does not wrap a foot through a nonperiodic boundary. An inflow/exit implementation must instead use an explicit first-hit oracle and return an unresolved status when the first hit or its error certificate is not resolved; A transverse backward boundary hit has a certified time and trace error bound records the transverse error interface. No grazing, simultaneous, or unbounded event sequence is hidden in the periodic update.

The algorithm defines tensor-product multilinear interpolation only. A higher-order replacement needs its own operator-norm or limiter bound and its own interpolation defect estimate; high order alone does not imply $L^{\mathrm{\infty }}$ contractivity.

For the periodic tensor interpolant of Periodic tensor grids and multilinear interpolation, every value is a convex combination of the $2^d$ corner data. Consequently nonnegative data remain nonnegative, the interpolant lies between the minimum and maximum corner values, and for any node arrays $V,W$, $\mathrm{\parallel }{\mathcal{I}}_{h}V-{\mathcal{I}}_{h}W{\mathrm{\parallel }}_{L^{\mathrm{\infty }}({\mathbb{T}}_{\mathrm{\ell }}^d)}\le \mathrm{\parallel }V-W{\mathrm{\parallel }}_{{\mathrm{\ell }}^{\mathrm{\infty }}}\mathrm{.}$ These conclusions hold at every foot, with no displacement-to-cell-size restriction.

Under the hypotheses of A periodic C1 velocity has a global characteristic flow on a finite horizon, fix $s,t\in [0,T]$ and let ${\mathrm{\Phi }}_{t,s}(x):=X(t;s,x)$ on the periodic lift ${\mathbb{R}}^d$. Then ${\mathrm{\Phi }}_{t,s}$ is a $C^1$ diffeomorphism with inverse ${\mathrm{\Phi }}_{s,t}$, and $\det D_x{\mathrm{\Phi }}_{t,s}(x)>0(x\in {\mathbb{R}}^d)\mathrm{.}$

Let $u\in C^2({\mathbb{T}}_{\mathrm{\ell }}^d)$ and let $h_j$ be the coordinate mesh widths in Periodic tensor grids and multilinear interpolation. Then $\mathrm{\parallel }{\mathcal{I}}_{h}u-u{\mathrm{\parallel }}_{L^{\mathrm{\infty }}({\mathbb{T}}_{\mathrm{\ell }}^d)}\le \frac{1}{8}{\sum }_{j=1}^d{h}_j^2\mathrm{\parallel }{\mathrm{\partial }}_{jj}u{\mathrm{\parallel }}_{L^{\mathrm{\infty }}({\mathbb{T}}_{\mathrm{\ell }}^d)}\mathrm{.}$ The estimate includes grid nodes and periodic cell endpoints.

Let $b\in C^1([0,T]\times {\mathbb{R}}^d;{\mathbb{R}}^d)$ be periodic in space, and set $M:=\sup \mathrm{\parallel }b{\mathrm{\parallel }}_2,L_x:=\sup \mathrm{\parallel }{D}_{x}b\mathrm{\parallel },L_t:=\sup \mathrm{\parallel }{\mathrm{\partial }}_{t}b{\mathrm{\parallel }}_2,$ where the suprema are over one full periodic time-space cylinder. For $0\le t_n<t_{n+1}\le T$, $\mathrm{\Delta }t=t_{n+1}-t_n$, and an arrival lift $x$, let $X(t_n;t_{n+1},x)$ be the exact backward characteristic foot. The explicit Euler foot $x-\mathrm{\Delta }tb(t_{n+1},x)$ satisfies $\parallel X(t_n;t_{n+1},x)-(x-\mathrm{\Delta }tb(t_{n+1},x)){\parallel }_2\le \frac{1}{2}(L_{x}M+L_t)(\mathrm{\Delta }t{)}^2\mathrm{.}$ The estimate is local for every positive $\mathrm{\Delta }t$; it requires no relation between displacement and grid width.

Assume the Axiom of Countable Choice. Let $\mathrm{\Omega }={\prod }_{j=1}^d(0,{\mathrm{\ell }}_j)$ be the bounded open fundamental box used for Lebesgue measure, and let $Q={\prod }_{j=1}^d[0,{\mathrm{\ell }}_j)$ be its half-open grid-indexing copy. Let $\mathrm{\Phi }$ be the periodic $C^1$ characteristic diffeomorphism of A periodic C1 characteristic map is an orientation-preserving diffeomorphism, and let $A_i\subseteq Q$ be a Lebesgue-measurable arrival cell with $\mathrm{\mid }{A}_i\mathrm{\mid }:={\lambda }_d(A_i\cap \mathrm{\Omega })>0$. Then $D_i:={\mathrm{\Phi }}^{-1}(A_i)$, interpreted on the torus and represented in $\mathrm{\Omega }$, is Lebesgue measurable and satisfies $0<\mathrm{\mid }{D}_i\mathrm{\mid }<\mathrm{\infty }\mathrm{.}$ This includes every finite tensor-grid cell with nonempty interior. The departure cells form a partition up to null sets whenever a finite family of arrival cells does; an exact torus partition pulls back to an exact torus partition.

Assume the Axiom of Countable Choice (The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$)) for this Lebesgue-measurable-volume branch. Work on the periodic box ${\mathbb{T}}_{\mathrm{\ell }}^d$ of Periodic tensor grids and multilinear interpolation. For measure calculations use the bounded open fundamental domain $\mathrm{\Omega }:={\prod }_{j=1}^d(0,{\mathrm{\ell }}_j)$; the period faces omitted from the half-open grid-indexing copy $Q={\prod }_{j=1}^d[0,{\mathrm{\ell }}_j)$ are Lebesgue-null by A box in ${\mathbb{R}}^n$ with parameters $a_i\le b_i$ is Lebesgue measurable of measure ${\prod }_{i<n}(b_i-a_i)$, whichever of its faces are included. For a periodic measurable set $E$, define $\mathrm{\mid }E\mathrm{\mid }:={\lambda }_d(E\cap \mathrm{\Omega })$, where ${\lambda }_d$ is the $d$-dimensional Lebesgue measure of Lebesgue measurable sets, the family $\mathcal{L}({\mathbb{R}}^n)$, and the restricted set function ${\lambda }_n$. Let $\{C_j{\}}_{j=1}^J$ be a finite measurable source-cell partition and $\{A_i{\}}_{i=1}^J$ a finite measurable arrival-cell partition of $\mathrm{\Omega }$ up to null sets, with every cell of positive volume; their grid labels use the half-open convention in $Q$. Let $\mathrm{\Phi }={\mathrm{\Phi }}_{t_{n+1},t_n}$ be the exact characteristic map from time $t_n$ to $t_{n+1}$. Its inverse images $D_i:={\mathrm{\Phi }}^{-1}(A_i)$ are the departure cells; Characteristic departure cells are measurable and have positive finite volume gives their measurability and positive finite volume, while A periodic C1 characteristic map is an orientation-preserving diffeomorphism gives the diffeomorphism and positive-Jacobian convention.

Given a source cell-average density ${\rho }_j^n$ on $C_j$, set ${\bar{\rho }}_i:=\frac{1}{\mathrm{\mid }{D}_i\mathrm{\mid }}{\sum }_{j=1}^J\mathrm{\mid }{D}_i\cap C_j\mathrm{\mid }{\rho }_j^n,{\rho }_i^{n+1}:=\frac{\mathrm{\mid }{D}_i\mathrm{\mid }}{\mathrm{\mid }{A}_i\mathrm{\mid }}{\bar{\rho }}_i\mathrm{.}$ The first formula is the exact intersection-volume remap of Intersection-volume conservative remapping from the source partition to the departure partition. The second is the characteristic volume factor that converts the average on a departure cell into the transported mass per arrival-cell volume. All intersections and volumes are exact in this mathematical definition; a geometric approximation or quadrature rule would require a separate error term.

The batch-63 PE17 definition is a draft carrier and its current body has been inspected. It defines the exact overlap weights $\mathrm{\mid }{T}_j\cap S_i\mathrm{\mid }$ and target-cell average for finite measurable partitions of a bounded finite-positive-measure domain; here take the open box $\mathrm{\Omega }$, source cells $S_j=C_j\cap \mathrm{\Omega }$, and target cells $T_i=D_i\cap \mathrm{\Omega }$. Countable Choice is the axiom used locally for Borel-to-Lebesgue measurability and the finite-volume branch. The separate batch-63 theorem that proves conservation and positivity also assumes Countable Choice, as recorded in the dependent theorem.

Fix $T>0$ and a periodic box with grid width $h={\max }_j{h}_j$. Let $u\in C^1([0,T];C^2({\mathbb{T}}_{\mathrm{\ell }}^d))$ solve the nonconservative linear transport equation $u_t+b\cdot \mathrm{\nabla }u=0,$ with the periodic $C^1$ velocity and global flow of A periodic C1 velocity has a global characteristic flow on a finite horizon. Consider $N$ equal time steps $\mathrm{\Delta }t=T\mathrm{/}N$ and node updates $U_{\mathit{i}}^{n+1}=({\mathcal{J}}_h{U}^n)({\tilde{x}}_{\mathit{i}}^n),$ where ${\mathcal{J}}_h$ reconstructs a nodal array as a periodic function and ${\tilde{x}}_{\mathit{i}}^n$ is a computed backward foot. Suppose constants $\mathrm{\Lambda }\ge 1$, $C_I\ge 0$, and $C_F\ge 0$ are uniform over the refinement family and independent of $h,\mathrm{\Delta }t,N$. Assume $\mathrm{\parallel }{\mathcal{J}}_{h}V-{\mathcal{J}}_{h}W{\mathrm{\parallel }}_{L^{\mathrm{\infty }}}\le \mathrm{\Lambda }\mathrm{\parallel }V-W{\mathrm{\parallel }}_{{\mathrm{\ell }}^{\mathrm{\infty }}}$ for all node arrays, the pointwise interpolation defect at each computed foot is at most $C_I{h}^{r+1}$ for the exact samples $u_{\mathit{i}}^n=u(x_{\mathit{i}},t_n)$, and, for compatible lifts of the computed and exact feet, the foot error satisfies $\mathrm{\parallel }{\tilde{x}}_{\mathit{i}}^n-X(t_n;t_{n+1},x_{\mathit{i}}){\mathrm{\parallel }}_2\le C_F(\mathrm{\Delta }t{)}^{q+1}$, for integers $q,r\ge 1$. If $L_u:={\sup }_{[0,T]\times {\mathbb{T}}_{\mathrm{\ell }}^d}\mathrm{\parallel }\mathrm{\nabla }u{\mathrm{\parallel }}_2$ and $E_n:={\max }_{\mathit{i}}\mathrm{\mid }{U}_{\mathit{i}}^n-u(x_{\mathit{i}},t_n)\mathrm{\mid }$, then, with ${\delta }_h:=C_I{h}^{r+1}+\mathrm{\Lambda }{L}_u{C}_F(\mathrm{\Delta }t{)}^{q+1},$ $E_N\le {\mathrm{\Lambda }}^N{E}_0+{\delta }_h{\sum }_{k=0}^{N-1}{\mathrm{\Lambda }}^k\mathrm{.}$ In the contractive case $\mathrm{\Lambda }=1$, this becomes $E_N\le E_0+T(C_I\frac{h^{r+1}}{\mathrm{\Delta }t}+L_u{C}_F(\mathrm{\Delta }t{)}^q)\mathrm{.}$ For the explicit Euler and tensor multilinear algorithm, Explicit Euler gives a second-order local backward-foot defect, Tensor multilinear interpolation has a second-derivative error bound, and Periodic multilinear interpolation is convex and L-infinity contractive give $q=r=1$ and $\mathrm{\Lambda }=1$. Thus convergence for this branch follows, for example, when $E_0\to 0$, $\mathrm{\Delta }t\to 0$, and $h^2\mathrm{/}\mathrm{\Delta }t\to 0$. No classical advective CFL restriction is used; the joint consistency refinement is still required by this bound.

For $\mathrm{\Lambda }>1$, the geometric sum in the first estimate is not uniformly bounded as $N$ grows. A high-order interpolation or limiter must therefore supply its actual operator bound and local defect before this theorem yields a stable convergence claim. This theorem is for the periodic branch; a nonperiodic boundary branch must separately account for first-hit and boundary-data error as in A transverse backward boundary hit has a certified time and trace error bound.

Assume Countable Choice and the finite measurable positive-volume partition hypotheses in Characteristic-cell overlap remapping for a conservative density. For nonnegative source averages ${\rho }_j^n\ge 0$, the characteristic-cell overlap remap satisfies ${\rho }_i^{n+1}\ge 0$ for every arrival cell and ${\sum }_i\mathrm{\mid }{D}_i\mathrm{\mid }{\bar{\rho }}_i={\sum }_j\mathrm{\mid }{C}_j\mathrm{\mid }{\rho }_j^n\mathrm{.}$ In particular, it satisfies ${\sum }_i\mathrm{\mid }{A}_i\mathrm{\mid }{\rho }_i^{n+1}={\sum }_j\mathrm{\mid }{C}_j\mathrm{\mid }{\rho }_j^n\mathrm{.}$ The proof applies Overlap remapping is an L2 projection, conservative and positive to the source partition $\{C_j\}$ and departure partition $\{D_i\}$; its stated Countable Choice assumption is included here.

The batch-63 definition and theorem bodies have been inspected. The theorem assumes Countable Choice and finite measurable partitions with positive cell volumes; the departure-volume lemma supplies measurability and positive volume for $\{D_i\}$, while the periodic grid supplies those properties for $\{C_j\}$. The cited PE17 carriers are drafts, and this Step 1 contract records mathematical and dependency readiness only; it does not claim independent approval.