\documentclass[reqno]{amsart}
\usepackage{graphicx,latexsym}
\AtBeginDocument{{\noindent\small
{\em Electronic Journal of Differential Equations},
Vol. 2002(2002), No. 01, pp. 1--20.\newline
ISSN: 1072-6691. URL: http://ejde.math.swt.edu or http://ejde.math.unt.edu
\newline ftp ejde.math.swt.edu (login: ftp)}
\thanks{\copyright 2001 Southwest Texas State University.}
\vspace{1cm}}
\begin{document}
\title[\hfilneg EJDE--2001/01\hfil Boundary-value problems in discretized volumes]
{Solutions of boundary-value problems in discretized volumes}
\author[Mih\'aly Makai \& Yuri Orechwa \hfil EJDE--2002/01\hfilneg]
{Mih\'aly Makai \& Yuri Orechwa }
\address{ Mih\'aly Makai \hfill\break
KFKI Atomic Energy Research Institute \\
H-1525 Budapest 114, POB 49 \\
Hungary}
\email{makai@sunserv.kfki.hu}
\address{Yuri Orechwa \hfill\break
United States Nuclear Regulatory Commission \\
Washington DC, USA }
\email{yxo@nrc.gov}
\date{}
\thanks{Submitted June 1, 2001. Published January 2, 2002.}
\thanks{Partially supported by grant AEKI-144 fromthe Atomic Energy
Research Institute}
\subjclass[2000]{35B99, 20F29}
\keywords{boundary value problem, covering group, equispectral volumes }
\begin{abstract}
The solution of a boundary-value problem in a volume discretized
by finitely many copies of a tile is obtained via a Green's function.
The algorithm for constructing the solution exploits
results from graph and group theory. This technique produces
integral equations on the internal and external boundaries of the
volume and demonstrates that two permutation matrices characterize
the symmetries of the volume. We determine the number of linearly
independent solutions required over the tile and the conditions needed
for two boundary-value problems to be isospectral.
Our method applies group theoretical considerations to asymmetric volumes.
\end{abstract}
\maketitle
\newtheorem{theorem}{Theorem}[section] % theorems numbered with section #
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}
\numberwithin{equation}{section}
\section{Introduction}
The application of symmetry arguments to the solution of physical and
mathematical problems has a long and fruitful tradition. The development
of mathematical machinery in the form of group and graph theory gave
particular impetus to their application, in particular, in modern physics.
The advent of computers and the parallel flowering of numerical methods
have not yet exploited group theoretical principles to the same extent.
The development of nuclear power in the latter half of the last century
required the solution of large multidimensional boundary-value problems of
neutron transport which quickly taxed each advance in computational power.
Early on the possibility of systematically exploiting the symmetries inherent
in a nuclear reactor core using group theory were pointed out by Goldsmith (1963)
and Theophilou and Tsilimigras (1969); application to the finite element
formulation of boundary-value problems by F\"assler (1976); applications to
reactor control by Nieva and Christensen (1977);
the numerical formulation, viability
and the superior performance of a computer code for routine industrial
application was demonstrated for the solution of the neutron diffusion
equation Makai,(1980), Makai and Arkuszewski (1981); the application to
the response matrix method Makai (1984); the explanation
for the convergence of routinely applied iterative schemes Makai and Orechwa (1999)
the domain decomposition for parallel applications Makai and Orechwa (1997);
the optimization of sensor response in symmetric volumes Makai and Orechwa (2000).
Independently and somewhat later there appeared in the
literature similar approaches in the context of model problems, see Allgower,
B\"ohmer, Georg and Miranda (1992) and subsequent publications.
The success demonstrated by these implementations has given impetus to a
search for possible further applications of group theoretic results to the
numerical solution of boundary-value problems. In particular, we seek the
solution of an elliptic equation in a volume $\mathfrak{V}$ which is obtained by gluing
together copies of a given tile $\mathfrak{t}$. (Although only planar shapes are
considered here, we shall use the term volume, with an eye on those problems
in physics which are modeled as homogeneous and infinite in
extent in the
additional dimension.) The objective is to combine the language of numerical
analysis with that of modern algebra through group and graph theory to boundary
value problems on finite lattices.
To motivate the approach we can keep in mind two typical problems-- one physical,
the other mathematical-- which have a common formulation.
\begin{enumerate}
\item Determine the energy-band structure in a microscopic sample which
contains a few Wigner-Seitz cells. This requires the solution of the
Schr\"odinger equation in a finite region which consists of a
finite number of cells. A similar problem arises in the determination
of the neutron distribution in a finite periodic fuel lattice in a nuclear
reactor.
\item For the solution to a boundary-value problem with an elliptic operator in a
finite volume, one possible algorithm divides the volume into congruent
subvolumes (discretization). The solution is obtained iteratively from an
initial guess by taking one subvolume with given boundary conditions and solving
the equation in the subvolume; the solution inside the volume is expressed with the help of
the solution on the boundaries then we pass on to the next subvolume. This
type of numerical problem is encountered quite frequently.
\end{enumerate}
In the solution of a linear elliptic equation over a structure
$\mathfrak{V}$, which consists of a repetition of a tile $\mathfrak{t}$, we can exploit
translational symmetry. In an infinite lattice, for example, the solution is
usually expanded in terms of the eigenfunctions of the translation operator. In
certain finite volumes, with Dirichlet boundary conditions,
the image pile concept of Weinberg and Schweinler (1948) applies.
Assume that ${\mathfrak{V}}=G\backslash \mathfrak{t}$: that is, the orbit of $\mathfrak{t}$ under group $G$
is just $\mathfrak{V}$. Then, if $G$ commutes with operator $\mathcal{A}$ of the boundary value
problem (to be defined later), we can reduce the solution procedure from
$\mathfrak{V}$ to $\mathfrak{t}$.
Sunada (1985) and Brooks (1988) have given a method for deriving $G$ by
means of the fundamental groups $\pi_1({\mathfrak{t}})$ and $\pi_1(\mathfrak{V})$.
When $\mathfrak{t}$ is not
simply connected, $G$ is the quotient of the fundamental group of $\mathfrak{t}$
and $\mathfrak{V}$. When $\mathfrak{t}$ is simply connected, Gordon, Webb, Wolpert (1992)
made the case tractable.
An issue of interest and of practical consequence is the existence of
equispectral volumes. When
such volumes exist, the solids have the same spectrum, and the solutions
over two discretized volumes can be transformed into each other. Thus,
for a numerical solution we can choose the equispectral volume which is
easiest to solve. Sunada (1985), Brooks (1988)
and Buser (1988) have given a systematic method, based on group theory,
for finding equispectral volumes.
Our first task is to find a formalism which
accommodates some of the basic algebraic terms (e.g. covering group,
connectivity matrix) in the numerical algorithms for the solution of
boundary-value problems.
The Green's function of the tile is used to build a formal solution to the boundary
value problem. We then exploit graph properties to show that an
automorphism of a discretized volume can be described by two permutations.
The first permutes nodes, while the second permutes node boundaries.
The formal solution is expressed in terms of the solution along node boundaries.
These functions can be determined iteratively from (\ref{eq11}).
In problems with Dirichlet boundary conditions
the solution vanishes on external node boundaries; and thus, the number of unknowns is
smaller. The formalism gives the number of linearly
independent solutions over a node. In Section 5, we apply this approach to specific
problems: In the first, we show that "collective modes" may exist; (i.e. there are
situations where functions over two or more nodes together form a set of node
functions in such a way that they are transformed into each other when they are
reflected through a common internal boundary) the second example
illustrates the usage of the covering group, wherein the solution procedure is reduced to
a tile; the third example is taken from Gordon et al. (1992) and demonstrates the covering
group for a non-trivial shape. Section 6 addresses isospectral volumes. Assume that
connectivity matrices (see Section 3) ${{\bf C}}_1$ of volume $\mathfrak{V}_1$ and
${{\bf C}}_2$ of
volume $\mathfrak{V}_2$ are equivalent so that ${{\bf C}}_2={\bf TC}_1{\bf T}^{-1}$ and the
edge connectivity patterns described by the block matrices of the geometry
matrix in Section 3 are the same for $\mathfrak{V}_1$ and $\mathfrak{V}_2$. Then, the solution of a
suitable boundary-value problem over the constituents of $\mathfrak{V}_1$ is a linear
expression of the solutions over the constituents of $\mathfrak{V}_2$. Thus, by
solving an algebraic problem (viz. that of finding equivalent connectivity
matrices) we can solve boundary-value problems (viz. if the solution in $\mathfrak{V}_1$
is known we can also get the solution in $\mathfrak{V}_2$).
Our main results can be summarized as follows:
\begin{enumerate}
\item Knowledge of the covering group may result in a reduced range where we have
to find the solution. To demonstrate this, we present Example 3.
\item The amount of reduction depends on the structure of the covering group.
Existence of two-dimensional or higher representation tends to lessen the reduction.
\item If the geometry matrices of volumes ${\mathfrak{V}}_1$ and ${\mathfrak{V}}_2$ are similar,
and the conditions stipulated in Lemma 2 are met, ${\mathfrak{V}}_1$ and ${\mathfrak{V}}_2$
are isospectral.
\item We show the solution of a homogeneous problem contains as many
linearly independent node functions (defined later) as there are internal
boundaries in the volume.
\end{enumerate}
The matrices introduced in connection with the Green's
function, can be used to formulate the necessary conditions for two discretized
volumes to be isospectral.
The discretized volumes can be
ordered into classes with the help of the conjugate classes of the associated
node permutations. Construction of a computational scheme based
on these results may consist of these steps:
\begin{itemize}
\item find the symmetries of a discretized volume,
\item find the covering group, and
\item reduce the solution to a few tiles.
\end{itemize}
\section{The Physical Problem}
Let $\mathcal{A}$ be a linear, second order, elliptic operator with finite
coefficients at every point $x$. Consider the problem
\begin{equation} \label{eq1}
\begin{gathered}
\mathcal{A}\Phi(x)=\lambda \Phi(x) \quad x \in \mathfrak{V} \\
\mathcal{B}\Phi(x)=0 \quad x \in \partial \mathfrak{V},
\end{gathered}
\end{equation}
where $\mathcal{B}$ is a linear expression of $\Phi$ and of the normal
gradient $\partial_n\Phi$, where $n$ is the
outward normal at $x\in \partial \mathfrak{V}$.
In vibration problems, for example, $\mathcal{A}$ is the Laplace-Beltrami
operator, and $\mathcal{B}\equiv 1$. In solid-state physics, the
Schr\"odinger equation is given with
$$\mathcal{A}={\frac{\hbar^2} {2m}}\nabla^2 -V(x)
$$
as the Hamiltonian operator and $\mathcal{B}\equiv 1$. Here $V(x)$ is a given potential.
In neutron diffusion,
$$\mathcal{A}=-\langle D \rangle \nabla^2+\Sigma ,
$$
where $\langle D \rangle $ is a diagonal matrix, its entries are the diffusion
constants in the energy groups, $\Sigma$ is a matrix describing the energy
transfer processes. In the last example, the dependent variable is a vector,
${\underline \Phi}(x)$, called the
neutron flux whose components give the distributions of neutrons in energy.
On internal boundaries the flux and
$\langle D\rangle \partial_n{\underline \Phi}(x)$ (i.e. the normal component
of the current) must be continuous
and $\mathcal{B}\equiv 1$.
Some of the above problems have a unique solution if the material properties
(potential, cross-sections) have reasonable values, Habetler and Martino (1961).
If the solution is unique, the solution may inherit the symmetries of $\mathfrak{V}$,
see Kawohl (1998). The present work focuses on the conditions and numerical
exploitation of the latter observation.
We address the following mathematical properties of the above physical
problems. A
symmetry of $\mathfrak{V}$ can be described as the direct product of a
permutation of the nodes and a permutation of the sides of the
node. By means of the Green's function of the tile (i.e. of the node), and
knowledge of the solution along the edges the complete solution is determined.
The Green's function of the tile determines the dimension of the solution.
The number of edges where the solution is
not zero limits the linearly independent function shapes over a tile.
In Section 5, we apply the above considerations and construct a group $G$
such that the orbit of $\mathfrak{t}$ under $G$ just covers $\mathfrak{V}$.
In Section 6, we give a condition for two volumes to be isospectral.
The condition is formulated using the Green's function of the tile. We show
that the isospectral volumes derived by Sunada (1988), Brooks (1988),
Gordon et al. (1992) satisfy the condition we have specified.
%Finally, in
%Section 7 we give two further examples: we reproduce a theorem derived by
%Hersch (1965) for a vibration problem, and show the dimension of the
%solution for a volume investigated by Buser et. al (1994).
\section{Group theoretic, geometric and analysis background}
Below we outline the group theoretic background
applied throughout the present work;
for group theory and geometry, we follow Stillwell (1993) and Babai (1995),
for the response matrix
method, as a numerical method for solving boundary-value problems,
Weiss (1977).
\subsection*{Group theoretic background}
\begin{itemize}
\item {\em Generator}. In combinatorial topology, groups are described in
terms of ``generators" and ``relations". A generator is a letter $a_i$, and
has a formal inverse $a_i ^{-1}$. A word $w$ is any finite sequence
$$a_{i_1} ^{\epsilon_1}a_{i_2} ^{\epsilon_2}\dots a_{i_k} ^{\epsilon_k}$$
of generators or their inverses, so that each $\epsilon_j=\pm1$, where
$a_i ^{+1}$ denotes $a_i$. The product $w_1 w_2$ of words $w_1$ and $w_2$ is the
concatenation of the corresponding sequences. The empty word is denoted by $1$.
A relation is an equation $r=1$ where $r$ is a word. Words $w$ and $w'$ are called
equivalent with respect to relations $r_j=1$ if $w$ is convertible to $w'$ by a
finite sequence of operations of the following types:
\begin{enumerate}
\item insertion or deletion of a subword $r_j$,
\item insertion or deletion of a subword $a_i a_i ^{-1}$ or $a_i ^{-1}a_i$.
\end{enumerate}
\item {\em Finitely presented group}. The structure $\langle a_1,a_2,\dots:r_1,r_2,\dots\rangle$
of equivalence classes of words in $a_i$ with respect to the relations $r_j$,
under the product operation, is a group $G$. The expression
$\langle a_1,a_2,\dots:r_1,r_2,\dots\rangle$
is called a presentation of $G$. $G$ is finitely presented if it has a presentation
in which the sets $\{a_i \}$ and $\{ r_j \}$ are finite.
\item {\em Representation by matrices}. If $G$ is a finite group, and ${\bf M}_g$ is
a matrix, the isomorphism
$g\leftrightarrow {\bf M}_g$ for all $g\in G$ is called a matrix representation of $G$.
\item {\em Coset representation.} If $A$ is a subgroup of $G$ the sets
$Ag=\{ag:a\in A\}$
for $g\in G$ are called right cosets of $G$ modulo $A$. They constitute a partition
of $G$, called the {\em right coset decomposition}.
\item {\em Orbit}. Let $d$ be an object on which the action of elements of $G$ has been
defined. A point $e$ in the orbit of $d$ under the group $G$ is the point
for which a group element $g$ of $G$ exists such that $g\hat{}d=e$, where
$g\hat{}d$ is the object ``$g$ applied to $d$".
\item {\em Group action on functions}. Let $x$ denote the independent variables
in the problem under consideration. With a matrix representation acting on $x$,
the group action on a function $f(x)$ is usually defined as $gf(x)=f(g^{-1}x)$.
\end{itemize}
\subsection*{Geometric background}
The geometric notions applied throughout
the present work follow Stillwell (1993).
\begin{itemize}
\item {\em Graph}. A graph $\Gamma$ is defined by its vertex set $W$ and edge
set $E$.
\item {\em Symmetries of a graph}. In analogy to symmetries of volume
$\mathfrak{V}$, we need the symmetries (automorphisms) of a graph.
The automorphisms of a graph $\Gamma=(W,E)$ are permutation pairs $P, p$, where
$P$ permutes the elements of set $W$ whereas $p$ permutes elements of set $E$ so that
the incidence between vertices and edges is preserved, see Babai (1995).
\item {\em Discretized volume}. A discretized volume is created by the following
operations. We start from a tile $\mathfrak{t}$, which is a suitable polygon. We can reflect
$\mathfrak{t}$ along a side if the vertices of the new copy lie on the boundary of the first
tile, or entirely outside it. This gives a discretized volume consisting of two
copies of $\mathfrak{t}$. The procedure can be repeated whenever the vertices of the new copy of the tile
do not lie inside another already existing tile. We call the copies subvolumes
or nodes.
In the discretized volume, $E^k$ ($k=1,K$) denotes the set of edges,
A subvolume $F_{m\alpha}$ ($\alpha=1,n_F$) stands for the sides of node
$m$. $\phi_m$ is the restriction of the solution $\Phi(x)$ to
the $m$-th node. As the nodes are congruent, we can map them into each other.
Node $m=1$ is considered as the reference and $\tau_m$ is an isometry from
node $m=1$ to the $m$-th node. Such an isometry is the reflection of a node
through a joint boundary. With the consecutive application of that step, we
can map any node in $\mathfrak{V}$ into a given node. We can define a linear
transformation among the $\phi_m$'s as follows:
$$a_i\phi_i +a_j\phi_j=a_i\Phi\circ\tau_i+a_j\Phi\circ\tau_j .$$
We divide the edges as
$$E=E_i +E_e =\bigcup_{m=1}^N E_m=\bigcup_{m=1}^N\bigcup_{\alpha=1}^{n_F}
F_{m\alpha}=\bigcup_{k=1}^K E^k, $$
where $E_i$, $E_e$ are the set of internal and external edges; $E_m$ is the
set of edges belonging to node $m$, and $F_{m\alpha}$ stands for edge $\alpha$
of node $m$. An internal edge separates two nodes; an external edge lies
on the external boundary $\partial \mathfrak{V}$; $E^k$ is the $k$-th edge in $\mathfrak{V}$.
\item {\em Connectivity matrix}. The geometry of a discretized volume consisting
of $N$ copies of $\mathfrak{t}$ is characterized by a square matrix ${\bf C}$ called the connectivity
matrix of volume $\mathfrak{V}$. $C_{ij}=1$ if subvolumes $i$ and $j$
share an edge, $0$ otherwise.
\item {\em Fundamental group}.The product and inverse of closed curves is defined
as follows. The natural product of two curves $p,q$ which begin at $P$ is their
concatenation, the inverse $p^{-1}$ of $p$ will lie on top of $p$ but with the
opposite orientation. The fundamental group is a group of equivalence classes
of closed paths in a discretized volume $\mathfrak{V}$.
\item {\em Covering group}. If there is a group $G$, acting on a tile $\mathfrak{t}$ and
its orbit is $\mathfrak{V}$, $G$ is called covering group of $\mathfrak{V}$.
\item {\em Chromatic number}. Like a geographic map, a discretized volume
can also be colored. The minimal number of colors needed to color $\mathfrak{V}$ is called
its chromatic number.
\item{\em Quotient manifold.} Let us consider a manifold $\mathfrak{X}$, on which the action
of elements of $G$ is defined with $x$ being equivalent to $y$ if they lie in
the same orbit of $G$. Let $\mathfrak{X}/G$ denote the set of equivalence classes, or,
equivalently, the set of orbits of $G$. The equivalence class can be identified with
the orbit of $G$ passing through $x$. $\mathfrak{X}/G$ is called quotient manifold.
\end{itemize}
\subsection*{Analysis and numerical background}
In this Section, we outline the basic notions of mathematical analysis applied throughout
the present work.
\begin{itemize}
\item {\em Function space}. Throughout the present work, we are interested in
functions given in a finite region $\mathfrak{V}$. The space of functions continuous
along with its first derivatives is denoted by $C^1(\mathfrak{V})$.
\item {\em Operator}. An operator $\mathcal{A}$ is a map $C^1(\mathfrak{V})\rightarrow C^1(\mathfrak{V})$.
\item {\em Boundary value problem (BVP)}. The boundary-value problem under consideration
is (\ref{eq1}). We assume operators $\mathcal{A},\mathcal{B}$ to be linear. The boundary value is
prescribed on the boundary of $\mathfrak{V}$.
\item {\em Green's function}. With the help of the Green's function $\mathcal{G}$,
the boundary-value problem is transformed into an integral equation.
In the sequel, we consider BVP where the solution is prescribed on the boundary
(Dirichlet type BVP). We assume the existence of the following Green's function in each node:
\begin{equation}\label{eq2}
\begin{gathered}
\mathcal{A}\mathcal{G}_{\rm node}(x,x')=\lambda \mathcal{G}_{\rm node}(x,x')\quad x,x'
\in {\mathfrak{V}}_{\rm node}\\
\mathcal{B}\mathcal{G}_{\rm node}(x,x')=\delta (x-x') \quad x
\in {\mathfrak{V}}_{\rm node}, x'\in \partial
{\mathfrak{V}}_{\rm node}.
\end{gathered}
\end{equation}
Here $\delta$ is Dirac's delta function. Since all the nodes are congruent,
$\mathcal{G}_{\rm node}$ is applicable to every node in $\mathfrak{V}$. This Green's function,
when $x'$ is restricted to side $\alpha$, is
written as $\mathcal{G}_{{\rm node}\alpha}(x,x')$. Then, the solution in any node $m$
is expressed in terms of this Green's function as a sum of integrals over
the edges of the node as
\begin{equation}\label{eq3}
\phi_m (x)=\sum_{F_{m\alpha}\in E}\int_{F_{m\alpha}} \mathcal{G}_{{\rm node}\alpha}(x,x')q_{m\alpha} (x')dx'.
\end{equation}
Here
\begin{equation}\label{eq4}
q_{m\alpha}(x)=\Phi(x) \quad x \in F_{m\alpha}.
\end{equation}
When $x$ tends to the boundary of $\mathfrak{t}$, we have
\begin{equation}\label{eq5}
\lim_{x\to \partial t}\mathcal{G}_{{\rm node}\alpha}(x,x')=\left \{
\begin{array}{ll}
\delta (x-x') & \mbox {if $x \in F_{m\alpha}$ } \\
0 & \mbox {otherwise.}
\end{array}
\right.
\end{equation}
Thus,
\begin{equation}\label{eq6}
\lim_{x \to \partial t} \int_{F_{m\beta}}\mathcal{G}_{{\rm node}\alpha}(x,x')q_{m\beta}(x')dx'=
\int_{F_{m\beta}}\delta_{\alpha\beta}\delta(x-x')q_{m\beta}(x')dx'=
\delta_{\alpha\beta}q_{m\beta}(x),
\end{equation}
were $\delta$ is the Kronecker symbol.
The solution of the Dirichlet type BVP takes the form
\begin{equation}
\Phi(x)=\int_{x'\in \partial {\mathfrak{V}}} \mathcal{G}(x,x')f(x')dx'
\end{equation}
where $\mathcal{G}(x,x')$ is the Green's function for volume $\mathfrak{V}$ and $f(x')$ is a given function
on the boundary $\partial \mathfrak{V}$. The Green's function possesses the
following properties:
\begin{itemize}
\item If ${\bf O}\mathcal{A}=\mathcal{A}{\bf O}$ then
$\mathcal{G}({\bf O}x,{\bf O}x')=\mathcal{G}(x, x')$,
i.e. the symmetries of $\mathcal{A}$ leave the Green's function invariant;
\item $\mathcal{G}(x,x')$ -along with its first-order derivatives- is continuous
for all $x, x'$ if $x\ne x'$ and neither $x$ nor $x'$ lies on the
boundary;
\item $\mathcal{G}(x,x')=\mathcal{G}(x',x)$ and $\mathcal{G}(x,x')>0$ if $x\ne x'$.
\end{itemize}
\item {\em Geometry matrix}. The geometry matrix $\bf H$ expresses the connection
between the nodes in discretized volume $\mathfrak{V}$. The solution belongs to $C^1$,
hence, the normal gradients are continuous at internal faces, which
can be expressed as
\begin{equation}\label{eq10}
\begin{pmatrix}
{\bf H}_{11}& \dots & {\bf H}_{1N} \\
\vdots & \ddots & \vdots \\
{\bf H}_{N1}& \dots & {\bf H}_{NN}
\end{pmatrix}
\begin{pmatrix}
{\underline J}_1 \\
\vdots \\
{\underline J}_N
\end{pmatrix}
=0 .
\end{equation}
The geometry matrix contains $N$ blocks of order $n_F$ in each
row. In a row there are at most $n_F$ non-zero blocks. The element $(\alpha, \beta)$
in block ${\bf H}_{mm'}$ is $1$ if nodes $m$ and $m'$ are adjacent along side
$\alpha$ of node $m$ and side $\beta$ of node $m'$. The blocks on the diagonal
are diagonal matrices of order $n_F$. Element $({\bf H}_{mm})_\alpha =1$ if
side $\alpha$ of node $m$ is internal and $({\bf H}_{mm})_\alpha=0$ if side $\alpha$
of node $m$ is external. The vectors $J_{m\beta}(x)$ are defined in the
following.
\item {\em Reformulation of BVP}. Using the above Green's function, the boundary
value problem is reformulated. In the context of the
response matrix formalism, Weiss (1977), the normal gradient at face $\beta$ of ${\mathfrak{V}}_m$
is
\begin{equation}\label{eq7}
J_{m\beta}(x)=\partial_{n_\beta} \Phi(x); \quad x\in F_{m\beta}.
\end{equation}
The gradient can then be expressed by the solution
at the boundary as
\begin{equation}\label{eq8}
J_{m\beta}(x)=\sum_{\alpha \in E_m} \int_{F_{m\alpha}}\partial_{n_\beta} \mathcal{G}_{{\rm node}\alpha}
(x,x')q_\alpha (x')dx'=
\sum_{\alpha \in E_m} \mathcal{R}_{\beta\alpha}^{(m)}q_\alpha ^{(m)}.
\end{equation}
Let face $\alpha$ separate nodes $k_\alpha ^+$ and $k_\alpha ^-$. The continuity
of the normal gradient is expressed by
\begin{equation}\label{eq9}
\begin{aligned}
J_{k_\alpha ^+}(x) &=\sum_{\beta \in E_{k_\alpha ^+}}\mathcal{R}_{\alpha\beta}^{(k_\alpha ^+)}
q_\beta ^{(k_\alpha ^+)}(x')= \notag \\
-J_{k_\alpha ^-}(x)&=\sum_{\beta \in E_{k_\alpha ^-}} \mathcal{R}_{\alpha\beta}^{(k_\alpha ^-)}
q_\beta ^{(k_\alpha ^-)}(x').
\end{aligned}
\end{equation}
This is a set of linear integral equations for the solutions on the boundaries.
A nontrivial solution exists only if the null space of the operator acting on the
$"q"$s is not empty. This condition is met at certain values of $\lambda$,
called the eigenvalues of problem (\ref{eq1}).
Let us collect the gradients at the faces of node $m$ into a vector
${\underline J}_m=(J_{m\alpha}, \alpha=1,n_F)$. The continuity of the gradients
at the $N_i$ internal faces takes the form (\ref{eq10}),
where $N$ is the number of nodes in $\mathfrak{V}$. The matrix in (\ref{eq10}) is called a
geometry matrix, Weiss (1977), and contains $N$ blocks of order $n_F$ in each
row. As described above, in a row there are at most $n_F$ non-zero blocks. The element $(\alpha, \beta)$
in block ${\bf H}_{mm'}$ is $1$ if nodes $m$ and $m'$ are adjacent along side
$\alpha$ of node $m$ and side $\beta$ of node $m'$. The blocks on the diagonal
are diagonal matrices of order $n_F$. Element $({\bf H}_{mm})_\alpha =1$ if
side $\alpha$ of node $m$ is internal and $({\bf H}_{mm})_\alpha=0$ if side $\alpha$
of node $m$ is external. Thus, the geometry matrix and the connectivity matrix
of $\mathfrak{V}$ are related as
\begin{equation}\label{eq11}
\begin{pmatrix}
{\bf H}_{11}& \dots & {\bf H}_{1N} \\
\vdots & \ddots & \vdots \\
{\bf H}_{N1}& \dots & {\bf H}_{NN}
\end{pmatrix} ={\bf C}\times {\bf H}_{ij}+
\begin{pmatrix}
{\bf E-P}^{(1)} & & 0 \\
& \ddots & \\
0& & {\bf E-P}^{(N)}
\end{pmatrix},
\end{equation}
where ${\bf C}$ is the connectivity matrix and the direct product ($\times$) replaces
$1$ in position $mm'$ by ${\bf H}_{mm'}$, ${\bf E}$ is the $n_F$ order identity
matrix. The $n_F$ order matrix ${\bf P}^{(m)}$ projects out the external sides
of node $m$. If edge $\alpha$ is on the external boundary $\partial \mathfrak{V}$ and it
is in node $m$, then element $(\alpha,\alpha)$ in block ${\bf H}_{mm}$ specifies
a linear relationship between the solution and its normal gradient. Let constants $a^{(k)}$
and $b^{(k)}$ belong to the boundary condition at edge $E^k$. We drop superscript $k$
and characterize the general boundary condition
\begin{equation}\label{eq12}
a \Phi(x)+b\partial_n \Phi(x)=0
\end{equation}
by $a$ and $b$. Different edges may be characterized by different $(a,b)$,
which may also depend on the position.
We collect solutions along the $n_F$ sides of node $m$ into vector
${\underline q}_m$. Since in node $m$ the gradient is expressible by ${\underline q}_m$,
and assuming that constants $a$ and $b$ are the same in a given node, we get
\begin{multline}\label{eq13}
\begin{pmatrix}
{\bf H}_{11}& \dots & {\bf H}_{1N} \\
\vdots & \ddots & \vdots \\
{\bf H}_{N1}& \dots & {\bf H}_{NN}
\end{pmatrix}
\begin{pmatrix}
{\bf \mathcal{R}}^{(1)} & & 0 \\
& \ddots & \\
0 & & {\bf \mathcal{R}}^{(N)}
\end{pmatrix}
\begin{pmatrix}
{\underline q}_1 \\
\vdots \\
{\underline q}_N
\end{pmatrix}
= \\
\begin{pmatrix}
{\bf P}^{(1)} ( b^{(1)}*{\bf \mathcal{R}}^{(1)}+a^{(1)} ) & & 0 \\
& \ddots & \\
0& & {\bf P}^{(N)} ( b^{(N)}*{\bf \mathcal{R}}^{(N)}+a^{(N)} )
\end{pmatrix}
\begin{pmatrix}
{\underline q}_1 \\
\vdots \\
{\underline q}_N
\end{pmatrix}.
\end{multline}
Here ${\underline q}_m$ is the solution vector of $n_F$ components on the
sides of node $m$. In this equation, the external boundary condition
has been implemented as well. It should be noted that the left-hand side of
(\ref{eq13}) vanishes on external boundaries, whereas the right hand side
on internal boundaries. When node $m$ has at least one external boundary, the
block ${\bf H}_{mm}$ on the diagonal is an $n_F$ order diagonal matrix describing
the boundary condition at the boundaries of node $m$ lying also on $\partial \mathfrak{V}$.
Equation (\ref{eq13}) is the key to the solution of problem (\ref{eq1}-3).
Equation (\ref{eq13}) is an integral equation, the unknowns to be determined being
${\underline q}_1(x), \dots , {\underline q}_N(x)$. The kernel is implicitly in the
elements of ${\bf \mathcal{R}}^{(1)} , \dots ,{\bf\mathcal{R}}^{(N)}$ and involves the gradients of the
Green's function. Equation (\ref{eq13}) is a homogeneous problem: a nontrivial solution exists
only when the null space of the matrix is not empty. This is achieved by a suitable
choice of the eigenvalue $\lambda$ in (\ref{eq2}). Computer programs are available
to solve (\ref{eq13}), see e.g. Dorning (1979). We introduce the following compact
notation to shorten (\ref{eq13}):
\begin{equation} \label{13a}
{\bf H}\mathcal{R} {\bf q}=\mathcal{S}{\bf q}
\end{equation}
with obvious notation.
There are also numerical procedures to determine the largest eigenvalue and the
associated values of the solution at the boundaries. This is the solution we
are interested in; this solution is unique up to normalization. Once the
solution values at the boundaries are known, we can use (\ref{eq3}) to get the
solution at arbitrary $x$ in $\mathfrak{V}$. When the material composition is the same
in all the nodes, we have ${\bf \mathcal{R}}^{(m)}={\bf\mathcal{R}}$ for $m=1, \dots , N$.
\end{itemize}
\section{Structure of the Solution to a BVP}
We start with an analysis of the discretized volume $\mathfrak{V}$. The main question is
to determine when two apparently different discretized volumes are actually identical.
\begin{definition}\label{d1} \rm
Let tile $\mathfrak{t}$ have $n_F$ straight line sides. Let $\mathfrak{V}$ be a volume composed of
$N$ copies of a tile $\mathfrak{t}$, so that any two adjacent copies share a side of the
tile. Graph $\Gamma$ is created in the following manner. $N$ copies of
$\mathfrak{t}$ form the vertex set $W$ of the graph, and vertex $i$ and $j$ are connected
by an edge of color $\alpha$ if tile $i$ and $j$ share a side $\alpha$ of $\mathfrak{t}$.
This graph is referred to as $\Gamma({\mathfrak{V}},t)$.
\end{definition}
\begin{definition}\label{eqV} \rm
Two discretized volumes $\mathfrak{V}$ and ${\mathfrak{V}}'$ are called equivalent, if there
exists a map $i\leftrightarrow i'$ such that if nodes $i_1$ and $i_2$ in $\mathfrak{V}$ share
an edge of type $\alpha$ then nodes $i_1'$ and $i_2'$ in ${\mathfrak{V}}'$ also share an
edge of type $\alpha$.
\end{definition}
\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.4\textwidth]{fig1.eps}
\end{center}
\caption{Square composed of 8 triangles}
\end{figure}
Figure 1 is an illustration for the introduced terms. There tile $\mathfrak{t}$ is an
isosceles right triangle, the square volume $\mathfrak{V}$
consists of 8 copies of $\mathfrak{t}$. Tile $\mathfrak{t}$ has edges
$\alpha,\beta, \gamma$ but edge $\beta$ is always
on the external boundaries. There are 8 vertices and 8 edges in
$\Gamma(\mathfrak{V},t)$. Nodes 1 and 2 are connected by a $\gamma$ type edge,
nodes 2 and 3 are connected by an $\alpha$ type edge. In this case the graph
$\Gamma(\mathfrak{V},t)$ is closed.
Since the $\phi_m$'s form a linear space, we can ask the "dimension" of the solution.
In other words, we can ask the minimum number of functions over the tile with
the help of which we can build the solution of problem (1). Finally, exploiting
the fact that all the nodes can be mapped to $\mathfrak{t}$, we can define the dimension
of a function given on $\mathfrak{V}$.
\begin{definition}\label{d5} \rm
Let $\Phi(x)$ be given for any $x \in \mathfrak{V}$. Let $\phi_m(x)$ denote the restriction
of $\Phi(x)$ to $x \in {\mathfrak{V}}_m\subset \mathfrak{V}$ which we call node function and consider it
as a function of the position in tile $\mathfrak{t}$. $Dim(\Phi(x))$ is the
maximum number of linearly independent node functions. \end{definition}
Given the above dimension of the solution, we can seek a relationship between
the solutions belonging to two problems, which are formulated with the same operators
$\mathcal{A}$ and $\mathcal{B}$ but for different volumes ${\mathfrak{V}}_1$ and ${\mathfrak{V}}_2$.
The first problem is to reduce the number of data to describe $\mathfrak{V}$. To this end the
following automorphisms are exploited in the reduction.
\begin{definition}\label{d6} \rm
Operator ${\bf O}$ is called a symmetry of the boundary-value problem (\ref{eq1}-3)
if (i), ${\bf \mathcal{A}O}={\bf O\mathcal{A}}$ (ii), ${\bf \mathcal{B}O}={\bf O\mathcal{B}}$ and (iii), ${\bf O}$ is
invertible and maps $\mathfrak{V}$ into itself.
\end{definition}
\begin{lemma}\label{le1}
Let ${\bf O}$ be a symmetry of problem (\ref{eq1}). Then we can associate
a permutation $\bf P$ of the nodes and a permutation $p$ of the $n_F$ node
sides with ${\bf O}$.
\end{lemma}
{\em Proof}: A symmetry maps $\mathfrak{V}$ into itself, so it is an automorphism of
$\Gamma({\mathfrak{V}},t)$. This ensures preservation of incidence relation between
vertices and edges.
Thus, a general symmetry may have two effects:
mapping nodes into nodes and permutation of node faces as stated. \quad$\Box$
\begin{proposition}\label{p1}
The permutation matrices, which preserve the adjacency relation among node sides,
form a group $G$. The elements of that group leave the matrix
$\bf \mathcal{R}$ in (\ref{eq13}) invariant.
\end{proposition}
{\em Proof}: Each element $\mathcal{R}^{(k)}$ of block matrix ${\bf \mathcal{R}}$ is a cyclic matrix Diaconis (1990), its rows differ only
in the element order. The permutations preserving adjacency form a group
because there is a unit transformation; they are closed for
matrix multiplication; matrix multiplication is associative, each matrix is
invertible thus each has an inverse. Hence, the permutations under
consideration form group $G$. $ \mathcal{R}^{(k)}$ is cyclic, thus its element
$\mathcal{R}_{ij}$
depends only on the adjacency of edges $i$ and $j$, which adjacency is
untouched by elements of group $G$. \quad$\Box$
\begin{proposition}\label{p2}
A symmetry of (\ref{eq13}) orders the nodes into cycles. The nodes in one
cycle are permuted among each other. For the node-side permutation $p$, when the
maximal orbit length is $L$, then $p^L=1$.
\end{proposition}
{\em Proof}: A symmetry maps a node into another node, this map is
a permutation of nodes. According to Lemma \ref{le1}, a symmetry can be given
by a permutation ${\bf P}$ of nodes, actually ${\bf P}$ is a matrix of order $N$,
and a node-side permutation $p$. The permutation ${\bf P}$ can be ordered into
cycles, the nodes in a cycle are permuted among themselves. Applying a
given symmetry as many times as the maximum cycle length, we get the original
node- and node-side numbering, i.e. we get the identity transformation, thus, the
associated side permutation matrix satisfies $p^L=1$ as stated. \quad$\Box$
A corollary of Proposition {\ref{p2} is that the length of an orbit in a node
permutation associated with a symmetry can not be longer than the maximum order
of an element in group $G$.
Unless otherwise stated, we consider Dirichlet
problems: $\mathcal{B}\equiv 1$, where the solution vanishes on the external
boundaries and we deal only with internal boundaries. The $K$
non-zero boundary functions $q_k$ and the solutions $\phi_m$ in the $N$ nodes
are collected into their respective vectors{\footnote{Note the formal difference between $\underline
q$ and ${\bf q}$. The former involves the solution as function along the $K$ internal
faces, the latter consists of $N$ vectors of length $n_F$. The two vectors contain
the same information.}:
\begin{equation}\label{eq14}
\begin{gathered}
{\underline q}=\left(q_1, \dots,q_K \right) \\
{\Vec \phi}=\left( \phi_1, \dots \phi_N \right).
\end{gathered} \end{equation}
Clearly,
\begin{equation}\label{eq15}
{\Vec \phi}(x)={\bf \mathcal{M}}(x,x'){\underline q}(x'),
\end{equation}
where operator $\bf \mathcal{M}$ has $K$ columns and $N$ rows. In a row, $\bf \mathcal{M}$ may have
at most $n_F$ non-zero elements. $\bf \mathcal{M}$ is also a matrix,
its element $\mathcal{M}_{m\alpha}$ is defined by
\begin{equation}\label{eq16}
\mathcal{M}_{m\alpha}(x,x')*q_\alpha (x')=\int_{E_\alpha}
\mathcal{G}_{{\rm node}\alpha(m)}(x,x')q_\alpha (x')dx'.
\end{equation}
Here the notation $\alpha(m)$ refers to boundary type $\alpha$ in node $m$.
The following definition aims at separating a linear integral operator from the
matrix. The latter carries information on the structure of $\mathfrak{V}$, the former depends
on the boundary value to be solved.
\begin{definition}\label{d7} \rm
We write the linear operator ${\bf \mathcal{M}}(x, x')$ as a product of a matrix in
which the elements may take the value $0$ or $1$, and a diagonal matrix, whose
entries are integral operators:
\begin{equation}\label{eq16a}
{\bf \mathcal{M}}(x,x')={\bf Q}*{\bf \mathcal{G}}_K (x,x'),
\end{equation}
where $\bf Q$ is a $K\times M$ matrix and ${\bf \mathcal{G}}_K$ is a diagonal matrix of
order $K$, in the $k$th row its entry is $\mathcal{G}_\alpha(x,x')$ provided that boundary
$k$ is of $\alpha$ type.
\end{definition}
\begin{proposition}\label{p3}
$ \dim({\Vec \phi})=\mathop{\rm rank}({\bf Q})$.
\end{proposition}
{\em Proof}: Because ${\Vec \phi} (x)$ is a linear expression (cf. Eqs. (\ref{eq15})
and (\ref{eq16a})) of the rows in matrix $\bf Q$, the statement follows.
\quad$\Box$
When the solution to (\ref{eq1}) is unique and $\bf O$ is a symmetry of
(\ref{eq1}) then ${\bf O}:{\underline q} \to {\underline q}$ and ${\bf O}:
{\Vec \phi} \to {\Vec \phi}$. So a symmetry of problem (\ref{eq1})-(3) leaves
the set of equations determining the solution along boundaries invariant.
Let us return to the continuity of the normal gradients. Now the matrix in (\ref{eq10})
is a square matrix. To determine $Dim({\underline q})$, we note that if $\bf O$
is a symmetry of $\mathfrak{V}$, then it transforms internal edges into internal edges and
external edges into external edges. The symmetries of $\mathfrak{V}$ form a group $G$. Furthermore,
the symmetries of $\mathfrak{V}$ permute edges among themselves. Symmetry transforms a vertex
emanating $j$ edges into another vertex emanating $j$ edges. If the symmetries of
$\mathfrak{V}$ commute with operator $\mathcal{A}$, a representation of the symmetry group is also an
eigenspace of $\mathcal{A}$. If ${\mathfrak{V}}_0={\mathfrak{V}}/G$ then the solution in ${\mathfrak{V}}_0$ fully describes a
given representation. Consequently, $E/G$ fully describes the edges and ${\underline q}/G$
fully describes the internal faces. Now, let
\begin{gather*}
{\underline \phi}_0(x)={\underline \phi}(x)/ G \\
{\underline q}_0(x)={\underline q}(x)/ G ,
\end{gather*}
so that the zero subscripted functions refer to nodes in ${\mathfrak{V}}/G$.
We write (\ref{eq15}) on ${\mathfrak{V}}/G$ as
\begin{equation}\label{eq15a}
{\underline \phi}_0(x)={\bf \mathcal{M}}_0(x,x'){\underline q}(x'), \quad x,x'\in {\mathfrak{V}}/G.
\end{equation}
We have arrived at the following statement.
\begin{proposition}\label{p4}
Let $G$ denote the symmetry group of $\mathfrak{V}$. Then,
$\dim(\Vec\phi / G)=\mathop{\rm rank}({\bf \mathcal{M}}_0)$.
\end{proposition}
Since a symmetry of $\mathfrak{V}$ permutes the internal edges, we can easily formulate how
to obtain a symmetry of $\mathfrak{V}$.
\begin{proposition}\label{p5}
Let $\bf O$ be a symmetry of problem (\ref{eq1}). Assume that the solution to problem
(\ref{eq1}) is unique. Then ${\bf O\mathcal{R}O}^{-1}={\bf \mathcal{R}}$, ${\bf OHO}^{-1}={\bf H}$ and
${\bf O}{\bf q}={\bf q}$.
\end{proposition}
{\em Proof}: According to Definition \ref{d6}, item (i), $\bf O$ commutes with
$\mathcal{A}$, thus according to the first property of the Green's function ${\bf O\mathcal{R}}={\bf \mathcal{R}O}$. By
definition, $\bf O$ is an automorphism of $\Gamma({\mathfrak{V}},t)$ so adjacency and non-adjacency
are preserved. Applying $\bf O$ to (\ref{13a})
we get from Definition {\ref{d6}, item (ii): ${\bf SO}={\bf OS}$ and
$({\bf O(H\mathcal{R})O}^{-1}{\bf O}){\bf q}={\bf OS}{\bf q}={\bf SO}{\bf q}$.
Since $\bf O$ is a symmetry, ${\bf O}{\Vec \phi}$ is also a solution but by the uniqueness
${\bf O}{\Vec \phi}={\Vec \phi}$ and consequently ${\bf O}{\bf q}={\bf q}$.
Comparing the above equation to (\ref{13a}),
and using $({\bf O(H\mathcal{R})O}^{-1})= ({\bf OHO}^{-1}){\bf \mathcal{R}}$
we conclude ${\bf OHO}^{-1}={\bf H}$
as stated. \quad$\Box$
\section{Application of the Covering Group}
Given $\mathfrak{V}$ and $\mathfrak{t}$, we are seeking a group $G$ such that the orbit of the group
elements applied to $\mathfrak{t}$ is just $\mathfrak{V}$, i.e. ${\mathfrak{V}}=G\backslash \mathfrak{t}$. We follow Buser's recipe
as given in Buser et al. (1994). The permutation representation of $G$ is obtained
through the following steps. If $\mathfrak{V}$ consists of $N$ copies of $\mathfrak{t}$, group $G$ will be
represented by permutations on $N$ letters. $G$ is constructed by means of $n_F$
generators. We enumerate the copies of $\mathfrak{t}$ from $1$ to $N$. We construct the first
generator from those copies that are adjacent along side $\alpha$, say,
$(i_{\alpha 1}, j_{\alpha 1}), (i_{\alpha 2}, j_{\alpha 2} ),\dots , (i_{\alpha m}, j_{\alpha m})$
make $a=(i_{\alpha 1}, j_{\alpha 1}), (i_{\alpha 2}, j_{\alpha 2} ),\dots , (i_{\alpha m}, j_{\alpha m})$
The procedure is repeated for each side, thus we obtain $n_F$ generators. $G$
is the group generated by the $n_F$ generators. That group permutates the $N$
nodes among each other. Since most finite groups can be presented on 2 generators,
this representation is quite general. When $n_F$ is even, we can reduce the number
of generators by numbering the faces of $\mathfrak{t}$ as $(\alpha, \beta, \dots)$ along
the first $n_F/2$ sides and using the second $n_F/2$ sides as "conjugated" sides, gluing side $\alpha$ to
side $\alpha$ conjugated.
{\em Example 1.} If the covering group has two- or three-dimensional conjugate classes,
the corresponding irreducible representations contain collective modes to be
determined over several nodes.
In this example, $\mathfrak{t}$ is an isosceles right triangle
and $\mathfrak{V}$ consists of 8 copies of $\mathfrak{t}$. $\mathfrak{V}$ is obtained with consecutive copies of $\mathfrak{t}$
glued sequentially along the hypotenuse ($\gamma$) and along another side ($\alpha$),
see Fig. 1.
In this case words can be written directly without resorting to a permutation
representation. The $8$ copies of $\mathfrak{t}$ are obtained by applying
$\gamma,\alpha\gamma, \gamma\alpha\gamma, \alpha\gamma\alpha\gamma,
\gamma\alpha\gamma\alpha\gamma, \alpha\gamma\alpha\gamma\alpha\gamma, \\
\gamma\alpha\gamma\alpha\gamma\alpha\gamma
$
and the identity element. These 8 elements form a group isomorphic to $D_4$.
There are $8$ internal boundaries, so in the solution of a general boundary
condition problem we have $8$ independent functions over $\mathfrak{t}$. The $8$ functions
are derived from $4$ functions over $\mathfrak{t}$, corresponding to even and odd functions
along sides $\gamma$ and $\alpha$. By means of the character table of group $D_4$,
any function $f(x)$ given for $x\in \mathfrak{V}$ can be decomposed into irreducible components
as
\begin{equation}
f_i(x)=\sum_{g \in D_4}\chi_i ^* (g) *f(g^{-1}x).
\end{equation}
Thus, the irreducible components of the solution in $\mathfrak{V}$ along any side of type
$\beta$ represent a linear combination of the boundary values along the $8$ external
faces of the $8$ copies of $\mathfrak{t}$ that make up $\mathfrak{V}$.
In the case of a Dirichlet problem, we have to solve equation (\ref{eq1})
over $\mathfrak{t}$ with the boundary condition solution being zero
along sides $\beta$. In this case $t={\mathfrak{V}}/G$ and $\mathfrak{t}$ has $3$
sides of which one is always an external boundary.
According to Proposition \ref{p3}, $Dim({\Vec \phi})=8$. Thus, the most
general boundary condition involves $8$ linearly independent solutions in a
tile $\mathfrak{t}$. There are four one dimensional representations of the group $D_4$,
the corresponding solutions obey the boundary conditions in Table 1.
\begin{table}[ht]
\label{t1} \begin{center}
\begin{tabular} {|c|c|c|}
\hline
Irrep &\multicolumn{2}{c|}{Boundary condition at} \\
& side $\alpha$&side $\gamma $ \\
\hline
$A_1$ &reflective&reflective\\
\hline
$A_2$ &black &black\\
\hline
$B_1$ &black &reflective\\
\hline
$B_2$ &reflective&black\\
\hline
\end{tabular}
\end{center}
\caption{Boundary conditions for 1D Irreps of symmetries of Fig. 1}
\end{table}
We use the term {\em reflective} for normal gradient equals zero, and {\em black}
for function equals zero on the boundary. There are two, two-dimensional irreps,
which are determined for two attached copies of $\mathfrak{t}$; hence, these values are fixed at
two $\alpha$ type faces and at a $\gamma$ type face, see Table 2.
\begin{table}[ht]
\label{t2}
\begin{center}
\begin{tabular} {|c|c|c|c|}
\hline Irrep &\multicolumn{3}{c|}{Boundary condition at} \\
& side $\alpha$&side $\gamma $ &side $\alpha$ \\
\hline
$E_1$ &black& None&reflective\\
\hline
$E_2$ &black &None&reflective \\
\hline
$E_3$ & reflective&reflective &black \\
\hline
$E_4$ &reflective&black&black\\
\hline
\end{tabular}
\caption{Boundary conditions for 2D Irreps of symmetries of Fig. 1}
\end{center}
\end{table}
{\em Example 2.} The covering group usually leads to a reduction in problem size.
To illustrate this, let us consider a square shaped tile and let $\mathfrak{V}$
be composed of two squares, see Fig. 2. The length of the side of the tile is $a$.
\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.5\textwidth]{fig2.eps}
\end{center}
\caption{ $\mathfrak{V}$ composed of two squares}
\end{figure}
Here node No. 2 can be obtained by a translation along the horizontal axis from
node No. 1, and $\mathfrak{V}$ is obtained by $mod 2$ addition. The covering group has $2$
elements and is isomorphic to the inversion group. In contrast to the previous
example, here the group elements map an internal side into an external one (sides $\beta$
and $\delta$) and vice versa. There is one internal side so in a Dirichlet problem
the solution is the same in the left and right squares. In the general case,
we decompose the prescribed value of the solution along the boundary into irreps
of the covering group and solve one boundary-value problem in one node for each
irrep. Let us consider the problem
\begin{equation*}
\Delta \Phi(x)+B^2 \Phi(x)=0, \quad x\in \mathfrak{V}.
\end{equation*}
Its solution is
$\Phi(x,y)=cos (\mu x) cos(\nu y)$
with $ \mu^2 +\nu^2=B^2 $.
Since the covering group is isomorphic to the inversion group, we decompose the
solution into irreducible representations of the covering group, i.e. into an
even and an odd component in $x$:
\begin{gather*}
\Phi_{\rm even}(x,y)=u_0 \frac{\cos (\mu x)} {\cos(\mu*a/2)}\cos(\nu y) \\
\Phi_{\rm odd}(x,y)=u_1 \frac{\sin(\mu x)} {\sin(\mu a/2)}\cos(\nu y).
\end{gather*}
If we choose
\begin{gather*}
u_0=\cos^2 (\mu*a/2) \\
u_1=\sin^2 (\mu*a/2),
\end{gather*}
the even and odd solutions are exact. Thus, we have reduced the solution of the
problem to a fraction of $\mathfrak{V}$ using the covering group.
{\em Example 3.} The covering group may introduce simplifications even in
asymmetric volumes. Notwithstanding, it is not trivial how to find the
covering group even for simple volumes.
To demonstrate this, we present an example after Gordon et al. (1992) and Buser et al. (1994).
In Fig. 3, $\mathfrak{V}$ is composed of $7$ isosceles right triangles. The edges of $\mathfrak{t}$
are labeled as $\alpha,\beta, \gamma$. Adjacent triangles are attached along the
appropriate edges, e.g. $7$ and $3$ share an $\alpha$ edge. As $\gamma$ is always
the hypotenuse, and at an edge only two types of side are incident, the types of
edges are unique in Fig. 3. To find the covering group, we follow Buser (1988).
We make the map ($\alpha \to a, \beta \to b$ and $\gamma \to c)$. Since along side
$\alpha$ we map nodes $7$ and $3$ into each other, as well as $6$ and $2$, the
permutation representations of $a, b$ and $c$ are readily available:
\begin{gather*}
a =( 7,3)(6,2) \\
b =(2,4)(3,5) \\
c =(5,6)(1,2).
\end{gather*}
\begin{figure}[t]
\begin{center}
\includegraphics[width=0.4\textwidth]{fig3.eps}
\end{center}
\caption{$\mathfrak{V}$ composed of 7 triangles}
\end{figure}
Group $G$, generated by $a, b$, and $c$ has $168$ elements (in group theoretic
calculations the GAP program was used, see GAP (1995)), and $G$ is isomorphic to
$SL(3,2)$ and $PSL(2,7)$. Let the subgroup $A=Stabilizer(G,1)$ be the stabilizer
of subvolume $1$, that subgroup has 24 elements. A coset representation of $G$
is
$$ G=\cup_{i=1} ^7 G_i = \cup_{i=1} ^7 A*u_i $$
where
\begin{gather*}
u_1=() \quad
u_2=(1,2)(5,6) \\
u_3=(1,3,2)(5,6,7) \quad
u_4=(1,4,2)(3,5,6) \\
u_5=(1,5,7,6,3,4,2) \quad
u_6=(1,6,3,7,5,4,2) \\
u_7=(1,7,4,2)(3,6).
\end{gather*}
The $u_i$ elements are transformed under the generators $a, b$ and $c$ into some $L_j$
if $u_i*s\in G_j$ for some $j$; and $s$ is a generator of $G$. In the following
table, indices $j$ of $u_i*s\in G_j$ are given for $s=a, b$ and $c$ and
$i=1,\dots ,7$:
which corresponds to Fig. 3. Gordon, et al. (1992) have shown that Fig. 3 can
also be considered as a Cayley graph of $G$.
\begin{table}[ht] \label{t3}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
$i$ & $u_i*a$ & $u_i*b$ & $u_i*c$ \\
\hline
1&1&1&2 \\
\hline
2&6&4&1 \\
\hline
3&7&5&3 \\
\hline
4&4&2&4 \\
\hline
5&5&3&6 \\
\hline
6&2&6&5 \\
\hline
7&3&7&7 \\
\hline
\end{tabular}
\end{center}
\caption{Coset indices for products $u_i*s$, for $s=a, b, c$}
\end{table}
\section{Isospectral Plane Manifolds}
Further computational applications
of isospectral, simply connected manifolds, depend on the ability to generate
such manifolds. Based on the relationship between the connectivity matrix
and the geometry matrix, we show that if ${\mathfrak{V}}_1$ and ${\mathfrak{V}}_2$
are volumes with
respective equivalent geometry matrices ${\bf C}_1$ and ${\bf C}_2$, then the
solutions of (\ref{eq1}) on the boundaries are also equivalent. The statement
is formulated in Lemma \ref{le2}.
\begin{lemma}\label{le2}
Let volumes ${\mathfrak{V}}_1$ and ${\mathfrak{V}}_2$ be such
that (a) Each consists of $N$ copies of tile $\mathfrak{t}$. There are the same number of
copies of $\mathfrak{t}$ in ${\mathfrak{V}}_1$ and ${\mathfrak{V}}_2$ which are filled with the same material. (b)
The associated geometry matrices take the form ${\bf H}_1={\bf C}_1\times
{\bf H}_{ij}+{\bf S}_1$ and ${\bf H}_2={{\bf C}}_2\times
{\bf H}_{ij}+{\bf S}_2$ , where ${\bf C}_1$ and ${\bf C}_2$ are the connectivity
matrices of order $N$, and ${\bf H}_{ij}$ are the edge connection matrices of
order $n_F$ introduced in connection with (\ref{eq13}). ${\bf S}_i,
i=1,2$ refer to the external boundary, they are diagonal block matrices of
order $N$, the order of each block being $n_F$. (c) Let ${{\bf C}}_2={\bf
T}{{\bf C}}_1{\bf T}^{-1}$ , and ${\bf \mathcal{R}}_2={\bf T}{\bf \mathcal{R}_1 T}^{-1}$,
where matrix ${\bf T}$ is of order $N$. (d) As to the
external boundaries, we assume ${\bf TS}_1 ={\bf S}_2 {\bf T}$. Then, from
\begin{equation}\label{eq20}
{\bf H}_1{\bf \mathcal{R}}_1 {\bf q}_1={\bf S}_1{\bf q}_1
\end{equation}
and
\begin{equation}\label{eq21}
{\bf H}_2{\bf \mathcal{R}}_2\left({\bf q}_2\right)={\bf S}_2\left({\bf q}_2 \right)
\end{equation}
it follows that ${\bf q}_2={\bf Tq}_1$.
\end{lemma}
{\em Proof}: From conditions (a), (b), (c) and (d), the geometry matrices are
equivalent:
${\bf H}_2={\bf TH}_1{\bf T}^{-1}$ and because of condition (a), the following
relationship holds for the response matrices: ${\bf \mathcal{R}}_2={\bf T\mathcal{R}}_1{\bf
T}^{-1}$. Now,
multiplying (\ref{eq20}) by $\bf T$ we get
\begin{equation}
{\bf TH}_1{\bf T}^{-1}{\bf T}{\bf \mathcal{R}}_1({\bf T}^{-1}{\bf T}){\bf q}_1=
{\bf TS}_1{\bf q}_1={\bf S}_2{\bf Tq}_1,
\end{equation}
where, in the last equation we have used condition (d). By means of the relationships
between the geometry matrices and the response matrices of ${\mathfrak{V}}_1$ and ${\mathfrak{V}}_2$, the above
equation becomes ${\bf H}_2{\bf \mathcal{R}}_2{\bf Tq}_1={\bf S}_2{\bf Tq}_1$,
from which we get ${\bf q}_2={\bf Tq}_1$ as stated. \quad$\Box$
According to Lemma \ref{le2}, two volumes are equivalent if their
connectivity matrices are similar and the geometry matrices contain the same
blocks. This means that the nodes in ${\mathfrak{V}}_1$ should match the nodes in ${\mathfrak{V}}_2$
with regard to the external and internal faces. Such volume pairs are
generated by group theoretic means Buser (1988), Brooks (1988), Gordon et
al. (1992). In such volume pairs, the solutions on every boundary of ${\mathfrak{V}}_1$
will be a linear combination of the boundary fluxes of ${\mathfrak{V}}_2$. Because of
(\ref{eq15}), this implies that the node functions in ${\mathfrak{V}}_1$ are linear
expressions of the node functions in ${\mathfrak{V}}_2$.
In a number of applications, it suffices to show that the dominant
eigenvalues are the same for some volumes ${\mathfrak{V}}_1$ and ${\mathfrak{V}}_2$ and the associated
eigenfunctions can be transformed into each other. If we know the solutions in $\mathfrak{V}_1$
and ${\mathfrak{V}}_2$ and there is a matrix transforming one solution into the other, the geometry-
and response matrices of ${\mathfrak{V}}_1$ and ${\mathfrak{V}}_2$ are also related.
\begin{lemma}\label{le3}
Let us consider
two volumes, ${\mathfrak{V}}_1$ and ${\mathfrak{V}}_2$, each consisting of $N$ copies of a tile $\mathfrak{t}$.
Let ${\mathfrak{V}}_1$ and ${\mathfrak{V}}_2$ have the same number of internal and external faces. If
the eigenvalue problem (\ref{eq13}) leads to
\begin{equation}\label{aa}
{\bf H}_i{\bf \mathcal{R}}_i {\bf q}_i={\bf S}_i{\bf q}_i, \quad i=1,2
\end{equation}
let the following relations hold between the solutions ${\underline \phi}_1$
and ${\underline \phi}_2$:
\begin{equation}\label{bb}
{\underline \phi}_1(x)={\bf U}{\underline \phi}_2(x),
\end{equation}
where $\bf U$ is invertible, furthermore,
\begin{equation}\label{cc}
{\bf S}_1{\bf U}{\bf q}_2={\bf VS}_2{\bf q}_2
\end{equation}
where $\bf V$ is invertible, then the eigenvalues of problem (\ref{eq13}) are
the same on ${\mathfrak{V}}_1$ and ${\mathfrak{V}}_2$ and the geometry- and response matrices of the
two problems are similar: ${\bf VH}_2={\bf H}_1{\bf U}$ and
${\bf \mathcal{R}}_1{\bf U}={\bf U\mathcal{R}}_2$.
\end{lemma}
{\em Proof}: First, from (\ref{bb}) letting $x$ tend to the boundary of
$\mathfrak{t}$
we get ${\bf q}_1={\bf U}{\bf q}_2$. Substituting this into
(\ref{aa}) with $i=1$ we get ${\bf H}_1{\bf \mathcal{R}}_1{\bf U} {\bf
q}_2={\bf S}_1{\bf U}{\bf q}_2$. Now using (\ref{cc}), we obtain
\begin{equation}
{\bf V}^{-1}{\bf H}_1{\bf \mathcal{R}}_1{\bf U} {\bf q}_2={\bf
S}_2{\bf U}{\bf q}_2.
\end{equation}
From this, we see
\begin{equation}
{\bf V}^{-1}{\bf H}_1{\bf UU}^{-1}{\bf \mathcal{R}}_1{\bf U}
{\bf q}_2= ({\bf V}^{-1}{\bf H}_1{\bf U})({\bf U}^{-1}{\bf \mathcal{R}}_1{\bf U})
{\bf q}_2 ={\bf H}_2{\bf \mathcal{R}}_2{\bf q}_2,
\end{equation}
with the
correspondence ${\bf H}_2={\bf V}^{-1}{\bf H}_1{\bf U}$ and ${\bf \mathcal{R}}_2={\bf
U\mathcal{R}}_1{\bf U}^{-1}, $ as stated. \quad$\Box$
Sunada (1985), Brooks (1988) and
Gordon et al. (1992) have introduced a systematic way of finding isospectral
shapes.
\begin{definition}\label{d8} \rm
Let $G$ be a finite group, and let $G_1$
and $G_2$ be subgroups of $G$. Then, $(G, G_1, G_2)$ is a
Sunada triple if the left $R[G]$-modules $R[G/G_1]$ and $R[G/G_2]$
determined by the $G$-sets $G/G_1$ and $G/G_2$ are orthogonally
isomorphic, where the inner products are those for which $G/G_1$ and
$G/G_2$ are orthogonal bases. Gordon et al. (1992).
\end{definition}
The Sunada condition is equivalent to the assertion that $G_1$ and
$G_2$ are almost conjugate subgroups of $G$, i.e., there is a bijection of
$G_1$ with $G_2$ carrying every element $\xi \in G_1$ to a
conjugate element $g\xi g^{-1}\in G_2$, where the conjugating element
$g$ may depend upon $\xi$.
\begin{theorem}(Sunada)\label{Sun}
Let $\mathfrak{M}$ be a compact Riemannian manifold, $G$ a
finite group acting on $\mathfrak{M}$ by isometries. Suppose that $(G,
G_1,G_2)$ is a Sunada triple, and that $G_1$ and $G_2$ act
freely on $\mathfrak{M}$. Then the quotient manifolds
$\mathfrak{M}_1=G_1\backslash \mathfrak{M}$ and $\mathfrak{M}_2=G_2\backslash \mathfrak{M}$ are
isospectral.
\end{theorem}
Based on a proof Berard (1992) of the Sunada
theorem, the requirement that $G_1$ and $G_2$ act freely, can be
removed.
\begin{theorem}[Berard] Let $\mathfrak{M}$ be a compact Riemannian manifold upon
which a finite group $G$ acts by isometries. Suppose that $(G, G_1,
G_2)$ is a Sunada triple. Then the quotient orbifolds
$\mathfrak{O}_1=G_1\backslash \mathfrak{M}$ and
$\mathfrak{O}_2=G_2\backslash \mathfrak{M}$ are isospectral.
If $\mathfrak{M}$ has a boundary, then $\mathfrak{O}_1$ and
$\mathfrak{O}_2$ are isospectral both with Dirichlet and Neumann boundary conditions.
\end{theorem}
We have to show that $\mathfrak{O}_1$ and $\mathfrak{O}_2$ satisfy the conditions
postulated in Lemma \ref{le3}. $\mathfrak{O}_1$ and $\mathfrak{O}_2$ consist of the
same number of copies of tile t, they have the same number of external faces
because there is a one-to-one relationship between the elements of $G_1$
and $G_2$. The $R[G]$ modules allow the construction of matrix $\bf U$.
\section{Concluding Remarks}
We have dealt with the solution of a linear elliptic equation in a finite volume
consisting of congruent nodes. In Section 4, we described the utilized basic concepts
and notations. The condition that the solution must be continuous along with its first derivative
gives an integral equation for the solution along the node boundaries.
The solution is given by means of the tile's Green's function. The
$\bf\mathcal{M}$ matrix
is factored into two components: the first component $\bf Q$ is a matrix, it
contains all information on the geometry of the investigated volume $\mathfrak{V}$ and
allows one to establish the number of independent node functions in the solution.
The second component associates an integral operator to every boundary and depends
only on the equation to be solved. In Section 5, we dealt with examples.
Example 1 illustrates the existence of collective modes when the covering group
has a multidimensional irrep. A collective mode spreads over several nodes and
its components are transformed into each other under an element of the covering
group. A detailed investigation of the covering group in the context of Quantum Mechanics
may result in a systematic
way of finding finite volumes in which the energy levels of electrons are the same.
In connection with {\em Example 2}, we demonstrated how the covering group reduces
the size of the problem. The asymmetric volume of {\em Example 3} also has a
covering group, the numerical solution is reducible to a part of the seven triangles.
In Section 6, we have formulated conditions for eigenvalue problems in volumes $\mathfrak{V}_1$
and $\mathfrak{V}_2$ to be isospectral. If the response and geometry matrices meet the stipulated
conditions, the solutions of the two problems can be transformed into each other.
The postulated conditions are consistent
with those of a few other known isospectral problems.
We presented a formulation of the boundary-value problem, which is applicable
in practice and capable of accommodating the connectivity matrix and the
covering group. This facilitates combining group- and graph theory with
numerical methods.
Graph- and group theory offers a means to make the investigation of boundary value
problems easier. The structure of the response matrix is similar to the structure of
the connectivity matrix, allowing us to find equivalent problems, see Section 6.
The covering group has made it possible to reduce the solution in an asymmetric
discretized volume. The structure of the covering group limits the achievable
reduction: The higher the dimension of the irreducible subspaces induced by
the covering group, the less reduction achieved.
Thus, some of the group theoretical techniques becomes applicable
to asymmetric volumes, as in Section 6.
\begin{thebibliography}{99} \frenchspacing
\bibitem{allgw92} E. L. Allgower, K. B\"ohmer, K. Georg and R. Miranda
(1993): Exploiting
Symmetry in Boundary Element Methods, SIAM J. Numer. Anal. {\bf 29},pp.
534--552
\bibitem{bab}
L. Babai(1995): Automorphism groups, isomorphism, reconstruction. Chapter 27 of the
Handbook of Combinatorics, R. L. Graham, M. Gr\"otschel, L. Lov\'asz, eds.,
North-Holland -- Elsevier, 1995, pp. 1447--1540
\bibitem{bro}
R. Brooks (1988): Constructing isospectral manifolds, Am. Math. Mon. {\bf 95},
pp. 823-839
\bibitem{bus}
P. Buser (1988): Cayley graphs and Planar Isospectral Domains, in: T. Sunada (Ed.):
Geometry and Analysis on Manifolds, Lect. Notes Math. vol. 1339, pp.64-77,
Springer, Berlin
\bibitem{doy}
P. Buser, J. Conway and P. Doyle (1994): Some Planar Isospectral Domains,
International Mathematics Research Notices, 1994, pp. 391-400
\bibitem{dia}
P. Diaconis (1990): Patterned Matrices, Proc. of Symposia in Applied Mathematics, {\bf 40},
pp. 37-58
\bibitem{dorn}
J. J. Dorning (1979): Modern Coarse Mesh Methods, A Development of the " '70's", p. 3-1, Proc. Conf.
Computational Methods in Nuclear Engineering, Williamsburgh, VA., US Department of Energy
\bibitem{Fas}
A. F\"assler (1976): Application of Group Theory to the Method of Finite Elements
for Solving Boundary Value Problems, Ph. D. Thesis No. 5696A, ETH Z\"urich
\bibitem{gap}
(GAP, 1995): M. Sch\"onert et al.: GAP-Groups, Algorithms and Programming, Lehrstuhl
f\"ur Mathematik, Rheinisch Westf\"alische Technische Hochschule, Aachen,
Germany.
\bibitem{gold}
M. Goldsmith (1963): Symmetries of Some Eigenfunctions Occurring in Reactor Analysis,
Nucl. Sci. Eng. {\bf 17}, 111--119
\bibitem{gww}
C. Gordon, D. Webb and S. Wolpert (1992): Isospectral Plane Domains and Surfaces via Riemannian Orbifolds, Invent. math. {\bf 110},
pp. 1-22
\bibitem{hamar}
G. J. Habetler and M. A. Martino (1961): Existence Theorems and Spectral
Theory for the Multigroup Diffusion Model, in: Proc. of the Eleventh Symposium in Applied
Mathematics of the American Mathematical Society, vol. XI., Nuclear Reactor Theory, American Mathematical Society, Providence, R. I.
\bibitem{kaw}
B. Kawohl (1998): Symmetry or Not? The Mathematical Intelligencer, {\bf 20},
16--24
\bibitem{kut}
J. R. Kuttler and V. G. Sigillito (1984): Eigenvalues of the Laplacian in Two Dimensions,
SIAM Review, {\bf 26}, 163--175
\bibitem{mak80}
M. Makai (1980): Symmetries and the Coarse-Mesh Method, Report EIR-414, Eidg. Institut f\"ur
Reaktorforschung W\"urenlingen
\bibitem{RMS}
M. Makai (1984): Response matrix of Symmetric Nodes, Nucl. Sci. Eng. {\bf 86}, 302--314
\bibitem{makar}
M. Makai and J. Arkuszewski (1981): A Hexagonal Coarshe-Mesh Programme Based on Symmetry
Considerations, Trans. Am. Nucl. Soc. {\bf 38}, 347--348
\bibitem{maor99a}
M. Makai and Y. Orechwa (1999): Symmetries of boundary-value problems in
mathematical physics, J. Math. Phys. {\bf 40}, 5247--5267
\bibitem{maor97}
M. Makai and Y. Orechwa (1997): Problem Decomposition and Domain Based Parallelism
Via Group Theoretic Principles, in: Proc. Int. Conf. on Mathematical Methods
and Supercomputing for Nuclear Applications, American Nuclear Society,
Saratoga (N.Y.), {\bf 2}, 1444--1453
\bibitem{Nieva}
R. Nieva and G. S. Christensen (1977): Symmetry Reduction of Reactor Systems,
Nucl. Sci. Eng. {\bf 64}, 791--796
\bibitem{stil}
John Stillwell (1993): Classical Topology and Combinatorial Group Theory, Springer,
New York
\bibitem{sun}
T. Sunada (1985): Riemannian Coverings and Isospectral Manifolds, Ann. Math.
{\bf 121}, pp. 248-277
\bibitem{theo}
A. Theophilou and P. Tsilimigras (1969): On the Application of Group Theory to the
Solution of Boundary Value Problems, Nukleonik, {\bf 12}, 280--285
\bibitem{wein}
A. M. Weinberg and H. C. Schweinler (1948): Theory of Oscillating Absorber in a Chain Reactor,
Phys. Rev. {\bf 74}, 851--862
\bibitem{wei}
Z. Weiss (1977): Some Basic Properties of the Response Matrix Equations,
Nucl. Sci. Eng. {\bf 63}, 457--478
\end{thebibliography}
\end{document}