%
% This is LaTeX, not plain TeX.
%

\input epsf

%
% Note: The graphics included in this article will not display properly
% on other platforms than NeXT, unless dvips(1) is used to convert the
% dvi output to postscript first.  (My experience.)
%

\def\picture#1#2#3{\noindent\epsfxsize=#1in\epsfysize=#1in \hfil\vbox{
     \hbox to \hsize{\hfil\epsffile{#2}\hfil}
     \hbox to \hsize{\hfil#3\hfil}}\bigskip}

\documentstyle{article}
\title
      {\large Square Conductor Networks\\
      of the Solar Cross Type}
\author{Konrad Schr\char 28 der}
\date{14 August 1992}
\begin{document}
\maketitle

\begin{abstract}
     \noindent Methods for recovering the conductances of solar cross
     networks from their Dirichlet-to-Neumann maps are discussed.  Three
     algorithms are given for the solution of this problem.
\end{abstract}

\section
       {Terminology: what is a $\lambda$-matrix?}

As in [2], consider a network $\Omega_\beta$ of conductors in
square-lattice form (Figures 1 and 2).

     \noindent \epsfxsize=2in
     \hbox{
          \vbox
               {\hbox to 2.25in{\hfil \epsffile{general.eps}\hfil}
               \hbox to 2.25in{\hfil Figure 1: general, $\Omega_\beta$\hfil}}
          \hfil
          \vbox
               {\hbox to 2.25in{\hfil \epsffile{4x4sans.eps}\hfil}
               \hbox to 2.25in{\hfil Figure 2: square, $\Omega_{4;\beta}$\hfil}}}
\bigskip

The conductances $\beta = \{\beta_i\}$ give rise to an
operator $\Lambda$ (more precisely, $\Lambda_\beta$), the
Dirichlet-to-Neumann operator for the network $\Omega_\beta$; if $\vec
\varphi$ is a vector representing the voltage potential at each boundary
node of $\Omega_\beta$, the vector of currents $\Lambda_\beta \vec \varphi$
represents the current flow at each boundary node, respectively.  The
matrix representations of these Dirichlet-to-Neumann maps are known as
$\lambda$-matrices.  When the network $\Omega$ is an $n \times n$ square
network, as shown above, it will be called $\Omega_{n;\beta}$, and the
Dirichlet-to-Neumann map $\Lambda_{n;\beta}$, respectively.

In this paper I am primarily concerned with the cross network, a refinement
of the ordinary square-lattice conductor network, that differs only in that
it is composed of elements of four conductors of equal conductivity,
arranged in a Greek or solar cross.  The Dirichlet-to-Neumann map for such
a network $\Omega^+_\alpha$ will be called $\Lambda^+_\alpha$, or simply
$\Lambda^+$, and the set of such maps, a subset of that for ordinary
networks, will be called the set of $\lambda^+$-matrices.

\section
     {Motivation: why solar crosses?}

Unlike the ordinary square-lattice network, the cross network lends an easy
interpretation to the voltage potential at the exterior nodes, and of the
conductances of its conductors, as an approximation to the case of
continuously varying conductance in a two-dimensional domain: the potential
at and current through a node correspond to the total\footnote
     {$\int_{edge}u\,d\lambda$ and $\int_{edge}\frac{\partial u}
     {\partial \vec n}\,d\lambda$, respectively, where $u$ is the potential
     function.}
potential of, and flux through, the face of an approximating block
of constant conductivity, and the conductivity $\alpha$ to twice the
constant conductivity density $\gamma$.  Another type of element with the
same properties, and indeed equivalent to the cross as a module, is that of
a flattened tetrahedron whose edges all have the same conductivity, i.e.,
$\frac{1}{2}\alpha_{cross} = \gamma = 2\alpha_{tetra}$.
The lack of a central node, however, makes them significantly more
difficult to work with.

The cross network also gives special properties to the $\Lambda^+$ map, as
will be discussed in the following sections.

\medskip From this point I shall discuss only {\em square} networks.

\section
     {Forward and Inverse problems: $\alpha     
     {}^{{}_\rightharpoonup}_{{}^\leftharpoondown} \Lambda^+_\alpha$}

\subsection
     {Ordinary Derivations:  $\alpha
     {}^{{}_\rightharpoonup}_{{}^\leftharpoondown} \beta
     {}^{{}_\rightharpoonup}_{{}^\leftharpoondown} \Lambda_\beta
     {}^{{}_\rightharpoonup}_{{}^\leftharpoondown} \Lambda^+_\alpha$}


The forward problem, that of determining the Dirichlet-to-Neumann map
$\Lambda$ from the known conductances $\{\alpha_i\}_{i=1}^{n^2}$, proceeds
directly, using techniques detailed in [2], [3], [4], and with the
knowledge of the conductance formula for conductors in series\footnote
     {more commonly known for resistors in series, $R_{equiv} = R_1 + R_2$;
     but conductance is the inverse of resistance, so
     $\frac{1}{\alpha_{equiv}}=\frac{1}{\alpha_1}+\frac{1}{\alpha_2}$.},
\begin{equation}
     \label{eq:series}
     \alpha_{equivalent}=\frac{\alpha_1\alpha_2}{\alpha_1+\alpha_2}.
\end{equation}

Likewise the inverse problem, once solved using the methods described in
[2]
for the square-lattice, can be further solved for all conductances
$\alpha_i$ by ``peeling off'' crosses from the boundary: the conductance of
each boundary conductor is equal to that of every other conductance in its
cross, and known crosses can be removed, revealing a new boundary.  A
preferable\footnote
     {in the sense of fewer operations}
method, however, is to use the relationships generated by the fact that the
network is of solar cross type to generate a different algorithm, as
in section \ref{sec:inverse}.

\subsection
     {Relations: $k$-corners and opposing sides}
\subsubsection{Corners}
\label{sec:corners}

In [3] it is shown that if zero potentials and zero currents are imposed
along the North and West faces of a square network (Figure 3), the
resulting potentials in all nodes north and west of the diagonal must be
zero; and this diagonal demarcation line may be moved NW by removing the
restrictions at the ``end'' nodes, those furthest south and east
respectively, or SE by imposing the same condition of zero voltage and zero
current at the northern nodes of the east face and the western nodes of the
south face.

\picture 3 {4x4czero.eps} {Figure 3: a 4-corner relationship for
$\Omega_{4;}$}

Known voltages placed at the other South-face boundary nodes may determine
voltages and currents through the rest of the network, including the other
(unrestricted) boundary nodes; in this manner, a ``$k$-corner
relationship'',
a linear system of the form
\begin{equation}
     \label{eq:lambda}\sum_{i=0}^{2k-1} x_i \lambda_{m,j+i} = 0, \qquad
     \hbox{for all}\ m \notin \{j, j+1, ... ,j+2k-1\}.
\end{equation}
is produced from $\Lambda_\beta$ and $k$, where the indices $j+k$ and
$j+k-1$ correspond to the two ``corner'' nodes, and $j$ and $j+2k-1$ to the
``end'' nodes.\footnote
     {Of course, consider all indices as residues modulo $4n$, e.g. $4n+1$
     and $1$ are equivalent as indices.  Also note that for every $k$ there
     are exactly {\em four} possible choices of $j$: $j=n-k+1, 2n-k+1,
     3n-k+1, 4n-k+1$.}

In [3] it is shown that (\ref{eq:lambda}) is over-determined\footnote
     {$x_k, ..., x_{2k-1}$ in terms of $x_0, ..., x_{k-1}$.}
when $k<n$, and under-determined when $k>n$.  In the case of the
over-determined systems, it is proved in [3] that although the system
(\ref{eq:lambda}) is over-determined, it has a solution $\vec x = (x_0, ...
, x_{2k-1})$ dependent only on $x_0, ..., x_{k-1}$.

The 1-corner relationship for cross networks is particularly simple,
stating that
\begin{equation}
     \lambda_{m,j} - \lambda_{m,j+1} = 0 \qquad\hbox{for all } m \notin
     \{j,j+1\}
\end{equation}
and
\begin{equation}
     \lambda_{j,j} - \lambda_{j+1,j+1} = 0
\end{equation}
where $j$ is one of $n$, $2n$, $3n$, $4n$.

\picture 3 {sides.eps} {Figure 4: the parallel-sides relationship for
     a $3 \times 3$ network}

\subsubsection{Remark}

In the case of cross networks, this method discovers a relationship between
$\Lambda^+_{n;\alpha}$ and $\Lambda^+_{n-1;\alpha |_{\Omega^+_{n-1}}}$:
when $k = n$, the same coefficients $\{x_i\}$ will solve the two
equations
\begin{equation}
     \label{eq:lambdaNdec}\sum_{i=0}^{2k-1} x_i \lambda^+_{n-1;m,j+i} =
     0, \qquad \hbox{for all}\ m \notin \{j,j+1,...,j+2k-1\}
\end{equation}
     and
\begin{equation}
     \label{eq:lambdaN}\sum_{i=0}^{2k-1} \chi(i) x_i \lambda^+_{n;m,j+i}
     = 0, \qquad \hbox{for all}\ m \notin \{j,j+1,...,j+2k-1\},
\end{equation}
where\qquad $\chi(i) = \cases{+1 &    if $0<i<2k-1$;\cr
                              -1 &    if $i=0$\ or\ $i=2k-1$\cr}$.

\subsubsection{Cone relations}

In the case that $n$ is odd, the following relationship is also possible.
Specifying voltage and current zero at all nodes on the north and south
faces,
as in Figure 4, the system
\begin{equation}
     \label{eq:sides}\sum_{i=1}^n x_i\lambda^+_{m,i} + \sum_{i=2n+1}^{3n}
     x_{i-n}\lambda^+_{m,i} = 0 \qquad\hbox{for all}\
m\in\{n+1,...,2n\}\cup
     \{3n+1,...,4n\}
\end{equation}
uniquely determines $\vec x$ as a function of $x_1$.  The same
relation can be found with respect to two adjacent sides,
as a special case of (\ref{eq:lambda}).

In any case ($n$ even or odd), a relation similar to
(\ref{eq:sides}) holds: given any interior node that is the
center of a cross, it is possible to force the potential to be zero at
that node and all nodes whose heading\footnote
     {where due east is considered to be heading zero, and proceeding
     counter-clockwise to $2\pi$, which is again due east.}
$\theta$, relative to the node in question, satisfies $-\frac{\pi}{4} \le
\theta \le \frac{\pi}{4}$\ or $\frac{3}{4}\pi \le \theta \le
\frac{5}{4}\pi$, by solving the (over-determined) system
\begin{equation}
     \label{eq:center} \sum_{i=2n-y-z}^{2n-y+z} x_{i-2n+y-z} \lambda^+_{m,i}
+
     \sum_{i=2n+y+z}^{4n-y-z} x_{i-2y} \lambda^+_{m,i} = 0,
\end{equation}
%
% this is a kluge
%
$$\hbox{for all}\ m \notin \{2n-y-z,...,2n-y+z\} \cup
\{2n+y+z,...,4n+y-z\}$$

\noindent for $\vec x$ in terms of $x_0$, where $(y,z)$ are the
Cartesian co\"ordinates of the cross element in question, considering the
south-western-most element as $(0,0)$.  This is exactly relation
(\ref{eq:sides}) when $y=z=\frac{n-1}{2}$.

\subsection
     {Specialized derivations: $\alpha \leftarrow \Lambda^+_\alpha$}
\label{sec:inverse}

The algorithm to find $\alpha$ proceeding inward from the corners is
described in detail in [2]; the only additions are as follows:

\begin{itemize}
\item     The corner conductances are immediately evident, for example
          $\alpha_{SE} = \lambda_{n,n} - \lambda_{n,n+1}$, from the
          1-corner relationship.
\item     After finding the conductances for each ladder, the known
          ``half'' of the conductance associated with a cross of known
          conductance must be ``subtracted'' using (\ref{eq:series}) to
          find the next diagonal of crosses.  Since only one leg of a cross
          need be computed, only half of the information gained in the
          solution to the general inverse problem need be employed; or,
          alternatively, the redundant information can be used to give
          greater accuracy.
\end{itemize}

Using the corner method, $n^2$ variables $x_{j;k;i}$ must be determined,
and if all of the corner relationships are used, the system can be
redundantly over-solved $2+\frac{2}{n}$ times.

If the conductance of a specific element is all that is desired,
relation (\ref{eq:center}) may prove useful.  The conductances of
boundary elements can be solved for directly, setting $x_0=1$;
$\alpha_*$, the conductance in question, is given by
\begin{equation}
     \alpha_* = \sum_{i=1}^{4n}\varphi_i\lambda^+_{m,i}
\end{equation}
where $\vec \varphi$ is the boundary potential vector obtained from
(\ref{eq:center}).

\picture 3 {crossedge.eps} {Figure 5: a cone relationship}

Once three adjacent boundary crosses are known, relation
(\ref{eq:center}) can again be used to find the conductance of the
element neighboring the centermost of the three elements; and
in general, if the conductances of all crosses forming a wedge, the
tip of which is the ``element in question'', are known,
(\ref{eq:center}) can be used to determine its conductance.

To solve the entire inverse problem in this fashion would require
solving for $4\sum_{i=1}^{n/2} (n-i)(2n-2i+1)$\ variables; it is
apparent that this method is useful primarily for determining the
conductance of single elements at or near the edge of a large network.

\subsubsection{Isolation}

The method of ``resistor isolation'' given in [4] can also be applied to
cross networks, although unlike general square-lattice networks, a path of
elements with known conductances must join the element in question with the
boundary if its conductance is to be determined.

\picture 3 {josh.eps} {Figure 6: Landrum's ``resistor isolation''}

In the general case, the method proceeds as follows: the conductor in
question, which I shall call $I$, has two nodes: a ``top'' node and a
``bottom'' node.  To all boundary nodes whose heading, relative to the
``top'' node satisfies $\frac{3\pi}{4} \le \theta \le \frac{5\pi}{4}$,
assign the potential $+1$, and to all boundary nodes whose heading,
relative to the ``bottom'' node, satisfies $-\frac{\pi}{4} \le \theta \le
\frac{\pi}{4}$, potential $0$, and to all of these boundary nodes assign
current $0$.  This forces two wedges of constant potential, as shown in
Figure 6.  The system
\begin{equation}
     \label{eq:josh}
     \sum_{i=2n-y-z}^{2n}          x_{2n-y-z+i}\lambda_{m,i} +
     \sum_{i=2n-y+z+2}^{2n+x+y+2}  \lambda_{m,i} +
     \sum_{i=3n}^{4n+y-z}          x_{i-2z-2}\lambda_{m,i}=0,
\end{equation}
%
% this is a kluge
%
$$\hbox{for all}\ m \in \{y-z+1,...,2n-y-z-1\} \cup
\{2n-y+z+2,...,2n+y+z+2\},$$

\noindent where $(y,z)$ are the Cartesian co\"ordinates of the bottom of $I$,
with
$(0,0)$ designating the south-western-most interior node, can be solved for
$\vec x$, and hence for $\vec \varphi$, the $4n$-dimensional vector of
potentials around the boundary.  In [4] it is shown that the current
through $I$, which is equal to the total flux through the ``top'' of the
network, i.e.
\begin{equation}
     \sum_{i=2n+z+1}^{5n-z}\lambda_{i,j}\varphi_i
\end{equation}
is also equal to the conductance of $I$, by Ohm's law.

Additional conductances are gained where the wedges of potential $0$
and $1$ join to the nodes whose potentials were determined by
(\ref{eq:josh}); since the potential of the nodes in the wedge is fixed,
and the potential at and current through the boundary node is known, Ohm's
law will reveal the conductance of the joining conductor.  At least two
conductances can be gained in such a fashion, raising the total for this
procedure to at least three conductances--although, as we are warned in [4],
accuracy rapidly drops as $(y,z)$ is removed from
$(\frac{n-1}{2},\frac{n-1}{2})$.

Unfortunately, however, returning to the cross network, this information is
not sufficient to recover any cross that does not border on another
element whose conductance is known.

\section
     {Characterization: Which $\Lambda$'s are $\Lambda^+$'s?}
\label{sec:characterization}

Obviously, not all square-lattice networks are of solar cross type; but
every cross network generates a square-lattice network from which it is
recoverable.  The question arises, then, how to tell the {\em legal} cross
networks from {\em illegal} or ordinary square-lattice networks.  If the
conductances are known, boundary crosses need only be peeled off until none
remain (legal) or a contradiction is reached (illegal).

Alternatively, the network can be subjected to the $k$-corner relationships
stated in section \ref{sec:corners}, in a partial solution of the
inverse problem; if any contradictions arise, e.g. if
$\lambda_{n;m,n}-\lambda_{n;m,n+1} \ne 0$ for any $m \notin \{n,n+1\}$,
this $\Lambda$ is not a legal $\lambda^+$-matrix.

\vfill\eject

\section*{Works Cited}

\noindent[1] Calderon, A. P., \underbar{On an Inverse Boundary Value
Problem}.

\noindent[2] Curtis, Edward B. and Morrow, James A.,\\
\underbar{Determining the Resistors in a Network}. SIAM J. Appl. Math, Vol.
50, No. 3, pp. 918-930, June 1990.

\noindent[3] Curtis, Edward B. and Morrow, James A.,\\
\underbar{The Dirichlet to Neumann Map for a Resistor Network}. SIAM J.
Appl. Math, Vol. 51, No. 4, pp. 1011-1029, August 1991.

\noindent[4] Landrum, Joshua,\\
\underbar{A Comparison of Three Algorithms for the Inverse Conductivity
Problem}.\\
August 1990.

\end{document}
