roof of ordinary homomorphisms and, with an additional assumption of the
completeness of idempotents involved, a gluing of quasi-homomorphisms in the
sense of Definition 4.2.3 is nothing but the ordinary gluing of homomorphisms
after the replacement by roofs.

######  Remark 4.2.5.

$[$transitivity of subordination relation of idempotents$]$ Caution that for a
general noncommutative ${\mathbb{C}}$-algebra $A$, idempotents $e_{1}\prec
e_{2}$ and $e_{2}\prec e_{3}$ do not imply $e_{1}\prec e_{3}$. (E.g.
$A={\mathbb{C}}\langle
z_{1},z_{2},z_{2}\rangle/(z_{1}^{2}-z_{1},z_{2}^{2}-z_{2},z_{3}^{2}-z_{3},z_{1}z_{2}-z_{1},z_{2}z_{1}-z_{1},z_{2}z_{3}-z_{2},z_{3}z_{2}-z_{2})$.)
However, transitivity of $\prec$ holds for idempotents of the Azumaya/matrix
algebra $M_{r}({\mathbb{C}})$ of rank $r$ over ${\mathbb{C}}$, for all $r$.
(For idempotents $e_{1}\prec e_{2}$, $e_{2}\prec e_{3}$ in
$M_{r}({\mathbb{C}})$, the three $e_{1}$, $e_{2}$, $e_{3}$ must be commuting
and hence simultaneously diagonizable. Which implies $e_{1}\prec e_{3}$ in the
end.)

Homomorphisms from a $\Delta$-system of ${\mathbb{C}}$-algebras to a
${\mathbb{C}}$-algebra $A$

Let $\Delta$ be a fan in $N_{\mathbb{R}}$ that satisfies Assumption 2.2.2 and
$A$ a ${\mathbb{C}}$-algebra.

######  Definition 4.2.6.

[$\Delta$-system of idempotents in $A$] Let
$\mathbf{e}_{\Delta}^{A}:=\\{e_{\sigma}\\}_{\sigma\in\Delta}$ be a collection
of idempotents in $A$ labelled by cones in $\Delta$. $\mathbf{e}_{\Delta}^{A}$
is said to be

  * (i)

a weak $\Delta$-system of idempotents in $A$ if $e_{\tau}\preccurlyeq
e_{\sigma}$ for all $\tau\prec\sigma\in\Delta$;

  * (ii)

a strong $\Delta$-system of idempotents in $A$ if
$e_{\sigma}e_{\sigma^{\prime}}=e_{\sigma\cap\sigma^{\prime}}$ for all
$\sigma,\,\sigma^{\prime}\in\Delta$.

Note that since $\sigma\cap\sigma^{\prime}=\sigma^{\prime}\cap\sigma$, all the
idempotents in a strong $\Delta$-system of idempotents in $A$ commute with
each other. Furthermore, since $\tau\cap\sigma=\tau$ for
$\tau\prec\sigma\in\Delta$, a strong $\Delta$-system of idempotents in $A$ is
naturally a weak $\Delta$-system of idempotents in $A$.

######  Lemma/Definition 4.2.7.

[reduced idempotents in strong $\Delta$-system] Let
$\mathbf{e}_{\Delta}^{A}=\\{e_{\sigma}\\}_{\sigma\in\Delta}$ be a strong
$\Delta$-system of idempotents in $A$. Then, there exists a unique collection
$\\{\underline{e}_{\sigma}\\}_{\sigma\in\Delta}$ of orthogonal (i.e.
$\underline{e}_{\sigma}\,\underline{e}_{\sigma^{\prime}}=0$ for
$\sigma\neq\sigma^{\prime}$) idempotents in $A$ such that

$e_{\sigma}\;=\;\sum_{\tau\preccurlyeq\sigma}\underline{e}_{\tau}\,.$

$\underline{e}_{\sigma}$ is called the reduced idempotent associated to
$\sigma\in\Delta$ from the strong $\Delta$-system $\mathbf{e}_{\Delta}^{A}$.
It is the contribution to $e_{\sigma}$ after being trimmed away all the
boundary contributions.

###### Proof.

Explicitly, the reduced idempotent $\underline{e}_{\sigma}$, for
$\sigma\in\Delta(k)$, is given by:

$\displaystyle\underline{e}_{\,\sigma}\;:=\;e_{\sigma}\,-\sum_{\tau\in\Delta(k-1),\,\tau\prec\sigma}e_{\tau}\,+\sum_{\tau\in\Delta(k-2),\,\tau\prec\sigma}e_{\tau}\,-\sum_{\tau\in\Delta(k-3),\,\tau\prec\sigma}e_{\tau}$
$\displaystyle\hskip
20.00003pt+\,\cdots\,+(-1)^{k-1}\sum_{\tau\in\Delta(1),\,\tau\prec\sigma}e_{\tau}\,+(-1)^{k}e_{\mathbf{0}}\,.\hskip
120.00018pt$

Equivalently, let $\\{\tau_{1},\,\cdots\,,\,\tau_{k}\\}$ be the set of facets
(i.e. codimension-$1$ faces) of $\sigma\in\Delta(k)$, then

$\underline{e}_{\,\sigma}\;=\;e_{\sigma}-\sum_{i}e_{\tau_{i}}+\sum_{i_{1}<i_{2}}e_{\tau_{i_{1}}}e_{\tau_{i_{2}}}-\sum_{i_{1}<i_{2}<i_{3}}e_{\tau_{i_{1}}}e_{\tau_{i_{2}}}e_{\tau_{i_{3}}}+\,\cdots\,+(-1)^{k}e_{\tau_{1}}\cdots
e_{\tau_{k}}\,.$

Such inclusion-exclusion formula is akin and applies to simplicial cones.

That $\underline{e}_{\sigma}^{2}=\underline{e}_{\sigma}$, for
$\sigma\in\Delta$, and that
$\underline{e}_{\sigma}\,\underline{e}_{\sigma^{\prime}}=0$, for
$\sigma\neq\sigma^{\prime}$, follow by induction on ‘up to $k$’, $1\leq k\leq
n-1$.

∎

######  Definition 4.2.8.

[complete strong $\Delta$-system of idempotents] Let
$\mathbf{e}_{\Delta}^{A}:=\\{e_{\sigma}\\}_{\sigma\in\Delta}$ be a strong
$\Delta$-system of idempotents in $A$ and
$\underline{\mathbf{e}}_{\Delta}^{A}:=\\{\underline{e}_{\sigma}\\}_{\sigma\in\Delta}$
be the associated collection of reduced idempotents. We say that
$\mathbf{e}_{\Delta}^{A}$ is complete if
$\sum_{\sigma\in\Delta}\underline{e}_{\sigma}=1$.

With all these preparations, we are now ready for a key definition:

######  Definition 4.2.9.

[homomorphisms from inverse $\Delta$-system of ${\mathbb{C}}$-algebras to $A$]
Let ${\cal
Q}:=(\\{Q_{\sigma}\\}_{\sigma\in\Delta},\\{\iota_{\tau\sigma}^{\sharp}:Q_{\sigma}\rightarrow
Q_{\tau}\\}_{\tau\prec\sigma\in\Delta})$ be an inverse $\Delta$-system of
${\mathbb{C}}$-algebras. Denote the identity element of $Q_{\sigma}$ by
$1_{Q_{\sigma}}$ and that of $A$ by $1$. Then a collection

$\varphi^{\sharp}\;:=\;\\{f_{\sigma}^{\sharp}:Q_{\sigma}\rightarrow
A\\}_{\sigma\in\Delta}$

of ${\mathbb{C}}$-algebra quasi-homomorphisms indexed by cones in $\Delta$ is
called a homomorphism from ${\cal Q}$ to $A$, denoted now
$\varphi^{\sharp}:{\cal Q}\rightarrow A$, if

  * (i)

(Inverse $\Delta$-system of quasi-homomorphisms of ${\mathbb{C}}$-algebras)

$f_{\sigma}\;\stackrel{{\scriptstyle\iota_{\tau\sigma}^{\sharp}}}{{\rightsquigarrow}}\;f_{\tau}\,,\;\;\mbox{for
$\tau\prec\sigma\in\Delta$}\,,$

Cf. Definition 4.2.3. In particular,
$\mathbf{e}_{\varphi^{\sharp}}:=\\{e_{\sigma}:=f_{\sigma}^{\sharp}(1_{Q_{\sigma}})\\}_{\sigma\in\Delta}$
is a weak $\Delta$-system of idempotents in $A$, called the $\Delta$-system of
idempotents in $A$ associated to $\varphi^{\sharp}$.

  * (ii)

(Completeness) $\mathbf{e}_{\varphi^{\sharp}}$ is a complete strong
$\Delta$-system of idempotents in $A$.

For the simple uniformness of terminology but with slight abuse, we shall call
such homomorphisms also ${\mathbb{C}}$-algebra homomorphisms when need to
distinguish with homomorphisms of other algebraic structures. The set of
homomorphisms from ${\cal Q}$ to $A$ is thus denoted $\mbox{\it
Hom}\,_{{\mathbb{C}}{\mbox{\scriptsize\it-Alg}\,}}({\cal Q},A)$, or simply
$\mbox{\it Hom}\,({\cal Q},A)$.

######  Explanation 4.2.10.

[gluings of $\Delta$-system of (local) quasi-homomorphisms to
a “global” homomorphism] Given a homomorphism $\varphi^{\sharp}:{\cal
Q}\rightarrow A$ as defined in Definition 4.2.9. Let
$\underline{\mathbf{e}}_{\varphi^{\sharp}}:=\\{\underline{e}_{\sigma}\\}_{\sigma\in\Delta}$,
$e_{\sigma}:=f_{\sigma}^{\sharp}(1_{Q_{\sigma}})$, $\sigma\in\Delta$, be the
collection of the reduced idempotents from $\mathbf{e}_{\varphi^{\sharp}}$ and

$A_{\underline{e}_{\sigma}}\;:=\;\\{a\in
A\,|\,ae_{\underline{e}_{\sigma}}\,=\,e_{\underline{e}_{\sigma}}a\,=\,a\\}\,,\hskip
10.00002pt\mbox{$\sigma\in\Delta$}\,.$

Then, a generalization of Explanation 4.2.4 gives the inclusions of
${\mathbb{C}}$-algebras

$\displaystyle f_{\sigma}^{\sharp}(Q_{\sigma})$ $\displaystyle\subset$
$\displaystyle\oplus_{\tau\preccurlyeq\sigma}A_{\underline{e}_{\tau}}\;\;\mbox{(as
a multiplicatively closed ${\mathbb{C}}$-vector subspace of $A$)}$
$\displaystyle\simeq$
$\displaystyle\times_{\tau\preccurlyeq\sigma}A_{\underline{e}_{\tau}}\;\;\mbox{(as
an abstract ${\mathbb{C}}$-algebra)}\,,\hskip
10.00002pt\mbox{$\sigma\in\Delta$}\,,$

and commuting diagrams of homomorphisms of ${\mathbb{C}}$-algebras:

|
---|---
$\textstyle{A_{\varphi}\,:=\,\times_{\sigma\in\Delta}A_{\underline{e}_{\sigma}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pi_{A_{\varphi}}^{\sharp}}$$\scriptstyle{\jmath_{\sigma}^{\sharp}}$$\textstyle{A}$$\textstyle{Q_{\sigma}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f_{\sigma}^{\sharp}}$$\scriptstyle{\iota_{\tau\sigma}^{\sharp}}$$\textstyle{A_{\varphi,\,\sigma}\,:=\,\times_{\rho\preccurlyeq\sigma\in\Delta}A_{\underline{e}_{\rho}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\jmath_{\tau\sigma}^{\sharp}}$$\textstyle{Q_{\tau}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f_{\tau}^{\sharp}}$$\textstyle{A_{\varphi,\,\tau}\,:=\,\times_{\rho\preccurlyeq\tau\in\Delta}A_{\underline{e}_{\rho}}}$$\textstyle{,\>\>\mbox{for
$\tau\prec\sigma\in\Delta$}\,.}$

Here $\jmath_{\sigma}^{\sharp}:A_{\varphi}\rightarrow A_{\varphi,\sigma}$,
$\sigma\in\Delta$, and
$\jmath_{\tau\sigma}^{\sharp}:A_{\varphi,\,\sigma}\rightarrow
A_{\varphi,\,\tau}$ are the projection maps onto factors of product
${\mathbb{C}}$-algebras as indicated. The underlying geometry of the diagrams
is revealed in terms of commuting diagrams of morphisms of noncommutative
affine schemes in the opposite category: ($\amalg$ = disjoint union)

|
---|---
$\textstyle{\mbox{\it${\cal
S}\\!$cheme}\,(A_{\varphi})=\amalg_{\sigma\in\Delta}\mbox{\it${\cal
S}\\!$cheme}\,(A_{\underline{e}_{\sigma}})}$$\textstyle{\mbox{\it${\cal
S}\\!$cheme}\,(A)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pi_{A_{\varphi}}}$$\textstyle{\mbox{\it${\cal
S}\\!$cheme}\,(Q_{\sigma})}$$\textstyle{\mbox{\it${\cal
S}\\!$cheme}\,(A_{\varphi,\,\sigma})\rule{0.0pt}{11.99998pt}=\amalg_{\rho\preccurlyeq\sigma\in\Delta}\mbox{\it${\cal
S}\\!$cheme}\,(A_{\underline{e}_{\rho}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\jmath_{\sigma}}$$\scriptstyle{f_{\sigma}}$$\textstyle{\mbox{\it${\cal
S}\\!$cheme}\,(Q_{\tau})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{\tau\sigma}}$$\textstyle{\mbox{\it${\cal
S}\\!$cheme}\,(A_{\varphi,\,\tau})\rule{0.0pt}{11.99998pt}=\amalg_{\rho\preccurlyeq\tau\in\Delta}\mbox{\it${\cal
S}\\!$cheme}\,(A_{\underline{e}_{\rho}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\jmath_{\tau\sigma}}$$\scriptstyle{f_{\tau}}$,

for $\tau\prec\sigma\in\Delta$. Think of ${\cal Q}$ as defining
contravariantly a noncommutative space “$\mbox{\it Space}\,({\cal Q})$”.
$\varphi^{\sharp}$ then defines a morphism $\varphi:\mbox{\it${\cal
S}\\!$cheme}\,(A)\rightarrow\mbox{\it Space}\,(\cal Q)$ of noncommutative
spaces.

(Dynamical, complex algebraic) D-branes on a soft noncommutative scheme

Let $X$ be a (commutative) scheme over ${\mathbb{C}}$, ${\cal E}$ be a locally
free ${\cal O}_{X}$-module of rank $r$,

$X^{\\!{\mbox{\scriptsize\it A$\\!$z}}}\;=\;(X,\,{\cal
O}_{X}^{\mbox{\scriptsize\it A$\\!$z}}:={\mbox{\it${\cal E}\\!$nd}\,}_{{\cal
O}_{X}}({\cal E}),\,{\cal E})$

be the Azumaya/matrix scheme over ${\mathbb{C}}$ with the underlying topology
$X$ and the fundamental module ${\cal E}$, and $\breve{Y}$ be a soft
noncommutative scheme via toric geometry, with the structure sheaf

${\cal O}_{\breve{Y}}\;=\;\breve{\cal
R}_{\Delta}\;:=\;(\\{\breve{R}_{\sigma}\\}_{\sigma\in\Delta},\,\\{\iota_{\tau\sigma}^{\sharp}\\}_{\tau\prec\sigma\in\Delta})\,.$

an inverse $\Delta$-system of ${\mathbb{C}}$-algebras, cf. Definition 3.10.
Consider the sheaf of sets

$\mbox{\it${\cal H}$om}\,_{{\mathbb{C}}{\mbox{\scriptsize\it-Alg}\,}}({\cal
O}_{\breve{Y}},\,{\cal O}_{X}^{\mbox{\scriptsize\it A$\\!$z}})\hskip
10.00002pt\mbox{over $X$}$

associated to the presheaf defined by the assignment $U\mapsto\mbox{\it
Hom}\,_{{\mathbb{C}}{\mbox{\scriptsize\it-Alg}\,}}(\breve{R}_{\Delta},\,{\cal
O}_{X}^{\mbox{\scriptsize\it A$\\!$z}}(U))$ for $U$ open in $X$ and
restriction maps $\mbox{\it Hom}\,_{{\mathbb{C}}{\mbox{\scriptsize\it-
Alg}\,}}(\breve{R}_{\Delta},\,{\cal O}_{X}^{\mbox{\scriptsize\it
A$\\!$z}}(U))\rightarrow\mbox{\it Hom}\,_{{\mathbb{C}}{\mbox{\scriptsize\it-
Alg}\,}}(\breve{R}_{\Delta},\,{\cal O}_{X}^{\mbox{\scriptsize\it
A$\\!$z}}(V))$ via the post-composition with the ${\mathbb{C}}$-algebra
homomorphism ${\cal O}_{X}^{\mbox{\scriptsize\it A$\\!$z}}(U)\rightarrow{\cal
O}_{X}^{\mbox{\scriptsize\it A$\\!$z}}(V)$ for open sets $V\subset U\subset
X$.

######  Definition 4.2.11.

[D-brane on $\breve{Y}$: morphism $X^{\\!{\mbox{\it
Az}}}\rightarrow\breve{Y}$] A morphism $\varphi:X^{\\!{\mbox{\scriptsize\it
A$\\!$z}}}\rightarrow\breve{Y}$ is by definition a global section, in notation

$\varphi^{\sharp}\;:\;{\cal O}_{\breve{Y}}\;\longrightarrow\;{\cal
O}_{X}^{\mbox{\scriptsize\it A$\\!$z}}$

of $\mbox{\it${\cal H}$om}\,_{{\mathbb{C}}{\mbox{\scriptsize\it-Alg}\,}}({\cal
O}_{\breve{Y}},\,{\cal O}_{X}^{\mbox{\scriptsize\it A$\\!$z}})$. Explicitly,
$\varphi^{\sharp}$ is represented by the following data

$({\cal U}:=\\{U_{\alpha}\\}_{\alpha\in I},\varphi^{\sharp}_{\cal
U}:=\\{\varphi^{\sharp}_{\alpha}:\breve{R}_{\Delta}\rightarrow\mbox{\it
End}\,_{{\cal O}_{X}}({\cal E}|_{U_{\alpha}})\\}_{\alpha\in I})\,,$

where ${\cal U}$ is an open covering of $X$ and $\varphi^{\sharp}_{\cal U}$ a
collection of ${\mathbb{C}}$-algebra homomorphisms such that the following
diagrams commute

$\textstyle{\mbox{\it End}\,_{{\cal O}_{X}}({\cal
E}|_{U_{\alpha}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mbox{\it
End}\,_{{\cal O}_{X}}({\cal E}|_{U_{\alpha}\cap
U_{\beta}})}$$\textstyle{\breve{R}_{\Delta}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi^{\sharp}_{\alpha}}$$\scriptstyle{\varphi^{\sharp}_{\beta}}$$\textstyle{\mbox{\it
End}\,_{{\cal O}_{X}}({\cal
E}|_{U_{\beta}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$,

for all $\alpha,\,\beta\in I$.

With the additional data of a connection $\nabla$ on ${\cal E}$ (the Chan-
Paton sheaf with a gauge field) this gives a mathematical model for dynamical,
complex algebraic D-branes as an extended object moving on the soft
noncommutative target-space $\breve{Y}$ over ${\mathbb{C}}$. (One may also
introduce a Hermitian structure on ${\cal E}$ and consider only unitary
connections $\nabla$ on ${\cal E}$.)

######  Definition 4.2.12.

[surrogate of $X^{\\!A\\!z}$ associated to $\varphi$] The completeness
condition on idempotents (cf. Definition 4.2.9: Condition (ii)) implies that
the inclusion
${\cal A}_{\varphi}:={\cal O}_{X}\langle\varphi^{\sharp}({\cal
O}_{\breve{Y}})\rangle\hookrightarrow{\cal O}_{X}^{A\\!z}$ is an ${\cal
O}_{X}$-algebra homomorphism (rather than only a quasi-homomorphism of ${\cal
O}_{X}$-algebras). The corresponding noncommutative scheme $X_{\varphi}$ over
$X$ is called the surrogate of $X^{\\!A\\!z}$ associated to $\varphi$. The
sequence of ${\cal O}_{X}$-algebra inclusions ${\cal
O}_{X}\stackrel{{\scriptstyle\pi_{\varphi}^{\sharp}}}{{\hookrightarrow}}{\cal
A}_{\varphi}\hookrightarrow{\cal O}_{X}^{A\\!z}$ gives a sequence of dominant
morphisms $X^{\\!A\\!z}\longrightarrow\longrightarrow
X_{\varphi}\stackrel{{\scriptstyle\pi_{\varphi}}}{{\longrightarrow\longrightarrow}}X$.
By construction, $\varphi$ factors to a composition of
$X^{\\!A\\!z}\rightarrow\rightarrow X_{\varphi}\stackrel{{\scriptstyle
f_{\varphi}}}{{\longrightarrow}}\breve{Y}$.

######  Definition 4.2.13.

[image of $\varphi$ and push-forward Chan-Paton sheaf] The two-sided ideal
sheaf $\mbox{\it Ker}\,(\varphi^{\sharp})$ of ${\cal O}_{\breve{Y}}$ defines a
soft closed subscheme of $\breve{Y}$, denoted $\mbox{\it Im}\,\varphi$ and
called the image of $\varphi$. $\varphi^{\sharp}$ renders ${\cal E}$ an ${\cal
O}_{\breve{Y}}$-module, denoted $\varphi_{\ast}{\cal E}$ and called the push-
forward Chan-Paton sheaf on $\breve{Y}$. By construction, $\varphi_{\ast}{\cal
E}$ is supported on $\mbox{\it Im}\,\varphi$.

Figure 4-2-1.444Revised from: Chien-Hao Liu and Shing-Tung Yau, More on the
admissible condition on differentiable
maps $\varphi:(X^{\\!A\\!z},E;\nabla)\rightarrow Y$ in the construction of the
non-Abelian Dirac-Born-Infeld action $S_{DBI}(\varphi,\nabla)$,
arXiv:1611.09439 [hep-th] (D(13.2.1)), Figure 2-1.

Figure 4-2-1. A morphism $\varphi:X^{\\!A\\!z}\rightarrow\breve{Y}$ is
illustrated. Note that the image $\varphi(X^{\\!A\\!z})$ of $\varphi$ in $Y$
can have very rich variations of behavior as a closed subscheme of
$\breve{Y}$.

We conclude this subsection with a second guiding question:

######  Question 4.2.14.

[generalized matrix model] For $X$ a ${\mathbb{C}}$-point pt, ${\cal
E}={\mathbb{C}}^{r}$, and $\Delta=\\{\sigma\\}$, where $\sigma$ is a
simplicial cone of $N_{\mathbb{R}}$ of index $1$, one has that
$\breve{Y}(\Delta)=\mbox{\it nc}\mathbf{A}^{n}$ and morphisms from $\mbox{\it
pt}^{A\\!z}$ to $\mbox{\it nc}\mathbf{A}^{n}$ are given by tuples
$\mathbf{m}=(m_{1},\,\cdots\,,\,m_{n})$, $m_{i}\in M_{r}({\mathbb{C}})$. Such
$\mathbf{m}$’s (with possible Hermitian constraints) are fields in a matrix
model. From this aspect, a theory with fields morphisms from $\mbox{\it
pt}^{A\\!z}$ to a soft noncommutative toric scheme $\breve{Y}(\Delta)$ for a
fan $\Delta$ satisfying Assumption 2.2.2 gives a generalization of matrix
models via gluing simple matrix models on morphisms $\mbox{\it
pt}^{A\\!z}\rightarrow\mbox{\it nc}\mathbf{A}^{n}$. Details of some examples?
Consequences? Relations to Topological String Theory?

###  4.3 Two equivalent descriptions of a morphism
$\varphi:X^{\\!A\\!z}\rightarrow\breve{Y}$

The notion of a soft noncommutative toric scheme $\breve{Y}(\Delta)$ over
${\mathbb{C}}$ associated to a fan $\Delta$ can be generalized to the notion
of a soft noncommutative toric scheme $\breve{Y}_{X}(\Delta)$ over $X$
associated to $\Delta$ by generalizing the notion of an inverse
$\Delta$-system of ${\mathbb{C}}$ monoid algebras
$\\{{\mathbb{C}}\langle\breve{M}_{\sigma}\rangle\\}_{\sigma\in\Delta}$ to the
notion of an inverse $\Delta$-system of ${\cal O}_{X}$ monoid algebras
$\\{{\cal O}_{X}\langle\breve{M}_{\sigma}\rangle\\}_{\sigma\in\Delta}$.
Similarly, for close subschemes $\breve{Z}$ of $\breve{Y}$. This defines the
product space $X\times\breve{Y}$ of the commutative scheme $X$ and the soft
noncommutative scheme $\breve{Y}$ and its structure sheaf ${\cal
O}_{X\times\breve{Y}}$. The built-in inclusion

${\cal O}_{X}\;\hookrightarrow\;{\mbox{\it Center}\,}({\cal
O}_{X\times\breve{Y}})\;\subset\;{\cal O}_{X\times\breve{Y}}$

of ${\cal O}_{X}$-algebras defines the projection map $\mbox{\it
pr}_{X}:X\times\breve{Y}\rightarrow X$. In particular, an ${\cal
O}_{X\times\breve{Y}}$-module $\widetilde{\cal F}$ on $X\times\breve{Y}$ is
automatically an ${\cal O}_{X}$-module, denoted $\mbox{\it
pr}_{X,\,\ast}\,\widetilde{\cal F}$ or simply $\widetilde{\cal F}$. The built-
in inclusion

${\cal O}_{\breve{Y}}\;\hookrightarrow\;{\cal O}_{\breve{Y}}\cdot
1\;\subset{\cal O}_{X\times\breve{Y}}$

of ${\mathbb{C}}$-algebras defines the projection map $\mbox{\it
pr}_{\breve{Y}}:X\times\breve{Y}\rightarrow\breve{Y}$.

Let $\widetilde{\cal F}$ be a two-sided ${\cal O}_{X\times\breve{Y}}$-module.
The support of $\widetilde{\cal F}$, in notation $\mbox{\it
Supp}\,(\widetilde{\cal F})$, is by definition the closed subscheme of
$X\times\breve{Y}$ associated to the two-sided ideal sheaf of ${\cal
O}_{X\times\breve{Y}}$ generated by both left annihilators and right
annihilators of $\widetilde{\cal F}$

${\mbox{\it Ann}\,}(\widetilde{\cal F})\>:=\;(f\in{\cal
O}_{X\times\breve{Y}}\,|\,\mbox{$f\cdot\widetilde{\cal F}=0$ or
$\widetilde{\cal F}\cdot f=0$})\,.$

We say that $\widetilde{\cal F}$ is of relative dimension $0$ over $X$ if the
restriction of $\widetilde{\cal F}$ to each $\\{p\\}\times\breve{Y}$ for $p$ a
${\mathbb{C}}$-point on $X$ is a finitely dimensional ${\mathbb{C}}$-vector
space and ${\cal O}_{\mbox{\scriptsize\it Supp}\,(\widetilde{\cal F})}:={\cal
O}_{X\times\breve{Y}}/{\mbox{\it Ann}\,}(\widetilde{\cal F})$ is a coherant
${\cal O}_{X}$-module under $\mbox{\it pr}_{X,\,\ast}$.

######  Definition/Lemma 4.3.1.

[graph of morphism $\varphi:X^{\\!A\\!z}\rightarrow\breve{Y}$] Let
$\varphi:X^{\\!A\\!z}\rightarrow\breve{Y}$ be a morphism, defined via
$\varphi^{\sharp}:{\cal O}_{\breve{Y}}\rightarrow{\cal
O}_{X}^{A\\!z}:={\mbox{\it${\cal E}\\!$nd}\,}_{{\cal O}_{X}}({\cal E})$. Then,
$\varphi^{\sharp}$ determines a homomorphism of ${\cal O}_{X}$-algebras

$\widetilde{\varphi}^{\sharp}\;:\;{\cal
O}_{X\times\breve{Y}}\;\longrightarrow\;{\cal O}_{X}^{A\\!z}\,,\hskip
10.00002pt\mbox{with $f\cdot\breve{r}\longmapsto
f\cdot\varphi^{\sharp}(\breve{r})$ for all $f\in{\cal O}_{X}$ and
$\breve{r}\in{\cal O}_{\breve{Y}}$}\,.$

This defines the morphism $\widetilde{\varphi}:X^{\\!A\\!z}\rightarrow
X\times\breve{Y}$. The two-sided ideal sheaf $\mbox{\it
Ker}\,(\widetilde{\varphi}^{\sharp})$ of ${\cal O}_{X\times\breve{Y}}$ defines
a closed subscheme $\Gamma_{\varphi}$ of $X\times\breve{Y}$ that is isomorphic
to the surrogate $X_{\varphi}$ of $X^{\\!A\\!z}$ associated to $\varphi$, as
noncommutative schemes over $X$. By construction, $\widetilde{\cal
E}:=\widetilde{\varphi}_{\ast}{\cal E}$ is an ${\cal
O}_{X\times\breve{Y}}$-module supported on $\Gamma_{\varphi}$. The ${\cal
O}_{X\times\breve{Y}}$-module $\widetilde{\cal E}$ is called the graph of
$\varphi$. It has the property that

  * $\cdot$

$\widetilde{\cal E}$ is of relative dimension $0$ over $X$ and $\mbox{\it
pr}_{X,\,\ast}\widetilde{\cal E}={\cal E}$ (i.e. $\mbox{\it
pr}_{X,\,\ast}\widetilde{\cal E}\simeq{\cal E}$ canonically).

The converse also holds: Let $\widetilde{\cal E}$ be an ${\cal
O}_{X\times\breve{Y}}$-module of relative dimension $0$ over $X$ such that
${\cal E}:=\mbox{\it pr}_{X,\,\ast}\widetilde{\cal E}$ is a coherent locally
free ${\cal O}_{X}$-module, say of rank $r$ and
$X^{\\!A\\!z}:=(X,{\cal O}_{X}^{A\\!z}:={\mbox{\it${\cal E}\\!$nd}\,}_{{\cal
O}_{X}}({\cal E}),{\cal E})$ be the Azumaya scheme$/{\mathbb{C}}$ with the
fundamental module ${\cal E}$. Then, $\widetilde{\cal E}$ specifies a morphism
$\varphi:X^{\\!A\\!z}\rightarrow\breve{Y}$.

Cf. [L-L-S-Y: Figure 2-2-1] (D(2)).

###### Proof.

Via $\mbox{\it pr}_{\breve{Y}}^{\sharp}$, the ${\cal O}_{\breve{Y}}$-module
structure on $\widetilde{\cal E}$ induces a ${\cal O}_{\breve{Y}}$-module
structure on ${\cal E}$. This defines a homomorphism $\varphi^{\sharp}:{\cal
O}_{\breve{Y}}\rightarrow{\cal O}_{X}^{A\\!z}$.

∎

From Definition/Lemma 4.3.1, one realizes that

######  Lemma 4.3.2.

[$\varphi$ and moduli stack of $0$-dimensional ${\cal O}_{\breve{Y}}$-modules]
Let $\mathfrak{M}^{0;r}(\breve{Y})$ be the moduli stack of $0$-dimensional
${\cal O}_{\breve{Y}}$-modules that are of complex dimension $r$ as
${\mathbb{C}}$-vector spaces. Then a morphism from an Azumaya scheme over $X$
with the fundamental module of rank $r$ to $\breve{Y}$ gives a morphism
$X\rightarrow\mathfrak{M}^{0;r}(\breve{Y})$. Cf. [L-L-S-Y: Figure 3-1-1]
(D(2)).

## References

  * ††margin:  $\bullet$ References
  * [1] for D(15.1).
  * [2] Extended references in D(1) and D(2).
  * [Ar] M. Artin, On Azumaya algebras and finite dimensional representations of rings, J. Alg. 11 (1969), 532-563.
  * [Az] G. Azumaya, On maximally central algebras, Nagoya Math. J. 2 (1951), 119–150.
  * [A-K-M-V] M. Aganagic, A. Klemm, M. Mariño, and C. Vafa, Matrix model as a mirror of Chern-Simons theory, J. High Energy Phys. 02 (2004), 010, 45 pp. (arXiv:hep-th/0211098)
  * [A-N-T] E. Artin, C.J. Nesbitt, and R.M. Thrall, Rings with minimum condition, Univ. Michigan Press, 1944.
  * [Ba] C.P. Bachas, Lectures on D-branes, arXiv:hep-th/9806199.
  * [B-R-S-S-W] G. Bellamy, D. Rogalski, T. Schedler, J.T. Stafford, M. Wemyss, Noncommutative algebraic geometry, Math. Sci. Res. Inst. Publ. 64, Cambridge Univ. Press, 2016.
  * [Cox] D.A. Cox, The homogeneous coordinate ring of a toric variety, J. Alg. Geom. 4 (1995), 17-50; Erratum, 23 (2014), 393-398. (arXiv:alg-geom/9210008v3)
  * [C-K] D.A. Cox and S. Katz, Mirror symmetry and algebraic geometry, Math. Surv. Mono. vol. 68, Amer. Math. Soc., 1999.
  * [De] M. Dehn, Papers on group theory and topology, translated and introduced by J. Stillwell, Springer, 1987.
  * [D-K] Y.A. Drozd and V.V. Kirichenko, Finite dimensional algebras, with an Appendix by V. Dlab, translated from the Russian by V. Dlab, Springer, 1994.
  * [D-V1] R. Dijkgraaf and C. Vafa, Matrix models, topological strings, and supersymmetric gauge theories, Nucl. Phys. B644 (2002), 3-20. (arXiv:hep-th/0206255)
  * [D-V2] ——–, On geometry and matrix models, Nucl. Phys. B644 (2002), 21-39. (arXiv:hep-th/0207106)
  * [Ei] D. Eisenbud, Commutative algebra – with a view toward algebraic geometry, GTM 150, Springer, 1994.
  * [E-H] D. Eisenbud and J. Harris, The geometry of schemes, GTM 197, Springer, 2000.
  * [Fu] W. Fulton, Introduction to toric varieties, Ann. Math. Studies 131, Princeton Univ. Press, 1993.
  * [Ge] S.M. Gersten ed., Essays in group theory, Math. Sci. Res. Inst. Publ. 8, Springer, 1987.
  * [G-H-V] E. Ghys, A. Haefliger, A. Verjovsky eds., Group theory from a geometrical viewpoint, World Scientific, 1991.
  * [Ha] R. Hartshorne, Algebraic geometry, GTM 52, Springer, 1977.
  * [Hü] T. Hübsch, Calabi-Yau manifolds - A bestiary for physicists, World Scientific Publ., 1992.
  * [H-W] P.-M. Ho and Y.-S. Wu, Noncommutative geometry and D-branes, Phys. Lett. B398 (1997), 52-60. (arXiv:hep-th/9611233)
  * [Jo] C.V. Johnson, D-branes, Cambridge Univ. Press, 2003.
  * [Kl] A. A. Klyachko, Equivariant bundles over toric varieties, Math. USSR-Izv. 35 (1990), 337–375.
  * [K-L-M-V1] L. Katzarkov, E. Lupercio, L. Meersseman, and A. Verjovsky, The definition of a non-commutative toric variety, Contemp. Math. 620 (2014), 223-250.
  * [K-L-M-V2] ——–, Quantum (non-commutative) toric geometry: Foundation, arXiv: 2002.03876 [math.SG].
  * [K-S] A. Knutson and E. Sharpe, Sheaves on toric varieties for physics, Adv. Theor. Math. Phys. 3 (1998), 873-961. (arXiv:hep-th/9711036)
  * [La] C.I. Lazaroiu, Holomorphic matrix models, J. High Energy Phys. 05 (2003), 044. (arXiv:hep-th/0303008)
  * [Liu] C.-H. Liu, Azumaya noncommutative geometry and D-branes - an origin of the master nature of D-branes, lecture given at the workshop Noncommutative algebraic geometry and D-branes, December 12 – 16, 2011, organized by Charlie Beil, Michael Douglas, and Peng Gao, at Simons Center for Geometry and Physics, Stony Brook University, Stony Brook, NY; arXiv:1112.4317 [math.AG].
  * [L-Y1] C.-H. Liu and S.-T. Yau, Azumaya-type noncommutative spaces and morphisms therefrom: Polchinski’s D-branes in string theory from Grothendieck’s viewpoint, arXiv:0709.1515 [math.AG]. (D(1))
  * [L-L-S-Y] S. Li, C.-H. Liu, R. Song, and S.-T. Yau, Morphisms from Azumaya prestable curves with a fundamental module to a projective variety: Topological D-strings as a master object for curves, arXiv:0809.2121 [math.AG]. (D(2))
  * [L-Y2] C.-H. Liu and S.-T. Yau, D-branes and Azumaya/matrix noncommutative differential geometry, I: D-branes as fundamental objects in string theory and differentiable maps from Azumaya/matrix manifolds with a fundamental module to real manifolds, arXiv:1406.0929 [math.DG]. (D(11.1))
  * [L-Y3] ——–, D-branes and Azumaya/matrix noncommutative differential geometry, II: Azumaya/matrix supermanifolds and differentiable maps therefrom – with a view toward dynamical fermionic D-branes in string theory, arXiv:1412.0771 [hep-th]. (D(11.2))
  * [L-Y4] ——–, Dynamics of D-branes I. The non-Abelian Dirac-Born-Infeld action, its first variation, and the equations of motion for D-branes – with remarks on the non-Abelian Chern-Simons/Wess-Zumino term, arXiv:1606.08529 [hep-th]. (D(13.1))
  * [L-Y5] ——–, Dynamics of D-branes II. The standard action – an analogue of the Polyakov action for (fundamental, stacked) D-branes, arXiv:1704.03237 [hep-th]. (D(13.3))
  * [L-Y6] ——–, Grothendieck meeting [Wess & Bagger]: Wess & Bagger [Supersymmetry and supergravity: Chs. IV, V, VI, VII, XXII] (2nd ed.) reconstructed in complexified ${\mathbb{Z}}/2$-graded $C^{\infty}$-Algebraic Geometry I. The construction under a trivialization of the Weyl spinor bundles by complex conjugate pairs of covariantly constant sections, arXiv:2002.11868 [math.AG]. (SUSY (2.1))
  * [L-Y7] ——–, manuscript in preparation.
  * [Man] Y.I. Manin, Quantum groups and noncommutative geometry, 2nd ed., with a contribution by T. Raedschelders and M. Van den Bergh, CRM Short Courses, Springer, 2018.
  * [Mar] M. Mariño, Chern-Simons theory, matrix models and topological strings, Oxford Univ. Press, 2005.
  * [Mu] D. Mumford, Picard groups of moduli problems, Arithmetical algebraic grometry, Proceedings of Conference, Purdue Univ., 1963, O.F.G. Schilling ed., 33-81, Harper & Row, 1965.
  * [Og] A. Ogus, Lectures on logarithmic algebraic geometry, Cambridge Stud. Adv. Math. 178, Cambridge Univ. Press, 2018.
  * [Or] O. Ore, Theory of non-commutative polynomials, Ann. Math. 34 (1933), 480-508.
  * [Po1] J. Polchinski, Lectures on D-branes, in “Fields, strings, and duality”, TASI 1996 Summer School, Boulder, Colorado, C. Efthimiou and B. Greene eds., World Scientific, 1997. (arXiv:hep-th/9611050)
  * [Po2] ——–, String theory, vol. I : An introduction to the bosonic string; vol. II : Superstring theory and beyond, Cambridge Univ. Press, 1998.
  * [Ro1] A.L. Rosenberg, Noncommutative algebraic geometry and representations of quantized algebras, Kluwer, 1995.
  * [Ro2] ——–, Noncommutative spaces and schemes, preprint MPI-1999-84; Spectra of noncommutative spaces, preprint MPI-2003-110; Underlying spaces of noncommutative schemes, preprint MPI-2003-111; Spectra related with localizations, preprint MPI-2003-112; Spectra of ‘spaces’ represented by abelian categories, preprint MPI-2004-115.
  * [Sz] R.J. Szabo, An introduction to string theory and D-brane dynamics, with problems and solutions, 2nd, Imperial College Press, 2011.
  * [Wi] E. Witten, Bound states of strings and $p$-branes, Nucl. Phys. B460 (1996), 335-350. (arXiv:hep-th/9510135)

<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS>


# Prompt-Time Symbolic Knowledge Capture with Large Language Models

Tolga Çöplü, Arto Bendiken, Andrii Skomorokhov, Eduard Bateiko, Stephen Cobb,
Joshua J. Bouw
Haltia, Inc.
{tolga, arto, andrii, eduard, steve<EMAIL_ADDRESS>

###### Abstract

Augmenting large language models (LLMs) with user-specific knowledge is
crucial for real-world applications, such as personal AI assistants. However,
LLMs inherently lack mechanisms for prompt-driven knowledge capture. This
paper investigates utilizing the existing LLM capabilities to enable prompt-
driven knowledge capture, with a particular emphasis on knowledge graphs. We
address this challenge by focusing on prompt-to-triple (P2T) generation. We
explore three methods: zero-shot prompting, few-shot prompting, and fine-
tuning, and then assess their performance via a specialized synthetic dataset.
Our code and datasets are publicly available at
https://github.com/HaltiaAI/paper-PTSKC

##  1 Introduction

Large language models (LLMs) are transforming human-machine interaction with
their adeptness in carrying out conversations. However, despite their
proficiency in responding to queries, LLMs cannot be considered good
listeners. Their limitation lies in their inability to learn from user-
provided information. To utilize any data received from users beyond their
context window, LLMs require support from an external system, a significant
gap in their interactive capabilities.

Primarily, LLMs capture knowledge during their training phase. This phase,
which enables the implicit encoding of knowledge into the model’s parameters,
is deemed efficient in terms of data compression. However, the substantial
computational power, time, and cost required for training, particularly in the
pre-training stage, render it impractical for prompt-driven continuous
learning. LLMs are unable to capture knowledge obtained from users or through
external integrations/plugins, which presents significant challenges for many
AI applications. For instance, the ability of AI assistants to capture and
utilize personal information in future interactions is crucial. This
limitation is currently being addressed through various Retrieval-Augmented
Generation (RAG) approaches. Within this realm, knowledge graphs are
distinguished by their clear structures, symbolic representations, and
capacity for factual reasoning, making their integration with LLMs a vibrant
area of ongoing research [1, 2].

In this paper, we focus on the building blocks of prompt-driven symbolic
knowledge capture. We investigate the extraction of prompts in subject-
predicate-object triples111https://www.w3.org/TR/rdf12-concepts/ for a
predefined context (relation) through in-context learning and fine-tuning
approaches. Utilizing a specially designed dataset, we aim to assess the
efficacy of these methods, highlighting their strong points and identifying
areas for enhancement.

The structure of this paper is as follows: Section 2 introduces the proposed
in-context learning and fine-tuning approaches by providing examples. Section
3 describes the experimental setup by presenting the development framework,
the language model selection, and the dataset creation process. Section 4
outlines our test results and their interpretations. Finally, Section 5
concludes the paper and suggests future directions.

##  2 Prompt-to-triple generation

Triples, composed of (’subject’, ’predicate’, ’object’), are considered a
universal data model thanks to their inherent simplicity and versatility. This
format reflects the fundamental structure of human language and cognition,
capturing the essence of any asserted statement or fact. Each triple
represents a distinct atom of knowledge, with the subject and object
identifying entities and the predicate describing their relationship. In our
study, we have chosen triples as our data model for these characteristics.
Furthermore, for ease of presentation, we employ an informal free-form triple
format, which allows for greater flexibility in our discussions and examples.

Generating triples based on a predefined context from user prompts can be
viewed as a specific aspect of the broader text-to-graph (T2G) generation
problem [3, 4]. This perspective led us to define our research problem as
prompt-to-triple (P2T) generation. P2T generation entails extracting ’subject’
and ’object’ terms from user prompts that correspond with a ’predicate’ drawn
from a restricted vocabulary. This vocabulary consists of predefined, user-
specific relations such as birthdays, anniversaries, locations, and events. A
key aspect is ensuring that the ’predicate’ term of the generated triple
accurately reflects the relevant predefined relation. For example, from the
prompt ’I was born in 1979’, our goal is to generate the triple (’I’,
’birthday’, ’1979’), aligning with the ’birthday’ relation.

In our research, we began by pinpointing some relevant predefined relations
(aka a restricted vocabulary for the ‘predicate’ term). Following on this, we
developed the requisite training and test datasets essential for addressing
the problem. Building on this groundwork, we have formulated the following
three methodologies to effectively tackle the P2T generation challenge

###  2.1 P2T zero-shot prompting

Zero-shot prompting is an in-context learning technique that enables LLMs to
apply their inherent knowledge to complete tasks without additional training.
This approach is relevant in the T2G generation domain, especially in the
multi-turn question answering form, as noted in [5]. However, the P2T
generation task requires tailored zero-shot prompts due to specific predefined
relations. Our approach has evolved through a series of iterative developments
and tests. The critical aspects of zero-shot prompting, as explored in our
research, include:

Figure 1: Cases of zero-shot prompting to demonstrate the evaluation.

  * •

For the prompt context to match the predefined relations, the set of
predefined relations must be present in the system prompt. This leads to
scalability issues, as both the prompt size and processing time vary with the
size of the relation set.

  * •

Due to pre-training biases, LLMs often default to assigning the sentence’s
verb to the ’predicate’ term. This can result in incorrect triples when the
verb doesn’t match the predefined relation, despite explicit instructions for
relation matching. To improve accuracy, we introduced an extra term for
relation matching, which is then incorporated into the ‘predicate’ term via
post-processing. Relevant cases are presented in Figure.1. Case 1 demonstrates
that, in the absence of explicit instructions, the LLM generates the
‘predicate’ by utilizing the verb from the provided sentence, aligning with
expectations. In Case 2, despite clear instructions for relation matching, the
selection of either ’anniversary’ or ’birthday’ as the predicate is
suppressed. Case 3 resolves this by using a new ’relation’ term specifically
for matching ’birthday’ or ’anniversary’.

  * •

LLMs can recognize that a sentence context falls outside the predefined
relation set, even without explicit instruction in the zero-shot prompt. The
LLM even adds a justification in the response. An instance of this scenario is
depicted in Figure.2.

Figure 2: Zero-shot prompting case for out-of-context input

###  2.2 P2T few-shot prompting

Few-shot prompting, an in-context learning technique, provides an LLM with a
small set of examples to enhance its task understanding before generating a
response [6]. This method stands apart from zero-shot prompting, which
requires no examples, and fine-tuning, which demands extensive training data.
Few-shot prompting seeks a balance by offering sufficient context for
efficient model operation. Although there are criticisms in the literature [7,
8] regarding the efficiency of few-shot prompting, in our study, we aimed to
evaluate this method using our own dataset. Mirroring the approach used in
zero-shot prompting, we adopted an iterative development and testing cycle for
few-shot prompting. The significant aspects of few-shot prompting are outlined
below:

  * •

In a few-shot prompting, providing an example for every predefined relation is
necessary. This requirement, similar to zero-shot prompting, leads to
scalability challenges.

  * •

The variety of examples has a direct impact on performance. To effectively
match the ’birthday’ relation, examples must cover various sentence
structures, such as “I was born in 1979” and “My birthday is in November”.
Relevant cases are presented in Figure.3.

Figure 3: The impact of example diversity is presented with two different few-
shot prompts

  * •

When the LLM encounters a sentence context outside the predefined relation
set, it relies on its implicit knowledge to perform triple extraction, due to
the absence of a corresponding example in the few-shot prompt. Figure.4
represents a case of this particular scenario.

Figure 4: Few-shot prompting example for out of context input

###  2.3 P2T generation using a fine-tuned LLM

Fine-tuning is a process where a pre-trained LLM is further trained on a
specific dataset. This technique adjusts the model’s parameters to make it
more adept at a particular task, such as P2T generation in our case. The
following points highlight the key aspects of P2T fine-tuning:

  * •

The training dataset is critical to the success of the fine-tuning process. It
provides a targeted environment with specific examples for relation matching
and extracting subjects and objects, requiring a diverse array of examples to
address all potential issues. Details regarding the dataset and its generation
are presented in Section 3.3.

  * •

For each predefined relation, the training dataset must contain varied
examples. This requirement does not lead to scalability issues as in zero-shot
or few-shot prompting, but an enlarged training set might increase the risk of
performance degradation in other tasks for the LLM.

  * •

When the LLM encounters a sentence context not present in the predefined
relation set, it resorts to its implicit knowledge for triple extraction,
similar to the few-shot prompting scenario. Figure.5 presents cases for
relations both included and excluded in the training set.

Figure 5: Fine-tuning examples for in-context and out-of-context prompts

##  3 Experimental setup

This section explores the components of our experimental setup.

###  3.1 Development framework

The methods suggested in this paper have been implemented using the Apple MLX
framework [9]. MLX is a specialized array framework designed for machine
learning applications, akin to NumPy, PyTorch, or Jax, with the distinction of
being exclusive to Apple silicon.

P2T fine-tuning has been conducted using the parameter-efficient QLoRA
approach [10] on our custom dataset, comprising randomly selected, non-
overlapping sets of 1,000 training, 200 validation, and 200 test samples. The
fundamental QLoRA parameters used are as follows:

  * •

Optimizer: Adam

  * •

Learning rate: $1x10^{-5}$

  * •

Number of layers to fine-tune: 16

  * •

Minibatch size: 4

  * •

Iterations: 1,000

###  3.2 LLM

The methods we have developed here do not have a structural dependency on a
particular underlying foundation model.. The key factors guiding our LLM
selection were its proven effectiveness across diverse domains in community
benchmarks and its prevalence in the field. Owing to its performance in the
Hugging Face Leadership benchmark [11] and its robust ecosystem, the
Mistral-7B-Instruct-v0.2 [12], based on the Llama 2 [13] architecture, was
selected for our research. We ran all examples, tests, and benchmarks on a
4-bit quantized version of this model.

###  3.3 Dataset

In the field of natural language processing (NLP), the creation of robust and
diverse datasets is crucial for training and evaluating LLMs, especially for
tasks such as knowledge extraction, which involves identifying structured
information from unstructured text. Aligning with these needs, we have created
a synthetic dataset focused on ’birthday’ and ’anniversary’ content for P2T
generation study, adhering to the detailed stages described below.

Our synthetic dataset creation process consists of three distinct stages:

  1. 1.

We engaged native speakers to write templates for 86 user prompts and model
responses. This initial step ensures the dataset’s foundational accuracy and
contextual relevance.

  2. 2.

We leveraged Python’s capabilities, particularly a random date generator, to
expand this dataset from 86 to 860 prompt-response pairs.

  3. 3.

The final stage of our dataset development involved using an LLM, specifically
Llama-2-7b-chat-hf, to paraphrase each prompt from the previous dataset five
times. This resulted in a new dataset of 4300 prompt-response pairs.
Paraphrasing is a critical step as it introduces linguistic variations and
nuances, thereby enriching the dataset and making it more representative of
natural language variability [14, 15]. This approach is supported by recent
studies which highlight the importance of paraphrasing in dataset creation for
NLP tasks, as it significantly contributes to model generalizability and
understanding of diverse linguistic expressions.

##  4 Performance evaluation

We have evaluated the proposed methods using a non-overlapping test dataset,
comprising 128 ’birthday’ and 72 ’anniversary’ relations. The outputs
generated during the evaluation were compared with manually crafted ground-
truths. The comparisons were conducted in two distinct manners: ‘relation-
based’ and ‘triple-based’.

  * •

Relation-based comparison: This approach focuses solely on the ’predicate’
term. In this scenario, equality between the test result and the ground-truth
value is reported as a True Positive (TP). ’Predicate’ values falling outside
the predefined relation set are reported as False Negatives (FN), while those
within the set but differing from the ground-truth are reported as False
Positives (FP).

  * •

Triple-based comparison: This method involves comparing all terms of the
generated triple. The comparison of the ’predicate’ term follows the same
approach as the relation-based method. However, the ’subject’ and ’object’
values are compared based on a relationship of inclusion rather than direct
equality. For example, a generated triple (’I’, ’birthday’, ’November 14th’)
compared with the ground truth (’I me’, ’birthday’, ’November 14’) is
classified as TP.

The macro precision, recall, and f1-score calculated for both the relation-
based and entity-based approaches are presented in Table 1.

As indicated in Table 1, the recall for relation-based evaluation is
impeccable across all methods. We believe this outcome is associated with the
tests being conducted on only two relations. When considering precision and
f1-score, it is observed that both zero-shot prompting and fine-tuning methods
emerge as prominent. We assess that the clear guidance provided by the zero-
shot prompt, instructing the LLM to select one of the predefined relations,
plays a significant role in its superior performance compared to few-shot
prompting. The fact that the fine-tuning method yields significantly good
results clearly demonstrates its success in learning straightforward tasks.

Upon examining the triple segment in Table 1, we observe that despite
differing precision and recall performance, zero-shot prompting and few-shot
prompting methods exhibit similar f1-scores. In this segment, fine-tuning has
demonstrated superior performance compared to other methods. These outcomes
motivate us to focus on fine-tuning and conduct more comprehensive studies on
it.

Table 1: Relation and triple generation performance based on macro precision, recall and f1-score. | Relation | Triple
---|---|---
| Precision | Recall | F1-score | Precision | Recall | F1-score
zero-shot prompting | 0.815 | 1.0 | 0.8981 | 0.6636 | 0.4479 | 0.5348
few-shot prompting | 0.49 | 1.0 | 0.6577 | 0.3855 | 0.6531 | 0.4848
fine-tuning | 1.0 | 1.0 | 1.0 | 1.0 | 0.96 | 0.9796

##  5 Conclusion

In this paper, we initially discussed prompt-driven symbolic knowledge capture
and its significance in the LLM domain. We then projected the prompt-driven
symbolic knowledge capture problem into prompt-to-triple (P2T) generation,
which involves generating triples based on predefined relations from user
prompts. To address P2T, we developed new approaches using fundamental LLM
techniques, including in-context learning and fine-tuning. We concluded our
work with performance evaluations of these proposed methods.

Our findings indicate that fine-tuning is particularly sensitive in addressing
P2T. In our future work, we aim to refine the fine-tuning approach and
comprehensively examine its impact on the overall performance of the model
across across various scenarios.

Please see the corresponding GitHub repository at
https://github.com/HaltiaAI/paper-PTSKC

## References

  * Pan et al. [2023a] Jeff Z. Pan, Simon Razniewski, Jan-Christoph Kalo, Sneha Singhania, Jiaoyan Chen, Stefan Dietze, Hajira Jabeen, Janna Omeliyanenko, Wen Zhang, Matteo Lissandrini, Russa Biswas, Gerard de Melo, Angela Bonifati, Edlira Vakaj, Mauro Dragoni, and Damien Graux.  Large Language Models and Knowledge Graphs: Opportunities and Challenges, August 2023a.  URL http://arxiv.org/abs/2308.06374.  arXiv:2308.06374 [cs].
  * Pan et al. [2023b] Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu.  Unifying Large Language Models and Knowledge Graphs: A Roadmap, June 2023b.  URL http://arxiv.org/abs/2306.08302.  arXiv:2306.08302 [cs].
  * Guo et al. [2020] Qipeng Guo, Zhijing Jin, Xipeng Qiu, Weinan Zhang, David Wipf, and Zheng Zhang.  CycleGT: Unsupervised Graph-to-Text and Text-to-Graph Generation via Cycle Training, December 2020.  URL http://arxiv.org/abs/2006.04702.  arXiv:2006.04702 [cs].
  * Xu et al. [2022] Yi Xu, Luoyi Fu, Zhouhan Lin, Jiexing Qi, and Xinbing Wang.  INFINITY: A Simple Yet Effective Unsupervised Framework for Graph-Text Mutual Conversion, September 2022.  URL http://arxiv.org/abs/2209.10754.  arXiv:2209.10754 [cs].
  * Li et al. [2019] Xiaoya Li, Fan Yin, Zijun Sun, Xiayu Li, Arianna Yuan, Duo Chai, Mingxin Zhou, and Jiwei Li.  Entity-Relation Extraction as Multi-Turn Question Answering, September 2019.  URL http://arxiv.org/abs/1905.05529.  arXiv:1905.05529 [cs].
  * Brown et al. [2020] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language Models are Few-Shot Learners, July 2020.  URL http://arxiv.org/abs/2005.14165.  arXiv:2005.14165 [cs].
  * Ma et al. [2023] Yubo Ma, Yixin Cao, YongChing Hong, and Aixin Sun.  Large Language Model Is Not a Good Few-shot Information Extractor, but a Good Reranker for Hard Samples!, October 2023.  URL http://arxiv.org/abs/2303.08559.  arXiv:2303.08559 [cs].
  * Zhu et al. [2023] Yuqi Zhu, Xiaohan Wang, Jing Chen, Shuofei Qiao, Yixin Ou, Yunzhi Yao, Shumin Deng, Huajun Chen, and Ningyu Zhang.  LLMs for Knowledge Graph Construction and Reasoning: Recent Capabilities and Future Opportunities, May 2023.  URL http://arxiv.org/abs/2305.13168.  arXiv:2305.13168 [cs].
  * Hannun et al. [2023] Awni Hannun, Jagrit Digani, Angelos Katharopoulos, and Ronan Collobert.  MLX: Efficient and flexible machine learning on apple silicon.  https://github.com/ml-explore, 2023.
  * Dettmers et al. [2023] Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer.  QLoRA: Efficient Finetuning of Quantized LLMs, May 2023.  URL http://arxiv.org/abs/2305.14314.  arXiv:2305.14314 [cs].
  * Beeching et al. [2023] Edward Beeching, Clementine Fourrier, Nathan Habib, Sheon Han, Nathan Lambert, Nazneen Rajani, Omar Sanseviero, Lewis Tunstall, and Thomas Wolf.  Open llm leaderboard.  https://huggingface.co/spaces/HuggingFaceH4/open_llm_leaderboard, 2023.
  * Jiang et al. [2023] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed.  Mistral 7B, October 2023.  URL http://arxiv.org/abs/2310.06825.  arXiv:2310.06825 [cs].
  * Touvron et al. [2023] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom.  Llama 2: Open foundation and fine-tuned chat models, 2023.
  * Feng et al. [2021] Steven Y. Feng, Varun Gangal, Jason Wei, Sarath Chandar, Soroush Vosoughi, Teruko Mitamura, and Eduard Hovy.  A Survey of Data Augmentation Approaches for NLP, December 2021.  URL http://arxiv.org/abs/2105.03075.  arXiv:2105.03075 [cs].
  * Li et al. [2022] Bohan Li, Yutai Hou, and Wanxiang Che.  Data Augmentation Approaches in Natural Language Processing: A Survey.  _AI Open_ , 3:71–90, 2022.  ISSN 26666510.  doi: 10.1016/j.aiopen.2022.03.001.  URL http://arxiv.org/abs/2110.01852.  arXiv:2110.01852 [cs].


# On a Boundary Updating Method for the Scalar Stefan Problem

Evangelos F. Magirou<EMAIL_ADDRESS>Paraskevas Vassalos<EMAIL_ADDRESS>Nikolaos Barakitis<EMAIL_ADDRESS>Department of Informatics, Athens
University of Economics and Business, Patission 76, 10434 Athens, Greece.

###### Abstract

We report on a general purpose method for the scalar Stefan problem inspired
by the standard boundary updating method used in several existence proofs. By
suitably modifying it we can solve numerically any kind of Stefan problem. We
present a theoretical justification of the method and several computational
results.

##  1 Introduction

In the numerical solution of one dimensional phase change (Stefan) problems
involving an infinite rod of ice at zero temperature one usually considers a
zero thickness liquid region on which the computation is initiated. A key
issue is how to initiate this computation; a common approach is to determine a
starting solution analytically and input the results to a numerical scheme
after a small, arbitrary time interval [4]. Thus a boundary immobilization
scheme [1] can be implemented starting from a definite initial temperature
distribution. A criticism to this approach is that a singularity is
artificially introduced in the physical equations. However [4] shows that by a
modification of this method self similar solutions for the entire region can
be determined, and demonstrate the validity of their method for several cases
well known in the literature.

In this work we report on the application of a boundary updating method
inspired by the one used in proving the existence of a solution to the phase
change problem as outlined in [1]. One considers a Stefan problem with given,
positive heat flux at the initial point. An operator is introduced modifying
phase boundaries and such that its fixed points are solutions to the Stefan
problem. The operator is essentially the integral of the Stefan condition. One
then shows that the operator is continuous in the appropriate norm and hence a
fixed point exists. It is also shown that the operator is a contraction for
small horizons and hence it potentially provides a method to numerically
identify the boundary. This operator approach is not applicable to the Stefan
problem whose boundary condition is specified by a temperature function at the
origin since a fundamental property is not valid in this case and a different
proof is given [2].

We have reexamined this method with a modification that improves its
contraction features, and in fact we show that if the original operator is
bounded, an appropriate modification gives a contraction. This relies on a
reversal type property, namely that if a function dominates another, their
transforms have an inverted domination property. This shows that starting with
a function dominated by the fixed point repeated applications of the operator
result in oscillations around the fixed point. Then reasoning as in the scalar
case a reduction in the amplitude of the oscillations is possible if instead
of the original operator we consider one that is a weighted average of the
identity and the operator. Applying this straightforward idea to standard
cases in the literature [1],[4] we were able to obtain the analytic without
using the extra analysis required therein. Also novel examples were solved
giving results consistent with the Stefan condition. These example were of
both boundary types. Furthermore we were able to solve problems with a Stefan
condition corresponding to inhomogeneous ice. We have some results indicating
why the method is successful but these rely on reasonable but unproven
assumptions.

The next section (Section 2) presents the Stefan problems with particular
attention paid to the variations in the boundary conditions and the
homogeneity mentioned earlier as well as some relevant results from the
literature, especially the operators used in the existence proof in [1].
Section 3 presents the main iterative methods introduced and their
justification. Section 4 includes the numerical schemes used. In Section 5 we
present some iterative methods of a different philosophy based on an
optimization approach as in our previous work [3], show how to implement them
and present an argument for their convergence. Conclusions and further work
plans are in the final Section 6.

##  2 Statement of the Free Boundary Problem

We follow [1] and [4] in formulating the one dimensional Stefan problem. The
space parameter is $x$ and the time one $t$. Consider the melting of ice,
initially occupying the half line $x\geq 0$ as a rod of infinitesimal
thickness which is then heated at $x=0$. The liquid region at time $t$ is from
zero to $s(t)$ and we denote it by $Q_{s}=\\{(x,t)|0<x<s(t)\\}$. We are
interested in the temperature distribution $U(x,t)$ in the liquid region
$Q_{s}$, and the solid - liquid interface or boundary $s(t)$. The interface is
not known and must be determined so that it satisfies a condition reflecting
the latent heat of the melting of ice. In the liquid phase $Q_{s}$ the
temperature $U(x,t)$ satisfies the heat equation

$\frac{\partial{U}}{\partial{t}}(x,t)=\frac{\partial^{2}{U}}{\partial{x^{2}}}(x,t),\qquad
0<x<s(t),\>t>0$ (1)

while in the solid phase $Q^{c}_{s}=\\{(x,t)|x\geq s(t)\\}$ we assume that the
temperature is everywhere at zero. One can consider the case where there
exists initially a liquid phase interval at zero temperature, in which case
the problem simplifies; we will assume no such interval. We thus have the
initial conditions

$\displaystyle s(0)=0,$ (2) $\displaystyle U(0,0)=0$ (3) $\displaystyle
U(s(t),t)=0$ (4)

On the liquid-solid boundary the heat of melting must equal the heat transfer
due to the temperature gradient. Thus if $L=L(x)$ is the latent heat per unit
volume, $k=k(x)$ the diffusivity coefficient of the liquid at position $x$
then $-kU_{x}(s(t),t)\delta t=L\delta s$; setting $\beta=L/k$ we obtain the
Stefan condition

$\beta(s(t))\frac{ds}{dt}=-\frac{\partial{U}}{\partial{x}}(s(t)t).$ (5)

In case $L,k$ depend on the position $x$, a situation that might occur if
there are impurities in the solid phase, there is a space dependence
$\beta=\beta(x)$. We will mostly work with a constant $\beta$ but our
numerical methods work for variable $\beta$’s.

We consider as in the literature two modes of heating, a Dirichlet and a
Neumann form and consider two types of condition at $x=0$

$\displaystyle U(0,t)=g(t),$ $\displaystyle Dirichlet\;boundary$ (6)
$\displaystyle\frac{\partial{U}}{\partial{x}}(0,t)=h(t)\geq 0\qquad$
$\displaystyle Neumann\;boundary$ (7)

As customary we assume $g$ to be nonnegative and $h$ to be positive.

Let $Q_{s,T}=\\{(x,t)|0<x<s(t),0<t<T\\}$ and $\overline{Q_{s,T}}$ be the
closure of $Q_{s,T}$ . A solution of the problem consisting of
(1),(2)-(4),(5),and either (6) or (7) in the horizon from zero to $T$ i.e.
$Q_{s,T}$ is a pair $(U,s)$ with $s\in C^{1}((0,T])\cap
C([0,T]),\;s(0)=0,\;s\geq 0,\;0\leq t\leq T,\;U\in C(\overline{Q_{s,T}})\cup
C^{2,1}(\overline{Q_{s,T}}),\;U_{x}\in C(\overline{Q_{s,T}}-\\{t=0\\})$. For
constant $\beta$ there are standard existence and uniqueness theorems for both
the Dirichlet and the Neumann condition as long as the heat flux $h$ is
positive and the temperature is nonnegative at the origin [1],[2], but the
proof of the Neumann case is more relevant to our work.

In the existence proofs the following construction - transformation proves
useful [1]: One considers a function $s$ serving as a candidate for the
interface (and hence $s(0)=0$) and then solves a heat equation problem without
the Stefan condition and $s$ as the interface. Namely one considers the
solution $U^{s}(x,t)$ of (1),(2)-(4) and either (6) or (7) from zero to $T$
i.e. in the domain $Q_{s,T}$. We will refer to the problem of finding a
solution for given $s$ and a Dirichlet condition (6) as the Fixed Boundary
Dirichlet problem. Finding a solution $U(x,t)\equiv U^{s}(x.t)$ for $s$ and a
Neumann condition (7) will be called the Fixed Boundary Neumann problem

One then modifies the boundary $s$ by transforming it through:

$\mathcal{R}(s)(t)=-\int_{0}^{t}U^{s}_{x}(s(z),z)dz\qquad 0\leq t\leq T.$ (8)

It is easily verified that a fixed point $s^{*}$ of (8) is a solution to the
Stefan problem. Now, as in [1], using the divergence theorem for the
identically zero function $U_{xx}-U_{t}$ on $Q_{s,T}$ we obtain

$\mathcal{R}(s)(t)=-\int_{0}^{t}U^{s}_{x}(0,z)dz-\int_{0}^{s(t)}U^{s}(x,t)dx\qquad
0\leq t\leq T$ (9)

For Neumann type problems the transform becomes

$\mathcal{R}(s)(t)=\int_{0}^{t}h(z)dz-\int_{0}^{s(t)}U^{s}(x,t)dx$ (10)

and it can be then shown that $\mathcal{R}$ is continuous in the appropriate
norm; by Schauder’s theorem stated in [1] it has a fixed point which is the
required solution. Moreover it is also shown in the same reference that it is
a contraction for a small enough horizon $T$ leading thus to a constructive
existence proof. This argument is not applicable for the Dirichlet problem (6)
since the expression (9) does not lead to (10) which is crucial for proving
continuity of $\mathcal{R}$. A different approach is used to show existence
for this case [2]. However we will show that $\mathcal{R}$ after its
modification by the divergence theorem (9) has additional properties that can
serve as a basis for a general purpose iterative algorithm, as we show next.

##  3 A modified iterative algorithm for free boundary problems

A very useful property of $\mathcal{R}$ is stated as a n exercise in [1]. We
state and prove it next.

######  Lemma 3.1.

(Reversal lemma)

Consider the Fixed Boundary Neumann Problem as defined in the previous section
(Namely the solution $U^{s}$ of (1),(2)-(4) and the Neumann condition (7)) and
assume that it has a solution for any smooth $s$ starting at the origin. If
$s_{1},s_{2}$ are boundary functions such that $s_{1}(t)\leq
s_{2}(t),\;t\in[0,T]$ then $\mathcal{R}(s_{1})(t)\geq\mathcal{R}(s_{2})(t)$.

###### Proof.

We assumed the existence of $U^{s}$. If $h>0$ then we will first show that
$U^{s}$ is everywhere nonnegative. Since $U^{s}$ is zero on the boundary $s$
and it attains its extremes on the parabolic boundary, the minimum must be at
some $(x,t)=(0,t^{*})$. If the minimum is negative then $U^{s}(0,t^{*})<0$.
But since $U_{x}^{s}(0,t^{*})=-h(t^{*})<0$ the minimum can not occur on the
parabolic boundary and thus $U^{s}$ is nonnegative on $Q_{s,T}$.

Consider now the solutions of the above problem in the boundaries
$s_{1},s_{2}$$U^{s_{1},\epsilon}$ and $U^{s_{2}}$ respectively with Neumann
conditions $-U_{x}^{s_{1},\epsilon}(0,t)=h(t)+\epsilon$
,$-U_{x}^{s_{2}}(0,t)=h(t)$. Also consider their difference
$\Delta^{\epsilon}=U^{s_{1},\epsilon}-U^{s_{2}}$. On $s^{1}$,
$\Delta^{\epsilon}\geq 0$ and if its minimum is negative it occurs on a zero
value of $x$. But this is impossible since
$\Delta^{\epsilon}_{x}(0,t)=-\epsilon<0$ and thus $\Delta^{\epsilon}\geq 0$.
As $\epsilon\rightarrow 0$ and assuming continuity with $\epsilon$ we obtain
$\Delta^{0}=U^{s_{1},0}-U^{s_{2}}\geq 0$ everywhere. Then using (10) we have

$\displaystyle\mathcal{R}(s_{1})(t)-\mathcal{R}(s_{2})(t)=$
$\displaystyle\int_{0}^{s_{2}(t)}U^{s_{2}}(x,t)dx-\int_{0}^{s_{1}(t)}U^{s_{1}}(x,t)dx=$
$\displaystyle\int_{0}^{s_{1}(t)}[U^{s_{2}}(x,t)-U^{s_{1}}(x,t)]dx+\int_{s_{1}(t)}^{s_{2}(t)}U^{s_{2}}(x,t)dx.$
(11)

Since both terms are nonnegative we have
$\mathcal{R}(s_{1})\geq-\mathcal{R}(s_{2})$. ∎

Figure 1: Illustrating the modified boundary transform

This reversal lemma 3.1 is suggestive of a useful property in one dimensional
fixed point algorithms - see Diagram 1 \- where we are interested in computing
the fixed point of a scalar function $f$ with a large, negative slope. The
iteration $x_{n+1}=f(x_{n})$ is diverging, but the function $g(x)=(f(x)+x)/2$
is of smaller absolute value of slope and thus has a better chance of
converging to the fixed point through the iteration
$\overline{x}_{n+1}=g(\overline{x}_{n})$.

We thus introduce the operators $\mathcal{P}^{\alpha}(s)$ with
$\alpha\in[0,1]$ as

$\displaystyle\mathcal{P}^{\alpha}(s)(t)=\alpha\mathcal{R}(s)(t)+(1-\alpha)s(t)$
(12)

In most of our implementations $\alpha$ will be taken as $1/2$ but different
values might be necessary for convergence. Note that $s^{*}$ is a fixed point
of both $\mathcal{P}$ and $\mathcal{R}$. An indicative result for $\alpha=1/2$
is as follows:

######  Proposition 3.2.

Let $s^{*}$ be the solution of the Stephan problem with the Neumann condition
and let $s\leq s^{*}$ for all $t$. Then for all $t$

$\displaystyle
s-s^{*}\leq\frac{s-s^{*}}{2}\leq\mathcal{P}^{1/2}(s)-s^{*}\leq\frac{\mathcal{R}(s)-s^{*}}{2}\leq\mathcal{R}(s)-s^{*}.$
(13)

If $s\geq s^{*}$ for all $t$

$\displaystyle s-s^{*}\geq\frac{s-s^{*}}{2}\leq
s^{*}-\mathcal{P}^{1/2}(s)\geq\frac{\mathcal{R}(s)-s^{*}}{2}\geq\mathcal{R}(s)-s^{*}.$
(14)

###### Proof.

If $s\leq s^{*}$

$\displaystyle\mathcal{P}^{1/2}(s)-s^{*}=\frac{1}{2}(\mathcal{R}(s)+s)-\frac{1}{2}(\mathcal{R}(s^{*})+s^{*})=\frac{1}{2}(\mathcal{R}(s)-s^{*})+\frac{1}{2}(s-s^{*})\leq\frac{1}{2}(\mathcal{R}(s)-s^{*})$
(15)

and

$\displaystyle\mathcal{P}^{1/2}(s)-s^{*}=\frac{1}{2}(\mathcal{R}(s)+s)-s^{*}=\frac{1}{2}(\mathcal{R}(s^{*})-s^{*})+\frac{1}{2}(s-s^{*})\geq\frac{1}{2}(s-s^{*})$
(16)

A similar proof in case $s>s^{*}$. ∎

A similar result is valid if $s$ dominates the equilibrium $s^{*}$. The proof
is in a sense a special case of the next proposition modulo a boundedness
assumption on the operator $\mathcal{R}$. The proposition shows that our
modified operator $\mathcal{P}$ has better contraction properties than
$\mathcal{R}$. We generalize the proposition in our next result. We use the
norm $\|s_{1}-s_{2}\|\equiv\min_{t}|s_{1}(t)-s_{2}(t)|$ for $t\leq T$.

######  Proposition 3.3.

Assume $s_{1}\leq s_{2}$ and that $\mathcal{R}$ satisfies the reversal
property of Lemma 3.1, while
$\mathcal{P}^{\alpha}(s)(t)=\alpha\mathcal{R}(s)(t)+(1-\alpha)s(t)$ as in
(12). Assuming that $\mathcal{R}$ is bounded, i.e.
$\|\mathcal{R}(s_{1})-\mathcal{R}(s_{2})\|\leq\gamma\|s_{1}-s_{2}\|$ and
$\gamma$ is finite, then

$\|\mathcal{P}^{\frac{1}{\gamma+1}}(s_{1})-\mathcal{P}^{\frac{1}{\gamma+1}}(s_{2})\|\leq\frac{\gamma}{\gamma+1}\|s_{1}-s_{2}\|\leq\|s_{1}-s_{2}\|$
(17)

In terms of the operators $\mathcal{P}^{\alpha}$ we have
$\alpha=\frac{1}{\gamma+1}$.

###### Proof.

Let $s_{1}\leq s_{2}$ all $t$. Then for all $t$

$(1-\alpha)(s_{1}-s_{2})\leq\mathcal{P}^{\alpha}(s_{1})-\mathcal{P}^{\alpha}(s_{2})=\alpha(\mathcal{R}(s_{1})-\mathcal{R}(s_{2}))+(1-\alpha)(s_{1}-s_{2})\leq\alpha(\mathcal{R}(s_{1})-\mathcal{R}(s_{2}))$
(18)

since $s_{1}\leq s_{2},\;\mathcal{R}(s_{1})\geq\mathcal{R}(s_{2})$.

Now if $\mathcal{P}^{\alpha}(s_{1})-\mathcal{P}^{\alpha}(s_{2})\geq 0$ at some
$t$ then

$|\mathcal{P}^{\alpha}(s_{1})(t)-\mathcal{P}^{\alpha}(s_{2})(t)|\leq\alpha|\mathcal{R}(s_{1})(t)-\mathcal{R}(s_{2})(t)|\leq\alpha\max_{t}|\mathcal{R}(s_{1})(t)-\mathcal{R}(s_{2})(t)|=\alpha\|\mathcal{R}(s_{1})-\mathcal{R}(s_{2})\|\leq\alpha\gamma\|\mathcal{R}(s_{1})-\mathcal{R}(s_{2})\|$

and otherwise if $\mathcal{P}^{\alpha}(s_{1})-\mathcal{P}^{\alpha}(s_{2})\geq
0$ then

$|\mathcal{P}^{\alpha}(s_{1})(t)-\mathcal{P}^{\alpha}(s_{2})(t)|\leq(1-\alpha)|s_{1}(t)-s_{2}(t)|\leq(1-\alpha)\max_{t}|s_{1}(t)-s_{2}(t)|=(1-\alpha)\|s_{1}-s_{2}\|$

Hence

$|\mathcal{P}(s_{1})(t)-\mathcal{P}(s_{2})(t)|\leq\max(\alpha\gamma\|s_{1}-s_{2}\|,(1-\alpha)\|s_{1}-s_{2}\|)$

Since the above relation is true for all $t$ we have

$\max_{t}|\mathcal{P}(s_{1})(t)-\mathcal{P}(s_{2})(t)|\equiv\|\mathcal{P}(s_{1})-\mathcal{P}(s_{2})\|\leq\max(\alpha\gamma,1-\alpha)\|s_{1}-s_{2}\|$

and finally

$\|\mathcal{P}(s_{1})-\mathcal{P}(s_{2})\|\leq\min_{\alpha}\max(\alpha\gamma,1-\alpha)\|s_{1}-s_{2}\|=\frac{\gamma}{\gamma+1}\|s_{1}-s_{2}\|$
(19)

The min-max relation in the last equality occurs when the two terms
$\alpha\gamma,1-\alpha$ are equal and hence $\alpha=\frac{1}{1+\gamma}$. The
above inequality is symmetric in $s_{1},s_{2}$ so it is valid whenever one
boundary dominates the other. ∎

In the existence proof for the Neumann version in [1] it is shown that the
$\mathcal{R}$ operator is indeed bounded so the $\mathcal{P}$ operators can be
used as contraction operators to locate the fixed point. We next show that
even in the Dirichlet problem the $\mathcal{R}$ operator has the reversal
property, so if one can show that it is bounded this provides a justification
of the use of $\mathcal{P}$ to locate the fixed point.

######  Lemma 3.4.

Consider the fixed boundary Dirichlet problem with $U^{s}(0,t)=g(t)$, $g$
nonnegative and nondecreasing. Then for a given boundary $s$ the solution
$U^{s}$ satisfies $U^{s}_{x}(0,t)\leq 0$.

###### Proof.

Consider the problem for $Q_{s,T}$ i.e. $t\in[0,T]$.The maximum of $U^{s}$ is
on the parabolic boundary and since $U^{s}(s(t),t)=0$ the maximum is at
$x=0,\;t=T$ where $U^{s}(0,T)=g(T)$ given that $g$ is nondecreasing. Hence
$U^{s}_{x}(0,T)\leq 0$ for otherwise the maximum would not be on the parabolic
boundary. Since $g$ is nondecreasing the argument can be repeated for any
value of $T$. ∎

We will not use the above lemma, but it is interesting in its own right. It is
not valid for $g$’s that have both increasing and decreasing regions.

######  Lemma 3.5.

For the Fixed Boundary Dirichlet problems with boundaries $s_{1}\leq s_{2}$
(i.e. for which $U^{s_{1}}(0,t)=U^{s_{2}}(0,t)=g(t)$) we have
$U^{s_{1}}_{x}(0,t)\leq U^{s_{2}}_{x}(0,t)$.

###### Proof.

Consider $\Delta U(t)=U^{s_{2}}(x,t)-U^{s_{1}}(x,t)$ up to $s_{1}$, which
vanishes for $x=0$ and is nonnegative on $s_{1}$. The minimum of $\Delta U$ is
on the parabolic boundary and in particular for some zero $x$ and some $t$.
But then $\Delta U_{x}(0,t)$ must be nonnegative for otherwise there is a
minimum in the parabolic interior. Therefore $\Delta
U_{x}(0,t)=U^{s_{2}}_{x}(0,t)-U^{s_{2}}_{x}(0,t)\geq 0$ as required. ∎

The main result for Dirichlet problems is the following:

######  Proposition 3.6.

The operator $\mathcal{R}$ as defined in (8) for the Fixed Boundary Dirichlet
problem with nonnegative boundary condition $U(0,t)=g(t)\geq 0$ has the
reversal property of Lemma 3.1, i.e. if $s_{1},s_{2}$ are boundary functions
and $s_{1}(t)\leq s_{2}(t),\;t\in[0,T]$ then
$\mathcal{R}(s_{1})(t)\geq\mathcal{R}(s_{2})(t)$.

###### Proof.

Consider the boundary functions (smooth and starting at the origin)
$s_{1},s_{2}$ and such that $s_{1}(t)\leq s_{2}(t),\;t\in[0,T]$ and the
corresponding solutions $U^{s_{1}}(x,t),U^{s_{2}}(x,t)$ on for $x\leq
s_{1}(t)$. On $s_{1}$ we have $U^{s_{2}}(s_{1}(r),t)-U^{s_{1}}(s_{1}(r),t)\geq
0$ and at zero $U^{s_{2}}(0,t)-U^{s_{1}}(0,t)=g(t)-g(t)=0$. Hence by the
minimum principle $U^{s_{2}}(x,t)-U^{s_{1}}(x,t)\geq 0$ for $x\leq s_{1}(t)$.
We also have by lemma 3.5 $U^{s_{1}}_{x}(0,t)\leq U^{s_{2}}_{x}(0,t)$. Hence
using expression (9) for $\mathcal{R}$ we have

$\mathcal{R}(s_{2})(t)-\mathcal{R}(s_{1})(t)=-\int_{0}^{t}[U^{s_{2}}_{x}(0,\tau)-U^{s_{1}}_{x}(0,\tau)]d\tau-\int_{0}^{s_{2}(t)}U^{s_{2}}(x,t)dx+\int_{0}^{s_{1}(t)}U^{s_{1}}_{x}(x,t)dx=$
(20)

The first integral is non negative by the derivatives’ property at zero. The
last two integrals are

$-\int_{0}^{s_{2}(t)}U^{s_{2}}(x,t)dx+\int_{0}^{s_{1}(t)}U^{s_{1}}(x,t)dx=\int_{0}^{s_{1}(t)}[U^{s_{1}}(x,t)-U^{s_{2}}(x,t)]dx-\int_{s_{1}(t)}^{s_{2}(t)}U^{s_{2}}(x,t)dx\geq
0$ (21)

Hence $\mathcal{R}$ has the desired property ∎

To some extent a similar treatment is possible for the nonhomegeneous problem
where the Stefan condition is $-U_{x}(s(t),t))=\beta(s(t))\dot{s}(t)$. Then we
modify the operator $\mathcal{R}$ as follows (to be completed…)

###  3.1 Iterative algorithm based on the Boundary Immobilization Technique

Set,

  * T=final time

  * dx=spatial step

  * dt=time step

  * h_function=h(t)

  * t_vec=0:td:T

  * h_vec=h_function(t_vec)

  * s_vec

  * error=1

  * counter = 0

such that $1/dx$, $T/dt$ be integer and $s\\_vec$ be the vector of boundary of
equal length with $t\\_vec$, initially arbitrary.

  * while error $\geq$ tol & counter $\leq$ upCounterBound

    * F=temperatureDistribution(T,dx,dt,s,h)

    * for i=1:length(s)

      * s1(i) = -trapz(h_vec(1:i))dt - trapz(F(:,i))s(i)dx

    * end for

    * error = norm(abs(s1-s),inf)

    * counter = counter+1

    * s=s1

  * end while

###  3.2 Temperature distribution for given T,dx,dt,s,h

We will use the Crank-Nicolson scheme to implement the function
temperatureDistribution(T,dx,dt,s,h) that returns the temperature distribution
for given T,dx,dt,s,h.

##  4 Numerical schemes and results

###  4.1 Boundary immobilization technique-BIM

As the boundary varies in time, in order to keep the number of spatial nodes
fixed and any finite difference scheme can be applied, either a changing
spatial step, either a coordinate transformation technique must be used.We
here use the Boundary Immobilization technique, that fixes the moving boundary
by using a fixed co-ordinate system in space. So, we set

$\displaystyle\xi=\frac{x}{s(t)},\>T=F(\xi,t),$ (22)

so that the equations (1)-(7) become

$\displaystyle\frac{\partial^{2}{F}}{\partial{\xi^{2}}}=s^{2}\frac{\partial{F}}{\partial{t}}-s\xi\frac{ds}{dt}\frac{\partial{F}}{\partial{\xi}}$
(23) $\displaystyle s(0)=0,$ (24) $\displaystyle F(\xi,0)=0,$ (25)
$\displaystyle\beta\frac{ds}{dt}=-\frac{\partial{F}}{\partial{\xi}}|_{\xi=1}$
(26)

subject to

$\displaystyle F(0,t)=g(t),\>or$ (27)
$\displaystyle\frac{\partial{F}}{\partial{\xi}}|_{\xi=0}=s(t)h(t)=\hat{h}(t)$
(28)

Let for symplicity $s^{2}=z$, that is $s\frac{ds}{dt}=\frac{dz}{2dt}$, and

$\displaystyle N=\frac{1}{\Delta\xi},\>\>\xi_{i}=i\Delta\xi\>\>i=0...N$ (29)
$\displaystyle M=\frac{\mathbb{T}}{\Delta t},\>\>t^{n}=n\Delta t\>\>n=0...M$
(30)

where $\mathbb{T}$ is the final time.

Then, using the Crank-Nicolson scheme involving a central difference at time
$t^{n-\frac{1}{2}}$ and a second order central difference for space derivative
for the discretization of 23, we have

$\displaystyle\frac{1}{2}\left(\frac{F_{i+1}^{n}-2F_{i}^{n}+F_{i-1}^{n}}{\Delta\xi^{2}}\right)+\frac{1}{2}\left(\frac{F_{i+1}^{n-1}-2F_{i}^{n-1}+F_{i-1}^{n-1}}{\Delta\xi^{2}}\right)=$
$\displaystyle z^{n-\frac{1}{2}}\left(\frac{F_{i}^{n}-F_{i}^{n-1}}{\Delta
t}\right)$
$\displaystyle-\frac{\xi_{i}}{2}\left(\frac{dz}{dt}\right)^{n}\left[\frac{1}{2}\left(\frac{F_{i+1}^{n}-F_{i-1}^{n}}{2\Delta\xi}\right)+\frac{1}{2}\left(\frac{F_{i+1}^{n-1}-F_{i-1}^{n-1}}{2\Delta\xi}\right)\right]\Rightarrow$
$\displaystyle(F_{i+1}^{n}-2F_{i}^{n}+F_{i-1}^{n})+(F_{i+1}^{n-1}-F_{i}^{n-1}+F_{i-1}^{n-1})=$
$\displaystyle z^{n-\frac{1}{2}}\frac{2\Delta\xi^{2}}{\Delta
t}(F_{i}^{n}-F_{i}^{n-1})$
$\displaystyle-\frac{\xi_{i}}{4}\left(\frac{dz}{dt}\right)^{n}\Delta\xi[(F_{i+1}^{n}-F_{i-1}^{n})+(F_{i+1}^{n-1}-F_{i-1}^{n-1})]$

where $z^{n}=z(d\Delta t)$, $z^{n-\frac{1}{2}}=\frac{z^{n}+z^{n-1}}{2}$ and
$\left(\frac{dz}{dt}\right)^{n}=\frac{z^{n}-z^{n-1}}{\Delta t}$.
Setting $\rho^{n}=z^{n-\frac{1}{2}}\frac{2\Delta\xi^{2}}{\Delta t}$ and
$\sigma_{i}^{n}=\frac{\xi_{i}}{4}\left(\frac{dz}{dt}\right)^{n}\Delta\xi$ the
above equation becomes,

$\displaystyle(F_{i+1}^{n}-2F_{i}^{n}+F_{i-1}^{n})+(F_{i+1}^{n-1}-2F_{i}^{n-1}+F_{i-1}^{n-1})=\rho^{n}(F_{i}^{n}-F_{i}^{n-1})-\sigma_{i}^{n}[(F_{i+1}^{n}-F_{i-1}^{n})+(F_{i+1}^{n-1}-F_{i-1}^{n-1})]\Rightarrow$
$\displaystyle(1-\sigma_{i}^{n})F_{i-1}^{n}-(2+\rho^{n})F_{i}^{n}+(1+\sigma_{i}^{n})F_{i+1}^{n}=-(1-\sigma_{i}^{n})F_{i-1}^{n-1}+(2-\rho^{n})F_{i}^{n-1}-(1+\sigma_{i}^{n})F_{i+1}^{n-1}$
(31)

The above equation is valid for $i=1...N-1$, while for $i=0$, taking into
account that $\sigma_{i}^{n}=0$ and replacing the term $F_{-1}^{n}$ using the
relationship $\frac{F_{1}^{n}-F_{-1}^{n}}{2\Delta\xi}=h^{n}s^{n}\Rightarrow
F_{-1}^{n}=F_{1}^{n}-2h^{n}s^{n}\Delta\xi$, whith $s^{n}=s(n\Delta t)$,
$h^{n}=h(n\Delta t)$.So the equation becomes

$\displaystyle-(2+\rho^{n})F_{0}^{n}+2F_{1}^{n}=(2-\rho^{n})F_{0}^{n-1}-2F_{1}^{n-1}+4\Delta\xi\frac{s^{n}h^{n}+s^{n-1}h^{n-1}}{2}$
(32)

Since $F(s(t))=0$, the equation for $i=N$ is $F_{N}^{n}=F_{N}^{n-1}=0$ or

$\displaystyle-(2+\rho^{n})F_{N}^{n}=(2-\rho^{n})F_{N}^{n-1}=0$ (33)

Let now $R^{n}$, $L^{n}$ $\in\>\mathbb{R}^{(N+1)x(N+1)}$, defined as,

$\displaystyle L^{n}=\left[\begin{array}[]{ccccccccc}-(2+\rho^{n})&2\\\
1-\sigma_{1}^{n}&-(2+\rho^{n})&1+\sigma_{1}^{n}\\\
&1-\sigma_{2}^{n}&-(2+\rho^{n})&1+\sigma_{2}^{n}\\\ &&\ddots&\ddots&\ddots\\\
&&&\ddots&\ddots&\ddots\\\
&&&1-\sigma_{N-1}^{n}&-(2+\rho^{n})&1+\sigma_{N-1}^{n}\\\
&&&&0&-(2+\rho^{n})\\\ \end{array}\right],$ (41)

$\displaystyle R^{n}=\left[\begin{array}[]{ccccccccc}(2-\rho^{n})&-2&\\\
-1+\sigma_{1}^{n}&(2-\rho^{n})&-1-\sigma_{1}^{n}\\\
&-1+\sigma_{2}^{n}&(2-\rho^{n})&-1-\sigma_{2}^{n}\\\ &&\ddots&\ddots&\ddots\\\
&&&\ddots&\ddots&\ddots\\\
&&&-1+\sigma_{N-1}^{n}&(2-\rho^{n})&-1-\sigma_{N-1}^{n}\\\
&&&&0&(2-\rho^{n})\\\ \end{array}\right],$ (49)

and $E^{n}\>\in\mathbb{R}^{N+1}$ defined as
$E^{n}=[4\Delta\xi\frac{s^{n}h^{n}+s^{n-1}h^{n-1}}{2},0,\dots,0]^{T}$
Now, given the temperature distribution
$f^{n-1}=[F_{0}^{n-1},F_{1}^{n-1},\dots,F_{N}^{n-1}]^{T}$, the equations
(32)-(33) can be written in matrix form

$\displaystyle L^{n}f^{n}=R^{n}F^{n-1}+E^{n}\Rightarrow
f^{n}=(L^{n})^{-1}(R^{n}F^{n-1}+E^{n})$ (50)

for $n=1\dots M$ and $f^{0}=[0,0,\dots,0]^{T}$

####  4.1.1 Implementation

temperatureDistribution(T,dx,dt,s,h)

  * N = $\frac{1}{dx}$ \+ 1

  * M = $\frac{1}{dx}$ \+ 1

  * F = zeros(N,M)

  * for n=1:M

    * Define $R^{n}$

    * Define $L^{n}$

    * Define $E^{n}$

    * $F(:,n)=(R^{n})^{-1}(L^{n}F(:,n-1)+E^{n})$

  * end for

  * return F

###  4.2 Numerical Results

We consider three examples taken from [4] with the following boundary
conditions at $x=0$.

${}(i)T=e^{t}-1,\quad(ii)\frac{\partial{T}}{\partial{x}}=-e^{t},\quad(iii)T=1-\epsilon\sin(\omega
t),$

where the parameters $\epsilon$ and $\omega$ in $(iii)$ represent the
amplitude and the thermal oscillation. The solution for the first two boundary
conditions is known and it is

$T=e^{t-x}-1,\quad s(t)=t$

for both of them, provided $\beta=1$. The solution for boundary condition
$(iii)$ is unknown. For the two first examples we compare the approximate
solution found using the iterative algorithm with exact solution for both the
$s(t)$ and temperature distribution at final time, whilst for the third
example we compare the derivative of boundary $s$ with the $\frac{\partial
F}{\partial x}$ at $x=s(t)$ as evidence that the Stefan condition at the
boundary holds for approximate solution.

Following the [4] and [5] we define

$\Delta\xi_{k}=2^{-k}\Delta\xi_{0},\quad\Delta\xi_{0}=0.1$
$\xi_{i,k}=i\Delta\xi_{k},\quad i=0,1,\dots\frac{1}{\Delta\xi_{k}}.$

For the examples that the analytical solution is known $T$ we define the error
at time $n$ as follows

$E_{k}^{n}=\left(\Delta\xi_{k}\sum_{i=0}^{\frac{1}{\Delta\xi_{k}}}(F(\xi_{i,k},t^{n})-T(s^{n}\xi_{i,k},t^{n}))^{2}\right)^{1/2},$

$F$ being the numerical solution and $T$ being the exact. The order of
accuracy of the solution is defined as the number

$p=\frac{ln(E_{k}^{n}/E_{k+1}^{n})}{ln(\Delta\xi_{k}\ \Delta\xi_{k+1})}$

if that number exists.

| Boundary condition (i) | Boundary condition (i)
---|---|---
$\Delta\xi$ | $E^{n}$ | $p$ | $E^{n}$ | $p$
$1/10$ | $2.21\times 10^{-3}$ |  | $7.03\times 10^{-4}$ |
$1/20$ | $5.35\times 10^{-4}$ | $2.050$ | $1.72\times 10^{-4}$ | $2.024$
$1/40$ | $1.31\times 10^{-4}$ | $2.029$ | $4.29\times 10^{-5}$ | $2.010$
$1/80$ | $3.22\times 10^{-5}$ | $2.021$ | $1.06\times 10^{-5}$ | $2.004$
$1/160$ | $7.84\times 10^{-6}$ | $2.041$ | $2.66\times 10^{-6}$ | $2.002$
Table 1: The error of the numerical solution of $F$, fixed at time $t^{n}=1$
and the order of accuracy for boundary condition $(i)$ and $(ii)$.

Figure 2: The error versus iteration for the boundary found using the
iterative method with boundary condition $(i)$. The error is located near the
start.

Figure 3: The error versus iteration for the boundary found using the
iterative method with boundary condition $(ii)$. The approximation is good at
all time intervall.

Figure 4 confirmes the oscillating nature of the succesive boundaries. For
this example we have removed the average rule and the new boundary have been
calculated by straight use of the rule (10).

Figure 4: Detail from three successive boundaries for example 2. The
boundaries oscillate around and converge to the exact.

##  5 Alternative Iterative Methods

Given a boundary for the Stefan problem and the corresponding solution
$s,U^{s}$ one might try to improve on the boundary by considering a direct
modification that reduces the discrepancy in the Stefan condition
$U^{s}_{x}(s(t)t)=-\dot{s}(t)$. A possible measure the discrepancy is a
quadratic one

$D_{1}(s)=\int_{0}^{T}(U^{s}_{x}(s(t),t)+\dot{s}(t))^{2}dt$ (51)

One can then try to find an alternative boundary $\hat{s}$ on which this
discrepancy is reduced, namely set $\hat{s}=y$ where $y$ is the solution of
the following calculus of variations problem in $y$

$\inf_{y}\int_{0}^{T}(U^{s}_{x}(y,t)+\dot{y}(t))^{2}dt\quad
y(0)=0\;y(T)\;free$ (52)

which however can be solved by inspection.

An alternative formulation is to use the discrepancy measure

$D_{2}(s)=\int_{0}^{T}[(U^{s}_{x}(s(t),t)+\dot{s}(t))^{2}+U^{s}(s(t),t)^{2}]dt$
(53)

leading to the calculus of variations problem

$\inf_{y}\int_{0}^{T}[(U^{s}_{x}(y,t)+y^{\prime}(t))^{2}+U^{s}(y,t)^{2}]dt\quad
y(0)=0\quad y(T)\;free,$ (54)

In this formulation we are certain that the updated boundary $\hat{s}=y$ has
an overall penalty inferior to
$\int_{0}^{T}(U^{s}_{x}(s(t),t)+\dot{s}(t))^{2}dt$ because
$\int_{0}^{T}(U^{s}_{x}(s(t),t)+\dot{s}(t))^{2}dt=\int_{0}^{T}[(U^{s}_{x}(s(t),t)+\dot{s}(t))^{2}+U^{s}(s(t),t)^{2}]dt$
since $U^{s}(s(t),t)=0$.

The Euler Lagrange conditions for the first problem (52) is

$\frac{d^{2}y}{dt^{2}}=U^{s}_{xx}(y,t)U^{s}_{x}(y,t)-U^{s}_{x,t}(y,t)\qquad
y(0)=0,y^{\prime}(T)=U^{s}_{x}(y(T),T)$ (55)

while for (54) is the slightly more complicated:

$\frac{d^{2}y}{dt^{2}}=U^{s}_{xx}(y,t)U^{s}_{x}(y,t)-U^{s}_{x,t}(y,t)+U^{s}_{x}(y,t)U(y,t)\qquad
y(0)=0,y^{\prime}(T)=U^{s}_{x}(y(T),T)$ (56)

It can be easily shown that (55) leads to the obvious condition

$\frac{dy}{dt}=-U^{s}_{x}(y,t)\qquad y(0)=0,y(T)\;free.$ (57)

which requires to find a path $y$ on which $U^{s}$ satisfies the Stefan
condition; however on this path $U^{s}$ does not necessarily vanish, but we
hopefully get a boundary closer to the Stefan solution. The path satisfying
(56) presents a compromise between the goals of the derivative condition and
zero boundary temperature.

Solving even (55) is complicated by the fact that it requires the values of
$U^{s}$ for $x\geq s(t)$ which is an numerically unstable problem. A similar
situation was present in the authors’ previous work in the context of locating
the exercise boundary of an American typo option by improving on a current
exercise boundary [3]. We developed there an alternative approach sidestepping
the need to solve outside the $Q_{s,T}$. Solving (56) in addition introduces a
two point boundary value problem on the numerically generated function $U^{s}$
that must also be known outside $Q_{s,T}$. We have not worked on either the
convergence or the numerical properties of those improvements, but they are in
the spirit of the usually efficient (super-linear) policy iteration algorithms
analyzed in [3] and it would not be a surprise if they prove more efficient
than the $\mathcal{P}$ operator ones that are fixed point algorithms with
geometric convergence.

As in our previous work, we consider a linearized improvement that does not
require $U^{s}$ except on the boundary $s$ and could be of use in an
alternative method. For a fixed boundary problem with a solution $U^{s}$ on
$s$ consider a modification $\hat{s}=s+\xi$ with $\xi$ small. The first order
approximations of interest are $U^{s}_{x}(s+\xi,t)\approxeq
U^{s}_{x}(s,t)+U^{s}_{xx}(s,t)\xi,\quad U^{s}(s+\xi,t)\approxeq
U^{s}(s,t)+U^{s}_{x}(s,t)\xi=U^{s}_{x}(s,t)\xi$. Then we can write the first
order analog of (52) as

$\inf_{\xi}\int_{0}^{T}(\dot{s}+\dot{\xi}+U^{s}_{x}(s,t)+U^{s}_{xx}(s,t)\xi)^{2}dt\quad\xi(0)=0\;\xi(T)\;free$
(58)

The solution $\xi$ satisfies the obvious differential equation (equivalent to
the Euler Lagrange conditions)

$\xi^{\prime\prime}+\beta(t)\xi+\alpha(t)=0\quad\xi(0),\xi(T)\;free$ (59)

The coefficients are given in terms of $U^{s}(s(t),t)$ and its derivatives, in
particular
$\beta(t)=U^{s}_{xx}(s(t),t),\;\alpha(t)=\dot{s}+U^{s}_{x}(s(t),t)$. The
boundary update could be of the form $\hat{s}=s+\epsilon\xi$ with $\epsilon$
in [0,1] and we can show that for small enough $\epsilon$ we indeed get an
improvement. Consider the discrepancy measure $D_{2}$ in (53) for
$s+\epsilon\xi$

$\int_{0}^{T}[(U^{s}_{x}(s+\epsilon\xi,t)+\dot{s}+\epsilon\dot{\xi})^{2}+U^{s}(s+\epsilon\xi,t)^{2}]dt$

Using (59) we have

$\dot{s}+\epsilon\dot{\xi}+U^{s}_{x}(s+\epsilon\xi,t)=\dot{s}+\epsilon(-\dot{s}-U^{s}_{x}(s,t)-U^{s}_{xx}(s,t)\xi)+U^{s}_{x}(s,t)+U^{s}_{xx}(s,t)\epsilon\xi+o(\epsilon^{2})=(1-\epsilon)(\dot{s}+U^{s}_{x}(s,t))+o(\epsilon^{2})$

and also

$U^{s}(s+\epsilon\xi,t)=U^{s}(s,t)+U^{s}_{x}(s,t)\epsilon\xi+o(\epsilon^{2})=U^{s}_{x}(s,t)\epsilon\xi+o(\epsilon^{2}).$

Hence the quadratic discrepancy for $s+\epsilon\xi$ is

$(1-\epsilon)^{2}\int_{0}^{T}[(\dot{s}+U^{s}_{x}(s,t))^{2}+\epsilon^{2}\xi^{2}U^{s}_{x}(s,t)+o(\epsilon^{4})]dt=(1-2\epsilon)\int_{0}^{T}(\dot{s}+U^{s}_{x}(s,t))^{2}dt+o(\epsilon^{2})$
(60)

This shows that the discrepancy measure $D_{2}$ is reduced multiplicatively,
and thus this boundary updating algorithm will succeed if properly applied. A
similar treatment can be carried out for (54).

##  6 Conclusions

Concerning the numerical results presented in 4.2 we observe a consistent high
speed convergence, not entirely justified by our rather conservative results.
It would be of some interest to extend our theoretical results to explain this
fortuitous situation.

## References

## References

  * [1] D. Andreucci.  Lecture notes on the Stefan problem, 2003.
  * [2] A. Friedman.  Free boundary problems for parabolic equations I. Melting of solids.  Journal of Mathematics and Mechanics, (4):499–517.
  * [3] E. F. Magirou, P. Vassalos, and N. Barakitis. A policy iteration algorithm for the american put option and free boundary control problems.  J. Comput. Appl. Math., 373:112544, 2020.
  * [4] S.L. Mitchell and M. Vynnycky.  Finite-difference with increased accuracy and correct initialization for one-dimensional Stefan problems.  Appl. Math. Comput, 215:1609–1621, 2009\.
  * [5] S. Savović and J. Caldwell.  Finite difference solution of one-dimensional stefan problem with periodic boundary conditions.  Int. J. of Heat and Mass Transfer, 46(15):2911–2916, 2003.