text:
\begin{document}

\title{Optimal quasi-diagonal preconditioners for pseudodifferential operators of order minus two}
\date{\today}
\author{Thomas F\"{u}hrer}

\address{Facultad de Matem\'{a}ticas, Pontificia Universidad Cat\'{o}lica de Chile, Santiago, Chile}
\email{tofuhrer@mat.uc.cl \emph{(corresponding author)}, nheuer@mat.uc.cl}

\author{Norbert Heuer}

\thanks{{\bf Acknowledgment.}
This work was supported by CONICYT through FONDECYT projects 11170050 and 1150056}

\keywords{Pseudodifferential operator of negative order, diagonal scaling,
          additive Schwarz method, preconditioner, negative order Sobolev spaces}
\subjclass[2010]{65F35,
                 65N30

                 }

\begin{abstract}
  We present quasi-diagonal preconditioners for piecewise polynomial discretizations of
  pseudodifferential operators of order minus two in any space dimension.
  Here, quasi-diagonal means diagonal up to a sparse transformation.
  Considering shape regular simplicial meshes and arbitrary fixed polynomial degrees,
  we prove, for dimensions larger than one, that our preconditioners are asymptotically optimal.

  Numerical experiments in two, three and four dimensions confirm our results.
  For each dimension, we report on condition numbers for piecewise constant
  and piecewise linear polynomials.
\end{abstract}

\maketitle

\section{Introduction}
Let $A:\;H^{-1}(\Omega)\to H_0^1(\Omega)$ be a linear continuous and coercive operator, and
$f\in H_0^1(\Omega)$. Here, $\Omega\subset\R^n$ ($n\geq 2$) is a bounded connected polyhedral domain
with Lipschitz boundary, $H_0^1(\Omega)$ is the standard Sobolev space of $H^1(\Omega)$
functions with zero trace, and $H^{-1}(\Omega):=(H_0^1(\Omega))^*$ is its dual.
Considering the problem of finding $\phi\in H^{-1}(\Omega)$ such that
\begin{align} \label{prob}
  A\phi = f,
\end{align}
the finite element method (FEM) is a standard approach to approximate $\phi$. It consists in solving
the variational form of \cref{prob} in piecewise polynomial subspaces of $H^{-1}(\Omega)$.
The pseudodifferential operator $A$ is of order minus two and resulting linear systems are usually
ill conditioned.
For instance, using quasi-uniform meshes with elements of diameter $h$ and bounded polynomial
degrees, the FEM generates system matrices with spectral condition number growing like $O(h^{-2})$,
except specific basis functions are used, cf. Hsiao and Wendland
\cite[Corollary~2.1]{HsiaoW_81_ANL}, \cite[Remark~4]{HsiaoW_77_FEM}.
For a detailed analysis in the case of boundary integral operators, in particular considering locally
refined meshes, we refer to Ainsworth et al. \cite{amt99}.
Considering small mesh sizes $h$, there is an obvious need to use preconditioned
iterative solvers. In this paper, we show that very simple preconditioners yield uniformly
bounded condition numbers, for shape regular simplicial meshes in any space dimension
and for arbitrary, but fixed, polynomial degrees. Our preconditioners are diagonal up to
sparse transformations; we call them \emph{quasi-diagonal}.
We provide definitions and proofs for dimension $n\ge 2$. The one-dimensional case is ignored,
but can be deduced by straightforward simplifications.

Our interest in preconditioners for discretized operators of order minus two arose from our recent and
ongoing research. In~\cite{DPGplate} we proposed an ultraweak formulation of the
Kirchhoff--Love plate bending model where we consider two variables, the vertical deflection of the plate
and the bending moments. Both unknowns are taken in $L^2(\Omega)$, the standard Lebesgue space of
square integrable functions. In applications, also the shear force is a relevant quantity.
Being the divergence of the bending moments, it is generally not $L^2$-regular. Its natural
space is $H^{-1}(\Omega)^n$. Aiming at an approximation of the shear force, an efficient implementation
will require to study preconditioners in $H^{-1}(\Omega)$.

A second motivation is the approximation of obstacle problems by least-squares finite elements.
In~\cite{LSQobstacle}, a first-order reformulation with Lagrangian multiplier $\lambda$ was analyzed.
The functional to be minimized there, includes a residual term measured in the $L^2(\Omega)$ norm.
However, measuring the residual in the weaker (discrete) $H^{-1}(\Omega)$ norm (as in~\cite{BLP97,BP96}) ensures
optimal convergence orders for less regular solutions. This would lead to a different functional
\begin{align*}
   J_{-1}(u,\ssigma,\lambda) \simeq \norm{\nabla u}{}^2 + \norm{\ssigma}{}^2 + \norm{\lambda}{-1}^2,
   \quad (u,\ssigma,\lambda)\in H_0^1(\Omega)\times L^2(\Omega)^n\times H^{-1}(\Omega).
\end{align*}
An efficient implementation of a least-squares scheme for such a functional requires optimal preconditioners
for the $H^{-1}(\Omega)$ variable.

We note that the construction of preconditioners in Sobolev spaces of non-integer negative order is more
complicated than in $H^{-1}(\Omega)$. A standard case are weakly singular boundary integral operators
that are of order minus one. They are well posed as linear operators acting on $H^{-1/2}(\Gamma)$,
the dual space of the trace of $H^1(\Omega)$ when $\Gamma$ is the boundary of a sufficiently smooth
domain $\Omega$. Preconditioners consider a so-called coarse grid space and are of
two-level (or additive Schwarz) or multilevel type, see
\cite{TranS_96_ASM,HeuerST_98_MAS} for two-dimensional problems, and
\cite{Oswald_98_MNH,MundSW_98_TLM,Heuer_01_ApS,abemSolve} for problems in higher space dimensions.
Multigrid methods for two-dimensional problems have been analyzed in \cite{vonPetersdorffS_92_MSP},
and of algebraic construction in \cite{LangerPR_03_EPB}.
One has to note that in two-dimensions, where boundary integral operators live on curves,
the construction of preconditioners for weakly singular operators is equivalent to the one for
hypersingular operators, which are of opposite order, one.
Preconditioners constructed by using operators of opposite order have been proposed in
\cite{SteinbachW_98_CSE}. More recently, Stevenson and van Veneti\"e presented an abstract
theory for general negative orders and space dimensions based on the operator preconditioning framework, see~\cite{StevensonVanVenetiePrecond}.

In contrast to the aforementioned works, we consider simple (one-level) decompositions
of piecewise polynomials spaces of arbitrary (but fixed) order.
A key point is the decomposition of piecewise constants into the divergence of Raviart--Thomas basis functions.
We show that this decomposition is stable (in the sense of the additive Schwarz framework) in $H^{-1}(\Omega)$.
Since our decomposition includes only one-dimensional spaces and since the support of the Raviart--Thomas basis
functions is local, it follows directly from the additive Schwarz theory that the corresponding preconditioner is
quasi-diagonal in the following sense:
For piecewise constants our proposed preconditioner has the form
\begin{align*}
  \PRECmat^{-1} = \Imat \Dmat \Imat^t,
\end{align*}
where $\Dmat$ is a diagonal matrix and $\Imat$ is a sparse matrix.
Let $\Amat$ denote the Galerkin matrix of the operator $A$ discretized with piecewise constants. From our analysis it
follows that the condition number is uniformly bounded, i.e.,
\begin{align*}
  \kappa(\PRECmat^{-1}\Amat) \leq C_\mathrm{cond} < \infty,
\end{align*}
where the constant depends in general on $\Omega$, the dimension $n\in\N$, the polynomial degree $p\in\N_0$ and
the shape regularity of the underlying mesh.
We note that an optimal (local) multilevel diagonal preconditioner for the weakly singular integral operator
has been proposed in~\cite{abemSolve}.
It is based on the decomposition of piecewise constants into the surface divergence of Raviart--Thomas functions.

The remainder of this paper is as follows. Our discrete settings with definition of spaces,
subspace decompositions as well as the main results are formulated in the next section.
Specifically, Sobolev spaces and norms are recalled in \cref{sec:main:norm},
discrete spaces are defined in \cref{sec:main:discrete} along with collecting some norm relations,
and basic additive Schwarz settings are given in \cref{sec:abstract}. Subsequently, our
four principal results on bounded condition numbers are formulated in four steps,
namely for spaces of piecewise polynomials of degrees $p=0$ in $H^{-1}(\Omega)$ and $\widetilde H^{-1}(\Omega)$
(the dual of $H^1(\Omega)$), and for higher degrees in $H^{-1}(\Omega)$ and $\widetilde H^{-1}(\Omega)$,
respectively, in \cref{sec:decomp:Hm1,sec:decomp:tildeHm1,sec:decomp:Hm1:Pp,sec:decomp:tildeHm1:Pp}.
Proofs of the main results are given in \cref{sec:proof:Hm1,sec:proof:tildeHm1,sec:proof:Pp}.
For our numerical results we need explicit matrix representations of the preconditioners.
They are given in \cref{sec:matrix}. Finally, in \cref{sec:num}, we report on numerical experiments
in two, three and four space dimensions for piecewise constant and piecewise linear polynomials.
We study uniform refined meshes for all cases and locally refined meshes for the two-dimensional case.

In the appendix we give a proof of a technical result needed in the analysis.

Throughout, the notation $a\lesssim b$ means that there exists a constant $c>0$
such that $a\le cb$. The constant is independent of the underlying mesh under the assumption
of (uniform) shape regularity, but may depend on the polynomial degrees, the space dimension
and the domain $\Omega$.
The relation $a\simeq b$ means that $a\lesssim b$ and $b\lesssim a$.

\section{Main results}\label{sec:main}

\subsection{Sobolev spaces \& (semi-)norms} \label{sec:main:norm}
The boundary of the Lipschitz polyhedron $\Omega\subset \R^n$ ($n\geq 2$) is denoted by $\Gamma$,
and $\normal$ is the unit normal vector on $\Gamma$ pointing outside of $\Omega$.
For a non-empty open and connected subset $\omega\subseteq\Omega$, we denote the $L^2(\omega)$
scalar product and norm by $\ip\cdot\cdot_\omega$ and $\norm{\cdot}\omega$, respectively.
If $\omega=\Omega$ we skip the index, i.e., $\ip\cdot\cdot =
\ip\cdot\cdot_\Omega$ and $\norm\cdot{} =\norm{\cdot}\Omega$.
Furthermore, we also use the space $L_*^2(\omega) := \set{v\in L^2(\Omega)}{\ip{v}1_\omega=0}$.
For $m\in\N$, $H^m(\omega)$ denotes the standard Sobolev space of $m$ times weakly differentiable
functions, with norm $\norm{\cdot}{m,\omega}$.
Again, if $\omega=\Omega$, then $\norm{\cdot}{m} = \norm{\cdot}{m,\Omega}$.
We consider also fractional-order Sobolev spaces $H^{m+s}(\omega)$ ($m\in\N_0,s\in(0,1)$)
with (squared) Sobolev--Slobodetskij seminorm
\begin{align*}
  \snorm{v}{m+s,\omega}^2 := \sum_{|\boldsymbol{\alpha}|=m} \int_\omega\int_\omega
  \frac{|D^{\boldsymbol{\alpha}}v(x) - D^{\boldsymbol\alpha}v(y)|}{|x-y|^{n+2s}} \,dy\,dx
\end{align*}
and norm $\norm{\cdot}{m+s,\omega}^2 := \norm{\cdot}{m,\omega}^2 + \snorm{\cdot}{m+s,\omega}^2$.
For $m=0$ we identify $H^0(\omega) = L^2(\omega)$, and if $\omega=\Omega$, we skip the index.
For $s>0$, the dual spaces are $\widetilde H^{-s}(\omega) = (H^s(\omega))^*$ and
the duality pairing is given by the extended $L^2(\omega)$ scalar product.
The dual spaces are equipped with the norms
\begin{align*}
  \norm{\phi}{-s,\sim,\omega} := \sup_{0\neq v\in H^s(\Omega)} \frac{\ip{\phi}{v}}{\norm{v}{s,\omega}} \quad(s>0).
\end{align*}
For $s>0$, the spaces $H_0^s(\omega)$ are defined as the completion of $C_0^\infty(\Omega)$
with respect to the norm $\norm{\cdot}{s,\omega}$.
The dual spaces are denoted by $H^{-s}(\omega) := (H_0^s(\omega))^*$ with dual norms $\norm{\cdot}{-s,\omega}$.
In the special case $\omega=\Omega$ and $s=1$ we use the dual norm
\begin{align*}
  \norm{\phi}{-1} := \sup_{0\neq v\in H_0^1(\Omega)} \frac{\ip{\phi}v}{\norm{\nabla v}{}}.
\end{align*}
The scalar products in the dual spaces, inducing the norms $\norm{\cdot}{-1,\sim}$ and $\norm{\cdot}{-1}$,
are denoted by $\ip{\cdot}\cdot_{-1,\sim}$ and $\ip{\cdot}\cdot_{-1}$, respectively.

\subsection{Mesh \& discrete spaces} \label{sec:main:discrete}
Let $\TT$ denote a regular mesh of open $n$-simplices that cover $\Omega$, i.e.,
\begin{align*}
  \overline\Omega = \bigcup_{T\in\TT} \overline T.
\end{align*}
An open $n$-simplex $T\in\TT$ is the interior of the convex hull of $n+1$ different vertices
$\zz_{T,j}\in\R^n$ ($j=1,\dots,n+1$) that do not lie on the same hypersurface.
We say that $\TT$ is shape regular if there exists a positive constant $\gamma$ such that
\begin{align*}
  \max_{T\in\TT} \frac{\diam(T)^n}{|T|} \leq \gamma < \infty.
\end{align*}
Here, $|T|$ denotes the measure (volume) of $T\in\TT$.
By $\EE(T)$ we denote the set of all $n+1$ boundary simplices of $T$
(relatively open simplices made up of $n$ vertices of $T$). The elements $E\in\EE(T)$ are called facets.
The collection of all facets is denoted by $\EE = \EE(\TT) = \bigcup_{T\in\TT}\bigcup_{E\in\EE(T)} \{E\}$.
With $\EE^\Gamma$ we denote all facets in $\EE$ that are subsets of $\Gamma$, while
$\EE^\Omega := \EE\setminus \EE^\Gamma$ is the set of interior facets. For $T\in\TT$ we define the patch
\begin{align*}
  \patch(T) := \set{T'\in\TT}{\overline T' \cap \overline T \neq \emptyset}.
\end{align*}
The mesh-width function $h = h_\TT$ and the local mesh-width $h_T$ are given by
\begin{align*}
  h|_T := h_T := \diam(T) \quad\text{for all } T\in\TT.
\end{align*}
We note that $h_{T'}\simeq h_T$ for all $T'\in \patch(T)$,
and $h_E := \diam(E) \simeq h_T$ for all $E\in \EE(T)$, where the equivalence constants only depend on
the shape regularity of $\TT$.
For consistency we identify the patch $\patch(T)$ with the domain
$\mathrm{int}(\bigcup_{T'\in\patch(T)} \overline T')$ where needed, e.g., to refer to inner products on
patches as in $\ip\cdot\cdot_{\patch(T)}$.

Let $\PP^p(\TT)$ denote the space of $\TT$-elementwise polynomials of degree less than or equal to $p\in\N_0$.
Correspondingly, $\RT^0(\TT)$ is the lowest-order Raviart--Thomas space (basis functions are defined below).
The space $\PP^0(\TT)$ is equipped with the standard basis of characteristic functions
$\set{\chi_T}{T\in\TT}$, where
\begin{align*}
  \chi_T|_{T'} = \begin{cases}
    1 & \text{if } T'=T, \\
    0 & \text{else}.
  \end{cases}
\end{align*}
For $p\geq 1$, we denote $d(n,p):=\dim(\PP^p(T))$ (which is independent of $T\in\TT$), and let
\begin{align*}
  \set{\chi_T,\chi_{T,1},\chi_{T,2},\dots,\chi_{T,d(n,p)-1}}{T\in\TT}
\end{align*}
be a basis of $\PP^p(\TT)$ with $\supp\{\chi_{T,j}\}=\overline T$ and normalized by $\ip{\chi_{T,j}}1 = 0$
($T\in\TT$, $j\in \JJ := \{1,\cdots,d(n,p)-1\}$). Recall that
\begin{align*}
  d(n,p) = {p+n\choose p} = \frac{\prod_{j=1}^n (p+j)}{n!}.
\end{align*}
Throughout our analysis, we will make use of the inverse inequalities
\begin{align}\label{eq:invineq}
  \norm{h\phi}{} \lesssim \norm{\phi}{-1} \quad\text{and}\quad
  \norm{h\phi}{} \lesssim \norm{\phi}{-1,\sim} \quad\text{for all }
  \phi \in \PP^p(\TT),
\end{align}
see, e.g.,~\cite[Theorem~3.6]{ghs05} for a general case with $n=3$.
We stress the fact that these relations follow by simple scaling arguments.
The involved constants only depend on the shape regularity of $\TT$, $n\in\N$, and $p\in\N_0$.

For each $E\in \EE^\Omega$ there exist exactly two elements $T^\pm$ with $\overline T^+\cap \overline T^- = \overline
E$.
Furthermore, let $\pp_E^\pm\in \overline T^\pm$ denote the vertex of $T^\pm$ opposite to $E$ and let $\normal_E$ denote the
unit normal on $E$ pointing from $T^+$ to $T^-$.
If $E\in \EE^\Gamma$ then there is only one element $T\in\TT$ such that $E$ is a facet of $T$.
In such a case we write $T^+= T$, $T^-=\emptyset$ and note that $\normal_E$ points from $\Omega$ to the exterior,
i.e., $\normal_E$ coincides with the normal vector $\normal$ on $\Gamma$.
Let $|E|$ denote the (relative) measure of $E\in\EE$.
For $n\geq 2$ we define the Raviart--Thomas basis function
\begin{align*}
  \ppsi_E := \begin{cases}
    \pm \frac{|E|}{n|T^\pm|} \left(\xx - \pp_E^\pm\right) & \text{if } \xx \in T^+\cup T^-, \\
    0 & \text{else},
  \end{cases}
\end{align*}
and note that
\begin{align*}
  \div\ppsi_E = \begin{cases}
    \pm \frac{|E|}{|T^\pm|} & \text{if } \xx\in T^+\cup T^-, \\
    0 & \text{else}.
  \end{cases}
\end{align*}
The following scaling result on the Raviart--Thomas functions will be used several times.
\begin{lemma}\label{lem:scaling}
  It holds that
  \begin{alignat*}{2}
    \norm{\div\ppsi_E}{-1} &\leq \norm{\ppsi_E}{} \simeq h_E \norm{\div\ppsi_E}{}
    \lesssim \norm{\div\ppsi_E}{-1} &\quad&\text{for all } E\in\EE, \\
    \norm{\div\ppsi_E}{-1,\sim} &\leq \norm{\ppsi_E}{} \simeq h_E \norm{\div\ppsi_E}{}
    \lesssim \norm{\div\ppsi_E}{-1,\sim} &\quad&\text{for all } E\in\EE^\Omega.
  \end{alignat*}
  The involved constants only depend on the shape regularity of $\TT$ and $n$.
\end{lemma}
\begin{proof}
  By definition of the dual norm and integration by parts we see that
  \begin{align*}
    \norm{\div\ppsi_E}{-1} = \sup_{0\neq v\in H_0^1(\Omega)} \frac{\ip{\div\ppsi_E}{v}}{\norm{\nabla v}{}}
    = \sup_{0\neq v\in H_0^1(\Omega)} \frac{-\ip{\ppsi_E}{\nabla v}}{\norm{\nabla v}{}}
    \leq \norm{\ppsi_E}{}
  \end{align*}
  for all $E\in \EE$. If $E\in \EE^\Omega$ the same argument shows that
  \begin{align*}
    \norm{\div\ppsi_E}{-1,\sim} = \sup_{0\neq v\in H^1(\Omega)} \frac{\ip{\div\ppsi_E}{v}}{\norm{v}{1}}
    = \sup_{0\neq v\in H^1(\Omega)} \frac{-\ip{\ppsi_E}{\nabla v}}{\sqrt{\norm{\nabla v}{}^2+\norm{v}{}^2}}
    \leq \norm{\ppsi_E}{}.
  \end{align*}
  Furthermore, the equivalence $\norm{\ppsi_E}{} \simeq h_E \norm{\div\ppsi_E}{}$ follows by a simple scaling argument.
  Finally, note that $h_E\norm{\div\ppsi_E}{} \simeq \norm{h\div\ppsi_E}{}$. Together with the inverse
  inequality~\cref{eq:invineq} we conclude the proof.
\end{proof}

The following equivalence result in $L^2$ follows from the equivalence of norms in finite-dimensional
spaces and linear independence.
\begin{proposition}
  Let $T\in\TT$.
  If $\ppsi = \sum_{E\in\EE(T)} \alpha_E\ppsi_E$, then
  \begin{align*}
    \norm{\ppsi}{T}^2 \simeq \sum_{E\in\EE(T)} \norm{\alpha_E\ppsi_E}{T}^2,
  \end{align*}
  where the involved constants only depend on the shape regularity of $\TT$ and $n$.
  \qed
\end{proposition}

We recall that for $s>1/2$ the Raviart--Thomas projector $\Pi^\div : H^s(\Omega)^n \to \RT^0(\TT)$
is given by
\begin{align*}
  \Pi^\div\ssigma := \sum_{E\in\EE} \alpha_E \ppsi_E \quad\text{with}\quad \alpha_E := \frac{1}{|E|}
  \int_E \ssigma\cdot\normal_E \,ds_E.
\end{align*}
It holds the following local bound on the $L^2$ norm,
\begin{align}\label{eq:RT:localbound}
  \norm{\Pi^\div\ssigma}{T} \lesssim \norm{\ssigma}{T} + h_T^s\snorm{\ssigma}{s,T}.
\end{align}
Here, the involved constants only depend on the shape regularity of $\TT$, $n$ and $s\in(1/2,1]$.
Also recall the commutativity property $\Pi^0\div\ssigma = \div\Pi^\div\ssigma$ for sufficiently smooth $\ssigma$,
where $\Pi^0 : L^2(\Omega) \to \PP^0(\TT)$ is the $L^2(\Omega)$ projection.
These results can be found, e.g., in \cite[Chapter~2]{BoffiBrezziFortin} and easily extend to arbitrary space
dimensions.

\subsection{Additive Schwarz framework}\label{sec:abstract}
Let $\XX$ denote a finite-dimensional subspace of a Hilbert space $\HHH$ with norm $\norm\cdot{\HHH}$.
For an index set $\II$ let $\XX_i\subseteq \XX$ ($i\in\II$) denote subspaces of $\XX$ such that
we have the splitting
\begin{align}\label{eq:splitting:abstract}
  \XX = \sum_{i\in\II} \XX_i.
\end{align}
To this decomposition we associate the \emph{additive Schwarz norm} $\enorm\cdot_{\XX}$ given by
\begin{align}\label{eq:ASnorm:abstract}
  \enorm{x}_{\XX}^2 := \inf\set{\sum_{i\in\II} \norm{x_i}{\HHH}^2}{x_i\in \XX_i \text{ such that } x = \sum_{i\in\II} x_i}.
\end{align}
Central to the additive Schwarz framework is to establish a norm equivalence of the form
\begin{align}\label{eq:equiv:abstract}
  C^{-1} \enorm{x}_{\XX} \leq \norm{x}{\HHH} \leq C \enorm{x}_{\XX} \quad\text{for all }x\in \XX.
\end{align}
Having such an equivalence implies that one can define related additive Schwarz
preconditioners for elliptic problems in $\HHH$.
The condition numbers of the resulting preconditioned system matrices only depend on $C>0$.
This is well-known knowledge and we refer the interested reader to~\cite{oswald94,ToselliWidlund}.

\subsection{Subspace decomposition of $\PP^0(\TT)$ in $H^{-1}(\Omega)$}\label{sec:decomp:Hm1}
Set $\XX_E := \linhull\{\div\ppsi_E\}\subseteq \PP^0(\TT) =: \XX$.
We consider the splitting
\begin{align}\label{eq:splitting:Hm1}
  \XX = \sum_{E\in\EE} \XX_E
\end{align}
and the associated norm~\cref{eq:ASnorm:abstract}.
Noting that $\div(\RT^0(\TT)) = \PP^0(\TT)$ this shows that the sum on the right-hand side is indeed a decomposition of
$\PP^0(\TT)$.

Our first main result reads as follows.
\begin{theorem}\label{thm:Hm1}
  There exists $C>0$ which only depends on $\Omega$, $n$, and the shape regularity of $\TT$ such that
  \begin{align}\label{eq:equiv:Hm1}
    C^{-1} \enorm{\phi}_{\XX} \leq \norm{\phi}{-1} \leq C \enorm{\phi}_{\XX} \quad\text{for all }
    \phi \in \PP^0(\TT).
  \end{align}
\end{theorem}

\subsection{Subspace decomposition of $\PP^0(\TT)$ in $\widetilde H^{-1}(\Omega)$}\label{sec:decomp:tildeHm1}
Set $\XX_0 := \linhull\{1\}\subseteq \PP^0(\TT) =: \YY$.
We consider the splitting
\begin{align}\label{eq:splitting:tildeHm1}
  \YY = \XX_0 + \sum_{E\in\EE^\Omega} \XX_E
\end{align}
and the associated norm $\enorm\cdot_{\YY}$.
Again, the right-hand side of~\cref{eq:splitting:tildeHm1} defines a decomposition of
$\PP^0(\TT)$. A proof is omitted since it is implicitly contained in the proof of our second main result.
(In~\cref{sec:proof:tildeHm1}, a decomposition is constructed for any $\phi\in \PP^0(\TT)$.)
\begin{theorem}\label{thm:tildeHm1}
  There exists $C>0$ which only depends on $\Omega$, $n$, and the shape regularity of $\TT$ such that
  \begin{align}\label{eq:equiv:tildeHm1}
    C^{-1} \enorm{\phi}_{\YY} \leq \norm{\phi}{-1,\sim} \leq C \enorm{\phi}_{\YY} \quad\text{for all }
    \phi \in \PP^0(\TT).
  \end{align}
\end{theorem}

\subsection{Subspace decomposition of $\PP^p(\TT)$ in $H^{-1}(\Omega)$}\label{sec:decomp:Hm1:Pp}
Let $\XX_p := \PP^p(\TT)$, $\XX_{T,j} := \linhull\{\chi_{T,j}\}$. We consider the decomposition
\begin{align*}
  \XX_p = \sum_{E\in\EE} \XX_E + \sum_{T\in\TT} \sum_{j\in \JJ} \XX_{T,j} \quad\text{with associated norm }
  \enorm{\cdot}_{\XX_p}.
\end{align*}

\begin{theorem}\label{thm:Hm1:Pp}
  There exists $C>0$ which only depends on $\Omega$, $n$, $p$, and the shape regularity of $\TT$ such that
  \begin{align}\label{eq:equiv:Hm1:Pp}
    C^{-1} \enorm{\phi}_{\XX_p} \leq \norm{\phi}{-1} \leq C \enorm{\phi}_{\XX_p} \quad\text{for all }
    \phi \in \PP^p(\TT).
  \end{align}
\end{theorem}

\subsection{Subspace decomposition of $\PP^p(\TT)$ in $\widetilde H^{-1}(\Omega)$}\label{sec:decomp:tildeHm1:Pp}
There holds a similar decomposition:
\begin{align*}
  \YY_p = \XX_0  +  \sum_{E\in\EE^\Omega} \XX_E + \sum_{T\in\TT} \sum_{j\in \JJ} \XX_{T,j}
  \quad\text{with associated norm } \enorm{\cdot}_{\YY_p}.
\end{align*}

\begin{theorem}\label{thm:tildeHm1:Pp}
  There exists $C>0$ which only depends on $\Omega$, $n$, $p$, and the shape regularity of $\TT$ such that
  \begin{align}\label{eq:equiv:tildeHm1:Pp}
    C^{-1} \enorm{\phi}_{\YY_p} \leq \norm{\phi}{-1,\sim} \leq C \enorm{\phi}_{\YY_p} \quad\text{for all }
    \phi \in \PP^p(\TT).
  \end{align}
\end{theorem}

\section{Proof of~\cref{thm:Hm1}}\label{sec:proof:Hm1}
Before we come to the proof let us collect some auxiliary results.
Let $f\in L^2(\Omega)$ be given and let $u\in H_0^1(\Omega)$ denote the unique weak solution of the Poisson equation
\begin{align}\label{eq:dirichlet}
  -\Delta u = f \quad\text{in }\Omega \quad\text{and}\quad u|_\Gamma = 0.
\end{align}
From elliptic regularity theory \cite{grisvard,dauge88} we know that there exists a regularity shift
$s=s(\Omega)\in(1/2,1]$ such that
\begin{align}\label{eq:regularity}
  \norm{u}{1+r} \lesssim \norm{f}{-1+r} \quad\text{for all } r\in[0,s].
\end{align}
We need the following local regularity result.
Its proof follows along the argumentation given
in~\cite[Theorem~3.3]{AinsworthGuzmanSayas} with only minor modifications.
(The difference is that in~\cite{AinsworthGuzmanSayas} the authors consider the Poisson equation with $f=0$ and
non-trivial Neumann datum for $n=3$, whereas here we consider non-trivial $f$ and homogeneous Dirichlet datum for
$n\geq 2$. For completeness we give a proof in~\cref{app:localreg}.)
\begin{lemma}\label{lem:localreg}
  Let $f\in L^2(\Omega)$ and let $u\in H_0^1(\Omega)$ denote the solution of~\cref{eq:dirichlet}.
  It holds that
  \begin{align*}
    h_T^s \snorm{\nabla u}{s,T} \lesssim \norm{\nabla u}{\patch(T)} + h_T \norm{f}{\patch(T)}
    \quad\text{for all } T\in\TT.
  \end{align*}
  Here, the involved constant only depends on $\Omega$ and the shape regularity of $\TT$.
  \qed
\end{lemma}

\subsection{Proof of lower bound in~\cref{eq:equiv:Hm1}}
Let $\phi \in \PP^0(\TT)$ be given. Define $u\in H_0^1(\Omega)$ as the solution of~\cref{eq:dirichlet} with right-hand
side $f=-\phi$.
By~\eqref{eq:regularity} it holds that $u\in H^{1+s}(\Omega)$.
In particular $\ssigma:= \nabla u \in H^s(\Omega)^n$ and $\Pi^{\div}\ssigma$ is well defined.
Recall that
\begin{align*}
  \Pi^{\div}\ssigma = \sum_{E\in\EE} \alpha_E \ppsi_E, \text{ where }
  \alpha_E = \frac1{|E|}\int_E \ssigma\cdot\normal_E \,ds_E.
\end{align*}
We set $\phi_E := \alpha_E \div\ppsi_E \in \XX_E$. Observe that (using the commutativity property of $\Pi^{\div}$)
\begin{align*}
  \sum_{E\in\EE} \phi_E = \sum_{E\in\EE} \div(\alpha_E\ppsi_E) = \div(\Pi^{\div}\ssigma) = \Pi^0\div\ssigma = \phi.
\end{align*}
Then,~\cref{lem:scaling} shows that
\begin{align*}
  \sum_{E\in\EE} \norm{\phi_E}{-1}^2 &= \sum_{E\in\EE} \norm{\alpha_E\div\ppsi_E}{-1}^2 \leq
  \sum_{E\in\EE} \norm{\alpha_E\ppsi_E}{}^2 = \sum_{T\in\TT} \sum_{E\in\EE(T)} \norm{\alpha_E \ppsi_E}{T}^2 \\
  &\simeq \sum_{T\in\TT} \norm{\sum_{E\in\EE(T)}\alpha_E\ppsi_E}{T}^2 = \sum_{T\in\TT} \norm{\Pi^{\div}\ssigma}T^2.
\end{align*}
Using~\cref{eq:RT:localbound} together with~\cref{lem:localreg} we estimate the last term further by
\begin{align*}
  \sum_{T\in\TT} \norm{\Pi^{\div}\ssigma}T^2 &\lesssim \sum_{T\in\TT} \left(\norm{\ssigma}T^2 +
  h_T^{2s}\snorm{\ssigma}{s,T}^2 \right)
  \lesssim \norm{\nabla u}{}^2 +
  \sum_{T\in\TT} h_T^2\norm{\phi}{T}^2.
\end{align*}
A standard estimate gives $\norm{\nabla u}{} \leq \norm{\phi}{-1}$ and with the inverse inequality~\cref{eq:invineq},
i.e.,
\begin{align*}
  \sum_{T\in\TT} h_T^2\norm{\phi}{T}^2 \lesssim \norm{\phi}{-1}^2,
\end{align*}
we conclude the proof of the lower bound in~\cref{eq:equiv:Hm1}. \qed

\subsection{Proof of upper bound in~\cref{eq:equiv:Hm1}}
Let $\phi\in \PP^0(\TT)$ and let $\phi_E\in\XX_E$ be arbitrary such that $\phi = \sum_{E\in\EE} \phi_E$.
Note that we can write $\phi_E = \alpha_E \div\ppsi_E$. This shows that
\begin{align*}
  \phi = \div(\sum_{E\in\EE}\alpha_E\ppsi_E).
\end{align*}
Using $\norm{\div(\cdot)}{-1}\leq \norm{\cdot}{}$ we get
\begin{align*}
  \norm{\phi}{-1}^2 &\leq \norm{\sum_{E\in\EE}\alpha_E\ppsi_E}{}^2 = \sum_{T\in\TT}
  \norm{\sum_{E\in\EE(T)}\alpha_E\ppsi_E}T^2
  \lesssim \sum_{T\in\TT} \sum_{E\in\EE(T)} \norm{\alpha_E\ppsi_E}T^2 = \sum_{E\in\EE}\norm{\alpha_E\ppsi_E}{}^2.
\end{align*}
With the estimate
\begin{align*}
  \norm{\ppsi_E}{}\simeq h_T\norm{\div\ppsi_E}{} \lesssim \norm{\div\ppsi_E}{-1},
\end{align*}
see~\cref{lem:scaling}, we conclude the proof of the upper bound in~\cref{eq:equiv:Hm1}.
\qed

\section{Proof of~\cref{thm:tildeHm1}}\label{sec:proof:tildeHm1}
The proof follows similar ideas as in~\cref{sec:proof:Hm1}.
Instead of the Dirichlet problem~\cref{eq:dirichlet}, we consider the following Neumann problem.
Let $f\in L_*^2(\Omega)$ be given and let $u\in H^1(\Omega)\cap L_*^2(\Omega)$ denote the unique weak solution of the
Poisson problem
\begin{align}\label{eq:neumann}
  -\Delta u = f \quad\text{in }\Omega \quad\text{and}\quad \nabla u\cdot\normal|_\Gamma = 0.
\end{align}
We note that the regularity~\cref{eq:regularity} also holds true for solutions of~\cref{eq:neumann}.

As in~\cref{sec:proof:Hm1} the proof of the next result follows along the argumentation given
in~\cite[Theorem~3.3]{AinsworthGuzmanSayas}.

\begin{lemma}\label{lem:localreg:neumann}
  Let $f\in L_*^2(\Omega)$ and let $u\in H^1(\Omega)\cap L_*^2(\Omega)$ denote the solution of~\cref{eq:neumann}.
  It holds that
  \begin{align*}
    h_T^s \snorm{\nabla u}{s,T} \lesssim \norm{\nabla u}{\patch(T)} + h_T \norm{f}{\patch(T)}
    \quad\text{for all } T\in\TT.
  \end{align*}
  Here, the involved constant only depends on $\Omega$ and the shape regularity of $\TT$.
  \qed
\end{lemma}

Throughout the remainder of this section, let $\phi \in \PP^0(\TT)$ be given.
We consider the (unique) splitting $\phi = \phi_0 + \phi_*$ where $\phi_0 := \frac1{|\Omega|}\int_\Omega \phi \,dx$.
Clearly, $\int_\Omega \phi_* \,dx = 0$.
Observe that
\begin{align*}
  \norm{\phi_0}{-1,\sim} \lesssim \norm{\phi}{-1,\sim},
\end{align*}
hence,
\begin{align}\label{eq:splitting:const}
  \norm{\phi}{-1,\sim} \simeq \norm{\phi_0}{-1,\sim} + \norm{\phi_*}{-1,\sim},
\end{align}
where the involved constants only depend on $\Omega$.

\subsection{Proof of lower bound in~\cref{eq:equiv:tildeHm1}}
Define $u\in H^1(\Omega)\cap L_*^2(\Omega)$
as the solution of~\cref{eq:neumann} with right-hand
side $f=-\phi_*$.
By~\eqref{eq:regularity} we have that $u\in H^{1+s}(\Omega)$, where $s\in(1/2,1]$ denotes the regularity shift.
In particular, $\ssigma:= \nabla u \in H^s(\Omega)^n$ and $\Pi^{\div}\ssigma$ is well defined.
Recall that
\begin{align*}
  \Pi^{\div}\ssigma = \sum_{E\in\EE} \alpha_E \ppsi_E, \text{ where }
  \alpha_E = \frac1{|E|}\int_E \ssigma\cdot\normal_E \,ds_E.
\end{align*}
Note that $\ssigma\cdot\normal = \nabla u\cdot\normal = 0$ on the boundary $\Gamma$ and therefore,
$\alpha_E = 0$ for all $E\in\EE^\Gamma$.
We set $\phi_E := \alpha_E \div\ppsi_E \in \XX_E$. Observe that (using the commutativity property of $\Pi^{\div}$)
\begin{align*}
  \sum_{E\in\EE^\Omega} \phi_E = \sum_{E\in\EE^\Omega} \div(\alpha_E\ppsi_E) = \sum_{E\in\EE} \div(\alpha_E\ppsi_E)
  = \div(\Pi^{\div}\ssigma) = \Pi^0\div\ssigma = \phi_*.
\end{align*}
Then, keeping in mind that $\alpha_E=0$ for $E\in\EE^\Gamma$,~\cref{lem:scaling} yields
\begin{align*}
  \sum_{E\in\EE^\Omega} \norm{\phi_E}{-1,\sim}^2 &= \sum_{E\in\EE} \norm{\alpha_E\div\ppsi_E}{-1,\sim}^2 \leq
  \sum_{E\in\EE} \norm{\alpha_E\ppsi_E}{}^2 = \sum_{T\in\TT} \sum_{E\in\EE(T)} \norm{\alpha_E \ppsi_E}{T}^2 \\
  &\simeq \sum_{T\in\TT} \norm{\sum_{E\in\EE(T)}\alpha_E\ppsi_E}{T}^2 = \sum_{T\in\TT} \norm{\Pi^{\div}\ssigma}T^2.
\end{align*}
Using~\cref{eq:RT:localbound} together with~\cref{lem:localreg:neumann}
we can bound the last term as in~\cref{sec:proof:Hm1}.
Finally, with the equivalence~\cref{eq:splitting:const}
we conclude the proof of the lower bound in~\cref{eq:equiv:tildeHm1}.
\qed

\subsection{Proof of upper bound in~\cref{eq:equiv:tildeHm1}}
Let $\phi_E\in\XX_E$ be arbitrary such that $\phi_* = \sum_{E\in\EE^\Omega} \phi_E$.
Note that we can write $\phi_E = \alpha_E \div\ppsi_E$. This shows that
\begin{align*}
  \phi_* = \div(\sum_{E\in\EE^\Omega}\alpha_E\ppsi_E).
\end{align*}
Since $(\sum_{E\in\EE^\Omega}\alpha_E\ppsi_E)\cdot\normal = 0$ on $\Gamma$ it holds that
\begin{align*}
  \norm{\div\sum_{E\in\EE^\Omega}\alpha_E\ppsi_E}{-1,\sim}\leq \norm{\sum_{E\in\EE^\Omega}\alpha_E\ppsi_E}{}.
\end{align*}
Arguing as in~\cref{sec:proof:Hm1} together with the equivalence~\cref{eq:splitting:const} we finish the proof of the
upper bound in~\cref{eq:equiv:tildeHm1}.
\qed

\section{Proof of~\cref{thm:Hm1:Pp,thm:tildeHm1:Pp}} \label{sec:proof:Pp}
We only consider the proof of~\cref{thm:Hm1:Pp}. \cref{thm:tildeHm1:Pp} can be shown analogously.

\begin{lemma}\label{lem:L2proj}
  The $L^2(\Omega)$ projection $\Pi^0$ restricted to $\PP^p(\TT)$ is bounded in $H^{-1}(\Omega)$.
  In particular,
  \begin{align*}
    \norm{(1-\Pi^0)\phi}{-1}
    &\leq C_1 \norm{h(1-\Pi^0)\phi}{} \leq C_1\norm{h\phi}{} \leq C_1 C_2 \norm{\phi}{-1}, \\
    \norm{\Pi^0\phi}{-1} &\leq (1+C_1C_2)\norm{\phi}{-1}
  \end{align*}
  for all $\phi \in \PP^p(\TT)$,
  where $C_1,C_2$ only depend on the shape regularity of $\TT$ and $C_2$ also depends on $p\in\N_0$ and $n$.
\end{lemma}
\begin{proof}
  With the local approximation property $\norm{(1-\Pi^0)v}{T}\lesssim h_T\norm{\nabla v}T$ of the $L^2$ projector and the estimate
  $\norm{(1-\Pi^0)\phi}T\leq \norm{\phi}T$ we have
  \begin{align*}
    \norm{(1-\Pi^0)\phi}{-1} &= \sup_{0\neq v\in H_0^1(\Omega)} \frac{\ip{(1-\Pi^0)\phi}v}{\norm{\nabla v}{}}
    = \sup_{0\neq v\in H_0^1(\Omega)} \frac{\ip{(1-\Pi^0)\phi}{(1-\Pi^0)v}}{\norm{\nabla v}{}}
    \\
    &\lesssim \norm{h(1-\Pi^0)\phi}{} \leq \norm{h\phi}{}.
  \end{align*}
  The inverse inequality~\cref{eq:invineq} shows the first estimate.
  Using the triangle inequality we conclude the second estimate.
\end{proof}

\subsection{Proof of lower bound in~\cref{eq:equiv:Hm1:Pp}}
Let $\phi\in \PP^p(\TT)$ be given. We consider the $L^2$ orthogonal splitting
\begin{align*}
  \phi := \phi_0 + \phi_1 = \Pi^0\phi + (1-\Pi^0)\phi.
\end{align*}
From~\cref{thm:Hm1} we already know that we can split $\phi_0 = \sum_{E\in\EE} \phi_E$ such that
\begin{align*}
  \sum_{E\in\EE} \norm{\phi_E}{-1}^2 \lesssim \norm{\phi_0}{-1}^2 \lesssim \norm{\phi}{-1}^2,
\end{align*}
where for the last estimate we have used~\cref{lem:L2proj}.
The function $\phi_1$ is uniquely decomposed as
\begin{align*}
  \phi_1 = \sum_{T\in\TT} \sum_{j\in\JJ} \phi_{T,j} \quad\text{with } \phi_{T,j}\in \XX_{T,j}.
\end{align*}
Recall that $\ip{\phi_{T,j}}1 = 0$, hence, $\phi_{T,j} = (1-\Pi^0)\phi_{T,j}$ and with~\cref{lem:L2proj} we infer that
\begin{align*}
  \norm{\phi_{T,j}}{-1} \lesssim h_T\norm{\phi_{T,j}}{T}.
\end{align*}
Together with the inverse inequality~\cref{eq:invineq} we infer that
\begin{align*}
  \sum_{T\in\TT} \sum_{j\in\JJ} \norm{\phi_{T,j}}{-1}^2 \lesssim \sum_{T\in\TT} h_T^2 \sum_{j\in\JJ}
  \norm{\phi_{T,j}}{T}^2
 \simeq \sum_{T\in\TT} h_T^2 \norm{\sum_{j\in\JJ} \phi_{T,j}}{T}^2
 = \sum_{T\in\TT} h_T^2 \norm{\phi}{T}^2 \lesssim \norm{\phi}{-1}^2.
\end{align*}
The proof is finished by combining the estimates. \qed

\subsection{Proof of upper bound in~\cref{eq:equiv:Hm1:Pp}}
Let $\phi_E\in \XX_E$, $\phi_{T,j}\in\XX_{T,j}$ be given.
Set $\phi := \phi_0 + \phi_1 := \sum_{E\in\EE} \phi_E + \sum_{T\in\TT}\sum_{j\in\JJ}\phi_{T,j}$.
Observe that $\phi_0 = \Pi^0\phi$ and $\phi_1 = (1-\Pi^0)\phi$. From~\cref{thm:Hm1} we already know that
\begin{align*}
  \norm{\phi}{-1}^2 \lesssim \norm{\phi_0}{-1}^2 + \norm{\phi_1}{-1}^2
  \lesssim \sum_{E\in\EE} \norm{\phi_E}{-1}^2
  + \norm{\phi_1}{-1}^2.
\end{align*}
By~\cref{lem:L2proj} we get
\begin{align*}
  \norm{\phi_1}{-1}^2 &= \norm{(1-\Pi^0)\phi}{-1}^2
  \lesssim \norm{h(1-\Pi^0)\phi}{}^2
  = \sum_{T\in\TT} h_T^2 \norm{\phi_1}{T}^2 = \sum_{T\in\TT} h_T^2
  \norm{\sum_{j\in\JJ}\phi_{T,j}}{T}^2
  \\ &\simeq \sum_{T\in\TT} h_T^2
  \sum_{j\in\JJ} \norm{\phi_{T,j}}{T}^2
  \lesssim \sum_{T\in\TT} \sum_{j\in\JJ} \norm{\phi_{T,j}}{-1}^2,
\end{align*}
which concludes the proof.
\qed

\section{Matrix representation}\label{sec:matrix}
In this section we briefly discuss the matrix representation of the preconditioner associated
to the space decompositions given in~\cref{sec:main}.

We consider the splitting $\PP^0(\TT) = \sum_{E\in\EE} \XX_E$. The additive Schwarz operator $\AS : \PP^0(\TT) \to
\PP^0(\TT)$ is given by
$\AS = \sum_{E\in\EE} \AS_E$, where $\AS_E : \PP^0(\TT) \to \XX_E$ is the projection within
$H^{-1}(\Omega)$, i.e,
\begin{align*}
  \ip{\AS_E\phi}{\phi_E}_{-1} = \ip{\phi}{\phi_E}_{-1} \quad\text{for all } \phi_E\in \XX_E.
\end{align*}
Let $\ASmat_E$, $\ASmat$, $\GALmat_E$, $\GALmat$ denote the matrix representations of $\AS_E$, $\AS$,
$\ip\cdot\cdot_{-1}$ on $\XX_E$, and $\ip\cdot\cdot_{-1}$ on $\PP^0(\TT)$, respectively.
Moreover, let $\Imat_E$ denote the matrix form of the canonical embedding $\XX_E \to \PP^0(\TT)$.
Then, following standard references (e.g.,~\cite[Chapter~2]{ToselliWidlund}) simple calculations show that
\begin{align*}
  \GALmat_E \ASmat_E = \Imat_E^t \GALmat \quad\text{or equivalently}\quad
  \ASmat_E = \GALmat_E^{-1} \Imat_E^t \GALmat,
\end{align*}
and the overall matrix representation is
\begin{align*}
  \ASmat = \sum_{E\in\EE} \Imat_E \GALmat_E^{-1} \Imat_E^t \GALmat =: \overline\PRECmat^{-1} \GALmat.
\end{align*}
The theory on additive Schwarz operators, together with~\cref{thm:Hm1}, shows that the condition number of
$\ASmat$ is uniformly bounded, that is, $\overline\PRECmat$ and $\GALmat$ are spectrally equivalent.
Note that the dimension of the spaces $\XX_E$ is one so that $\GALmat_E$ is just a scalar.
We can rewrite the preconditioner matrix $\overline\PRECmat$ as
\begin{align*}
  \overline\PRECmat^{-1} = \Imat \overline\Dmat \Imat^t,
\end{align*}
where the $j$-th column of $\Imat \in \R^{\#\TT \times \#\EE}$ is given by $\Imat_{E_j}$ and $\overline\Dmat\in \R^{\#\EE\times
\#\EE}$ is the diagonal matrix
with entries $\overline\Dmat_{jk} = \delta_{jk} \norm{\div\ppsi_{E_j}}{-1}^{-2}$.

Note that $\div\ppsi_E$ has support on at most two elements, i.e., with the notation from~\cref{sec:main},
\begin{align*}
  \div\ppsi_E =
  \begin{cases}
    \frac{|E|}{|T^+|} \chi_{T^+} - \frac{|E|}{|T^-|} \chi_{T^-} & \text{if } E\in \EE^\Omega
    \text{ where } E = \overline{T^+}\cap\overline{T^-}, \\
    \frac{|E|}{|T|} \chi_{T} &\text{if } E\in \EE^\Gamma \text{ where } E\subset \partial T.
  \end{cases}
\end{align*}
This means that each column of $\Imat$ has at most two non-zero entries and, thus, $\Imat$ is a sparse matrix.

Note that $\norm{\div\ppsi_E}{-1}$ is not computable in general. However, thanks to the additive Schwarz theory,
we can replace $\overline\Dmat$ by a matrix $\Dmat$ with equivalent entries.
By~\cref{lem:scaling} it holds that
\begin{align*}
  \norm{\div\ppsi_E}{-1} \simeq \norm{\ppsi_E}{} \simeq |T|^{1/2} \simeq \diam(E)^{n/2} \simeq |E|^{n/(2(n-1))}.
\end{align*}
Defining $\Dmat_{jk} = \delta_{jk} |E_j|^{-n/(n-1)}$, this leads to the preconditioner
\begin{align*}
  \PRECmat^{-1} := \Imat \Dmat \Imat^t.
\end{align*}
It is spectrally equivalent to $\overline\PRECmat^{-1}$. Therefore, the condition number of
$\PRECmat^{-1}\GALmat$ is uniformly bounded.

The very same approach can be used to define a preconditioner associated to the splitting
\begin{align*}
  \PP^0(\TT) = \XX_0 + \sum_{E\in\EE} \XX_E,
\end{align*}
considered in~\cref{sec:decomp:tildeHm1}.
Given the diagonal matrix $\widetilde\Dmat\in \R^{\#\EE^\Omega\times \#\EE^\Omega}$
with entries $\widetilde\Dmat_{jk}= \delta_{jk}|E_j|^{-n/(n-1)}$ (here, $E_j\in\EE^\Omega$),
and the constant vector $\onevec\in \R^{\#\TT\times 1}$ (with $\onevec_j = 1$), define
\begin{align*}
  \widetilde\PRECmat^{-1} = \alpha \onevec \onevec^t + \widetilde\Imat \widetilde\Dmat \widetilde\Imat^t,
\end{align*}
where the columns of $\widetilde \Imat \in \R^{\#\TT\times\#\EE^\Omega}$ are given by $\Imat_E$ ($E\in\EE^\Omega$).
The constant $\alpha\simeq 1$ can be freely chosen. Then, $\widetilde\PRECmat$ is an optimal preconditioner for the
Galerkin matrix of $\ip{\cdot}\cdot_{-1,\sim}$ on $\PP^0(\TT)$.
Note that the matrix $\onevec \onevec^t$ is fully populated. However, in practical situations we are only interested in
the application of $\widetilde\PRECmat^{-1}$ to a vector $\mathbf{x}$, which can be implemented efficiently since
$\onevec\onevec^t$ has rank one.

Finally, for the higher order case from~\cref{sec:decomp:Hm1:Pp}, we define the preconditioner matrix
\begin{align*}
  \PRECmat_p^{-1} = \begin{pmatrix}
    \PRECmat^{-1} & \mathbf{0} \\
    \mathbf{0} & \Dmat^{(p)}
  \end{pmatrix},
\end{align*}
where, with $N_p := (d(n,p)-1)\#\TT$, $\Dmat^{(p)} \in \R^{N_p\times N_p}$ is a diagonal matrix.
Its entries are given by $(|T|^{1/n}\norm{\chi_{T,j}}{})^{-2}$ (with some appropriate ordering of the basis
functions).

The preconditioner matrix for the splitting considered in~\cref{sec:decomp:tildeHm1:Pp} reads
\begin{align*}
  \widetilde\PRECmat_p^{-1} = \begin{pmatrix}
    \widetilde\PRECmat^{-1} & \mathbf{0} \\
    \mathbf{0} & \Dmat^{(p)}
  \end{pmatrix},
\end{align*}
which can be obtained with the same argumentation.

\section{Experiments} \label{sec:num}
In this section we present some experiments with $p=0,1$ and $n=2,3,4$ on uniformly and locally refined meshes.
In order to show that our proposed preconditioners from~\cref{sec:matrix} lead to uniformly bounded condition numbers we
need a mechanism to produce the $H^{-1}(\Omega)$ and $\widetilde H^{-1}(\Omega)$ norms.
Here, we consider the discrete $H^{-1}$ inner product from the seminal work~\cite{BLP97} (which can be extended to
locally refined meshes, see~\cref{sec:discreteHm1norm}).

The condition numbers $\kappa(\cdot)$ which are displayed in the figures are
obtained as follows. We use the power iteration (resp., inverse power iteration) to approximate
the largest (resp., smallest) eigenvalue of a matrix
(which is symmetric with respect to some inner product)
and then report on the condition number of that matrix as the ratio of the approximated extreme eigenvalues.

\subsection{Discrete $H^{-1}(\Omega)$ and $\widetilde H^{-1}(\Omega)$ norms}\label{sec:discreteHm1norm}
Let $\widetilde Q : L^2(\Omega) \to \PP^1(\TT)\cap H_0^1(\Omega)$ denote the $L^2(\Omega)$
projection. Given that $\widetilde Q$ is bounded, and
\[
   \norm{\nabla \widetilde Q v}{} \lesssim \norm{\nabla v}{}
   \quad\text{and}\quad
   \norm{(1-\widetilde Q)v}{T} \lesssim \norm{h_T\nabla v}{\patch(T)}
   \quad \forall v\in H_0^1(\Omega)
\]
(see, e.g., \cite{KPP13} for locally refined meshes under consideration) we follow~\cite{BLP97}.
First, observe that for $\phi\in \PP^p(\TT)$
\begin{align*}
  \norm{(1-\widetilde Q)\phi}{-1} = \sup_{0\neq v\in H_0^1(\Omega)}
  \frac{\ip{(1-\widetilde Q)\phi}{v}}{\norm{\nabla v}{}}
  = \sup_{0\neq v\in H_0^1(\Omega)}
  \frac{\ip{\phi}{(1-\widetilde Q)v}}{\norm{\nabla v}{}} \lesssim \norm{h\phi}{}.
\end{align*}
Second, define $u[\phi] \in \PP^1\cap H_0^1(\Omega)$ by
\begin{align*}
  \ip{\nabla u[\phi]}{\nabla v} = \ip{\phi}{v} \quad\text{for all }v\in \PP^1(\TT)\cap H_0^1(\Omega).
\end{align*}
Third, using boundedness we get
\begin{align*}
  \norm{\widetilde Q\phi}{-1} &= \sup_{0\neq v\in H_0^1(\Omega)} \frac{\ip{\widetilde Q\phi}{v}}{\norm{\nabla v}{}}
  = \sup_{0\neq v\in H_0^1(\Omega)} \frac{\ip{\phi}{\widetilde Qv}}{\norm{\nabla v}{}}
  = \sup_{0\neq v\in H_0^1(\Omega)} \frac{\ip{\nabla u[\phi]}{\nabla \widetilde Qv}}{\norm{\nabla v}{}}
  \lesssim \norm{\nabla u[\phi]}{}.
\end{align*}
Then,
\begin{align*}
  \norm{\phi}{-1}^2 \lesssim \norm{\widetilde Q \phi}{-1}^2 + \norm{(1-\widetilde Q)\phi}{-1}^2
  \lesssim \norm{\nabla u[\phi]}{}^2 + \norm{h\phi}{}^2 \lesssim \norm{\phi}{-1}^2,
\end{align*}
where in the last step we have used that $\norm{\nabla u[\phi]}{} \leq \norm{\phi}{-1}$ and the inverse
inequality~\cref{eq:invineq}.
Now let $\eta_j$ denote the nodal basis functions of $\PP^1(\TT)\cap H_0^1(\Omega)$ and let $\chi_k$ denote
the basis functions of $\PP^p(\TT)$, where $\chi_k = \chi_{T_k}$ for $k=1,\dots,\#\TT$.
We replace the mesh-width function $h$ by the equivalent function $\widetilde h$ given elementwise by $\widetilde h|_T
:= |T|^{1/n}$.
Defining the matrices
\begin{align*}
  \Mmat_{j\ell} := \ip{\chi_k}{\eta_j}, \quad \Rmat_{jk} := \ip{\nabla \eta_j}{\nabla \eta_k},
  \quad \Lmat_{\ell m} := \ip{\widetilde h^2\chi_\ell}{\chi_m}
\end{align*}
($j,k = 1,\dots,\dim(\PP^1(\TT)\cap H_0^1(\Omega))$, $\ell,m=1,\dots,d(n,p)\#\TT$) and
relating $\phi\in \PP^p(\TT)$ with $\mathbf{x}\in \R^{d(n,p)\#\TT\times 1}$ by
$\phi = \sum_{j=1}^{d(n,p)\#\TT} \mathbf{x}_j \chi_j$,
our considerations above yield
\begin{align*}
  \mathbf{x}^t (\Mmat^t\Rmat^{-1}\Mmat + \Lmat)\mathbf{x} =
  \norm{\nabla u[\phi]}{}^2 + \norm{\widetilde h\phi}{}^2 \simeq
  \norm{\nabla u[\phi]}{}^2 + \norm{h\phi}{}^2 \simeq
  \norm{\phi}{-1}^2.
\end{align*}
Therefore, we replace the matrix $\GALmat$ from~\cref{sec:matrix} by the computable matrix
\begin{align*}
  \GALmat := \Mmat^t\Rmat^{-1}\Mmat + \beta \Lmat,
\end{align*}
where $\beta\simeq 1$ can be chosen freely.

Following the same argumentation (with obvious modifications) we replace $\widetilde\GALmat$ from~\cref{sec:matrix}
with the matrix
\begin{align*}
  \widetilde\GALmat := \widetilde\Mmat^t\widetilde\Rmat^{-1}\widetilde\Mmat + \beta \Lmat.
\end{align*}
Here,
\begin{align*}
  \widetilde\Mmat_{j\ell} := \ip{\chi_\ell}{\eta_j}, \quad
  \widetilde\Rmat_{jk} := \ip{\nabla \eta_j}{\nabla \eta_k} + \ip{\eta_j}{\eta_k}
\end{align*}
($j,k=1,\dots,\dim(\PP^1(\TT)\cap H^1(\Omega))$, $\ell = 1,\dots,d(n,p)\#\TT$) where
$\eta_j$ now refers to the nodal basis functions of $\PP^1(\TT)\cap H^1(\Omega)$.

\subsection{Condition numbers for $n=2$}

\begin{figure}
  \begin{center}
    \input{Cond2D}
  \end{center}
  \caption{Condition numbers for $n=2$ and $p=0$ (upper panel) resp. $p=1$ (lower panel).
  The left column corresponds to uniform refinements and the right one to local refinements. The results shown
  correspond to the decompositions from~\cref{sec:decomp:Hm1,sec:decomp:Hm1:Pp}.}
  \label{fig:2d}
\end{figure}

\begin{figure}
  \begin{center}
    \input{Cond2Dtilde}
  \end{center}
  \caption{Condition numbers for $n=2$ and $p=0$ (upper panel) resp. $p=1$ (lower panel).
  The left column corresponds to uniform refinements and the right one to local refinements. The results shown
  correspond to the decompositions from~\cref{sec:decomp:tildeHm1,sec:decomp:tildeHm1:Pp}.}
  \label{fig:2d:tilde}
\end{figure}

\begin{figure}
  \begin{center}
    \input{Cond3D}
  \end{center}
  \caption{Condition numbers for $n=3$ and uniform refinement.
  The upper panel corresponds to $p=0$, the lower panel to $p=1$.}
  \label{fig:3d}
\end{figure}

\begin{figure}
  \begin{center}
    \input{Cond4D}
  \end{center}
  \caption{Condition numbers for $n=4$ and uniform refinement.
  The upper panel corresponds to $p=0$, the lower panel to $p=1$.}
  \label{fig:4d}
\end{figure}

We consider the L-shaped domain $\Omega := (-1,1)^2\setminus (-1,0]^2$ with an initial triangulation of $12$ elements
of the same area.
Our refinement method is the newest vertex bisection (NVB). Uniform refinement means that we bisect each triangle twice
such that each father triangle is divided into four son elements.
To obtain some ``realistic'' locally refined meshes, we define $w(r,\varphi) := r^{2/3}\cos(2/3\varphi-\pi/6)$
with polar coordinates $(r,\varphi)$ centered at the origin.
This function has a singular behavior at the reentrant
corner of the domain $\Omega$ and corresponds to singularities of the Laplacian.
We compute the error indicators
\begin{align*}
  \mu(T) := \norm{(1-Q)w}{1,T}^2,
\end{align*}
where $Q: L^2(\Omega) \to \PP^1(\TT)\cap H^1(\Omega)$ denotes the $L^2(\Omega)$ projection.
A set (of minimal cardinality) $\MM\subseteq\TT$ is determined using the bulk criterion
\begin{align*}
  \frac14 \sum_{T\in\TT} \mu(T) \leq \sum_{T\in\MM} \mu(T).
\end{align*}
Then, $\TT$ is refined based on the set of marked elements $\MM$ using NVB. Further details on NVB can be found, e.g.,
in~\cite{KPP13,stevenson:NVB}.

The diagonal matrix $\mathbf{C}$ is defined as
\begin{align*}
  \mathbf{C}_{jk} := \delta_{jk} |T_j|^2.
\end{align*}
This choice is (up to some logarithmic factors) equivalent to  $\norm{\chi_j}{-1}^2 \simeq \norm{\chi_j}{-1,\sim}^2$ for
sufficiently small $|T_j|$, see~\cite[Theorem~4.8]{amt99} for the scaling of basis functions in negative order Sobolev
norms.
We skipped the logarithmic factors since using them did not improve condition numbers.
For $p=1$ we use the matrix
\begin{align*}
  \mathbf{C}_1^{-1} := \begin{pmatrix}
    \mathbf{C}^{-1} & 0 \\
    0 & \Dmat^{(1)}
  \end{pmatrix}
\end{align*}
as diagonal preconditioner.

For the implementation of the matrices $\widetilde\PRECmat^{-1}$, $\GALmat$ and $\widetilde\GALmat$ we have set
the parameters to $(\alpha,\beta) = (1/100,1/10)$. We found that with this choice our proposed preconditioners lead to
reasonably small condition numbers for different examples (not reported here).
Nevertheless, one might find other values $(\alpha,\beta)$ that even lead to smaller condition numbers.

\Cref{fig:2d,fig:2d:tilde} show the condition numbers for uniform (left) and local refinements (right) for $p=0$ (upper panel) and $p=1$
(lower panel), respectively.
The diagonal preconditioner in the case of local refinements delivers --- as expected, see, e.g.,~\cite{amt99}, ---
condition numbers comparable to the case of uniform refinement. (More precisely, it is
shown in~\cite{amt99} that the condition number of diagonally preconditioned systems like those considered here only
depend on the number of elements up to some possible logarithmic factors.)
In all configurations our proposed preconditioners lead to quite small condition numbers, even on locally refined meshes, which confirms our
theoretical results.

\subsection{Condition numbers for $n=3$}

In this section we consider a similar problem in 3D where $\Omega = \{(-1,1)^2\setminus(-1,0]\}\times(0,1)$ is an L-shaped
domain. We start with a triangulation of 24 tetrahedrons.
The diagonal preconditioner matrix is now defined as
\begin{align*}
  \mathbf{C}_{jk} := \delta_{jk} |T_j|^{5/3}.
\end{align*}
The meshes are refined using the red refinement rule.
(Now a uniform refinement corresponds to the division of one tetrahedra into eight tetrahedrons.)

From~\cref{fig:3d} we observe a similar behavior as in the case $n=2$.
In particular, we see that our proposed preconditioners lead to quite small condition numbers (the parameters
$\alpha,\beta$ are chosen as in the case $n=2$).

\subsection{Condition numbers for $n=4$}
We consider the unit 4-cube $\Omega = (0,1)^4$ which is divided into 24 simplices (Kuhn's triangulation,
see~\cite{Bey00}). The diagonal preconditioner matrix is now defined with entries
\begin{align*}
  \mathbf{C}_{jk} := \delta_{jk} |T_j|^{3/2}.
\end{align*}
We use Freudenthal's algorithm (see also~\cite{Bey00})
to obtain uniform refined regular meshes. (Each simplex is decomposed into 16 subsimplices.)
We choose $\alpha=\tfrac1{10}=\beta$.
Results are shown in~\cref{fig:4d} for $p=0$ and $p=1$. Again, they appear to confirm our prediction
of bounded condition numbers.

\appendix
\section{Proof of~\cref{lem:localreg}}\label{app:localreg}
We follow exactly the same ideas and lines of proof as in~\cite[Appendix~A]{AinsworthGuzmanSayas} adapted to our
situation (with volume force but homogeneous boundary conditions) and notation.

Throughout fix $T\in\TT$ and let $\cutoff\in C^\infty(\patch(T))$ denote a cut-off function with the properties
\begin{subequations}
\begin{align}
  \cutoff|_T &= 1,  \qquad
  \cutoff|_{\Omega\setminus\patch(T)} = 0, \\
  \norm{D^m \cutoff}{L^\infty(\patch(T))} & \lesssim h_T^{-m}, \quad\text{for } m=0,1,2.
\end{align}
\end{subequations}

Let $u\in H_0^1(\Omega)$ denote the solution of~\cref{eq:dirichlet} with datum $f\in L^2(\Omega)$.
Let $s = s(\Omega)\in(1/2,1]$ denote the regularity shift. Then, by~\cref{eq:regularity} we have that
\begin{align}\label{eq:app:reg}
  \norm{u}{1+s,T} \leq \norm{\cutoff u}{1+s,\patch(T)} = \norm{\cutoff u}{1+s}
  \lesssim \norm{\Delta(\cutoff u)}{-1+s},
\end{align}
since $\cutoff u|_\Gamma = 0$ and $\Delta(\cutoff u)\in L^2(\Omega)$.

We consider the case where $|\partial \patch(T)\cap \Gamma| = 0$.
Then, $\nabla(\cutoff u)\cdot\normal = 0$ on $\Gamma$. Let $v\in H^{1-s}(\Omega)$.
Using $v_{\patch(T)} := |\patch(T)|^{-1} \int_{\patch(T)} v \,dx$ and the product rule
\begin{align}\label{eq:app:prodrule}
  \Delta(\cutoff u) = u\Delta \cutoff + 2\nabla \cutoff\cdot\nabla u -\cutoff f,
\end{align}
we infer that
\begin{align*}
  \ip{\Delta(\cutoff u)}{v} &= \ip{\Delta(\cutoff u)}{v-v_{\patch(T)}}
  = \ip{\Delta(\cutoff u)}{v-v_{\patch(T)}}_{\patch(T)} \\
  &= \ip{u\Delta \cutoff + 2\nabla\cutoff\cdot\nabla u - \cutoff f}{v-v_{\patch(T)}}_{\patch(T)}.
\end{align*}
Note that $\norm{v-v_{\patch(T)}}{\patch(T)} \lesssim h_T^{1-s}\snorm{v}{1-s,\patch(T)}$ and therefore,
\begin{align*}
  |\ip{\Delta(\cutoff u)}{v}| &\lesssim h_T^{1-s} (\norm{\Delta\cutoff}{L^\infty(\patch(T))}\norm{u}{\patch(T)}
    + \norm{\nabla \cutoff}{L^\infty(\patch(T))}\norm{\nabla u}{\patch(T)}
  + \norm{\cutoff}{L^\infty(\patch(T))} \norm{f}{\patch(T)}) \norm{v}{1-s} \\
  &\lesssim (h_T^{-1-s}\norm{u}{\patch(T)} + h_T^{-s}\norm{\nabla u}{\patch(T)} + h_T^{1-s}\norm{f}{\patch(T)})\norm{v}{1-s}.
\end{align*}
Recall that we consider the case where $\partial \patch(T)$ does not share a boundary facet.
So the same estimates hold true when we replace $u$ by $u=u-u_{\patch(T)}$ since $\cutoff (u-u_{\patch(T)})|_{\Gamma} =
0$ and $\Delta(\cutoff(u-u_{\patch(T)}))\in L^2(\Omega)$.
Using $\norm{u-u_{\patch(T)}}{\patch(T)}\lesssim h_T \norm{\nabla u}{\patch(T)}$, dividing by $\norm{v}{1-s}$,
and taking the supremum we get
\begin{align*}
  h_T^s\snorm{\nabla u}{s,T} \leq h_T^s\norm{u-u_{\patch(T)}}{1+s,T} \lesssim
  h_T^s\norm{\Delta(\cutoff (u-u_{\patch(T)}))}{-1+s}
  \lesssim \norm{\nabla u}{\patch(T)} + h_T\norm{f}{\patch(T)}.
\end{align*}

Now we tackle the case where $\partial\patch(T)$ includes at least one boundary facet $E\in\EE^\Gamma$.
First, note that if a function $w$ vanishes on one facet $E$, then
\begin{align*}
  \norm{w}{\patch(T)} \lesssim h_T^r \snorm{w}{r,\patch(T)}, \quad 0\leq r\leq 1.
\end{align*}
Second, recall that
\begin{align*}
  \norm{\phi}{-1+s} = \sup_{0\neq v\in C_0^\infty(\Omega)} \frac{\ip{\phi}v}{\norm{v}{1-s}}.
\end{align*}
Then, the product rule~\cref{eq:app:prodrule} and the properties of the cut-off function prove that
\begin{align*}
  |\ip{\Delta(\cutoff u)}v| &\lesssim (h_T^{-2}\norm{u}{\patch(T)} + h_T^{-1}\norm{\nabla u}{\patch(T)} +
  \norm{f}{\patch(T)})\norm{v}{\patch(T)} \quad \text{for all } v \in C_0^\infty(\Omega).
\end{align*}
Using $\norm{v}{\patch(T)}\lesssim h_T^{1-s}\snorm{v}{1-s,\patch(T)}$, $\norm{u}{\patch(T)}\lesssim
h_T\norm{\nabla u}{\patch(T)}$ we further infer that
\begin{align*}
  |\ip{\Delta(\cutoff u)}v| &\lesssim h_T^{-s} (\norm{\nabla u}{\patch(T)} + h_T\norm{f}{\patch(T)})\norm{v}{1-s}.
\end{align*}
Dividing by $\norm{v}{1-s}$ and taking the supremum, we conclude that
\begin{align*}
  h_T^s\snorm{\nabla u}{s,T} \leq h_T^s\norm{u}{1+s,T} \lesssim h_T^s \norm{\Delta(\cutoff u)}{-1+s}
  \lesssim \norm{\nabla u}{\patch(T)} + h_T \norm{f}{\patch(T)}.
\end{align*}
This finishes the proof of~\cref{lem:localreg}.
\qed

\bibliographystyle{abbrv}
\bibliography{literature}

\end{document}


TITLE: My Line-Of-Sight algorithm works, but I don't understand why
QUESTION [0 upvotes]: I am developing a 3D application, and am currently implementing a mutual visualization / Line-of-Sight algorithm. (Image from Mathworks.com)
What it is supposed to do is given two points, pA and pB, traverse the line and every few meters, check to see if that point is visible.
My algorithm for this is to get the distance from the starting point to the current point, and then get the difference in elevation between the two. I would compute the angle between these two points, and check it against the previous "highest angle"(or it would become the "highest angle" if there was not already one). If the angle were to be greater than the previous "highest angle", then that segment is visible and the angle becomes the new "highest angle". Otherwise, you cannot see that segment. This is repeated for every point along the line.
However, when testing this, it does not work. BUT, if I flip the comparison to be 'if the current angle is less than or equal to the highest angle, then you can see the point`, it does seem to work.
My LOS algorithm visualized
So, why does it work? Visually, it does not make any sense. If the angle from P0 to P3 is less than the angle from P0 to P1, then the segment from P2 to P3 should not be visible. But, my code disagrees with me. I've attached some pictures for visual help.
Below is my algorithm written up in C++ (highestAngle is computed from p0 to p1)
for (std::size_t i = 1; i < pointsVec.size(); ++i)
    {
        Point p;
        p.m_x_lon = pointsVec.at(i).x();
        p.m_y_lat = pointsVec.at(i).y();
        GetPointElevation(p.m_x_lon, p.m_y_lat, p.m_z_elev);
        double dist = osgEarth::GeoMath::distance(std::vector<osg::Vec3d>{osg::Vec3d { start_xlon, start_ylat, 0 }, osg::Vec3d { p.m_x_lon, p.m_y_lat, 0 }});
        double newAngle = atan2(dist, p.m_z_elev - start_zelev) * 180 / M_PI;

        if (newAngle <= highestAngle)
        {
            highestAngle = newAngle;
            p.m_hasLOS = true;
        }
        else
        {
            p.m_hasLOS = false;
        }

        terrainProfileVec.push_back(std::move(p));
    }

REPLY [0 votes]: Having to check for a smaller angle doesn’t seem right to me, either. This is due to a bug in your code: the function atan2 wants the $y$-value first, which here should be the elevation difference.
Note that you don’t need to compute the actual angles, which is a relatively expensive operation. It’s enough to compare slopes—tangents of the angles—which are just elevation difference divided by distance.


TITLE: Are the orbits in my simulation correct?
QUESTION [0 upvotes]: I'm creating a simulation of our solar system.

I used data from https://nssdc.gsfc.nasa.gov/planetary/factsheet/ and I supplied the planets with perihelion and aphelion values. But I'm afraid the orbits themselves don't have the correct angle. Since the date of each planet when it reaches its perihelion and aphelion differ. I realise that in my simulation, there are 2 moments in the orbital period, where the planet reaches its closest distance from the sun. Same goes for the furthest distance... This is because the center of all orbits, is the sun, while it should be the "center of force" of the orbit.
Can the angle and center position of the orbits (not the Orbital inclination) be calculated? Maybe with Orbital Eccentricity? Or are there data sheets for this somewhere as well?
Thank you!

Simulation: https://codepen.io/DerkJanS/full/OJMRgvW
UPDATE: I know have this:

Based on http://www.planetaryorbits.com/

REPLY [1 votes]: Kepler's First Law states that planets (or any orbiting body) will travel in an ellipse where the center object (in this case the Sun) is situated at the foci. This is exactly how eccentricity is defined. If $c$ is the distance between the Sun and the center of the ellipse, $a$ is the semi-major axis (the distance from Sun in the factsheet you posted) then the eccentricity of the orbit is
$$e=\frac{c}{a}$$
This will allow your simulation to be much more realistic and ensure that there is only one closest and farthest approach, which are the perihelion and aphelion.


TITLE: How to compute this definite improper integral using the Residue Theorem??
QUESTION [3 upvotes]: I have been trying to compute this integral:
$$
\int_0^\infty \frac{\log^{2}\left({\left\vert{\tan\left({x}\right)}\right\vert}\right)}{1 + x^{2}}\,\mathrm{d}x
$$
using the Residue Theorem but have not been successful.
I tried to use the classical upper semi-circular contour, but realized that it would not work because $\log^{2}\left({\left\vert{\tan\left({x}\right)}\right\vert}\right)$ has singularities on the contour and is therefore not holomorphic on/in that contour.
Does anybody have any ideas of what kind of contour I should use?
I don't think we have to worry about the branches of the logarithm function because it's argument will always be real. Is that correct?

REPLY [4 votes]: Let us consider a general family of integrals
$$ I(a) = \int_{0}^{\infty} \frac{\log^2 \left| \tan(x/2) \right|}{a^2 + x^2} \, dx. $$
Notice that OP's integral equals $2I(2)$ by a simple substitution. Now we make the following very simple observation:
$$ \forall x \in \mathbb{R} \ : \quad
\log^2 \left| \tan(x/2) \right|
= \operatorname{Re}\left[ \log(\tan (x/2)) \log(\tan(-x/2)) \right]. $$
By this observation and symmetry, we find that
\begin{align*}
I(a)
&= \frac{1}{2} \operatorname{Re}\left[  \int_{-\infty}^{\infty} \frac{1}{a^2 + x^2} \log\left( i \frac{1 - e^{ix}}{1 + e^{ix}} \right) \log\left( -i \frac{1 - e^{ix}}{1 + e^{ix}} \right) \, dx \right] \\
&= \operatorname{Re}\left[ \pi i \mathop{\underset{z=ia}{\mathrm{Res}}} \frac{1}{a^2 + z^2} \log\left( i \frac{1 - e^{iz}}{1 + e^{iz}} \right) \log\left( -i \frac{1 - e^{iz}}{1 + e^{iz}} \right) \right] \\
&= \operatorname{Re}\left[ \frac{\pi}{2a}\log\left( i \frac{1 - e^{-a}}{1 + e^{-a}} \right) \log\left( -i \frac{1 - e^{-a}}{1 + e^{-a}} \right) \right] \\
&= \frac{\pi}{2a} \left( \frac{\pi^2}{4} + \log^2 \left( \tanh(a/2) \right) \right).
\end{align*}
In the second line, we utilized the fact that the integrand extends to a holomorphic function on the upper half-plane $\mathbb{H}$ which vanishes sufficiently fast near $\infty \in \partial \mathbb{H}$ along appropriately chosen contours.


TITLE: Identity surrounding Killing vector field on a spacetime $\nabla_a \nabla_b w_c = -{R_{bca}}^d w_d$
QUESTION [1 upvotes]: Let $w^a$ be a Killing vector field on a spacetime $(M, g_{ab})$, i.e., $w^a$ satisfies $\nabla_{(a}w_{b)} = 0$. I hypothesize that$$\nabla_a \nabla_b w_c = -{R_{bca}}^d w_d,$$but I am not sure how I would be able to see this. Could anybody help?

REPLY [0 votes]: You might want to look at Weinberg's Book on Gravitation and Cosmology. The equation you wrote above is (13.1.9) of the book.


TITLE: How to get the value of 'scaled' binomial distribution?
QUESTION [1 upvotes]: People kindly told me that there is not a equivalent popular distribution for $aX$ when $X$ is distributed as Binomial, but it is just a 'scaled' distribution. Here, $a$ is a positive constant.
Question
How to get the value of 'scaled' binomial distribution? Do I need to use $\Gamma$ function? A simpler way is appreciated.
To be more precise, I want to calculate $$g(x) = \frac{1}{|a|}f(\frac xa) = {n \choose x/a} p^{\frac xa} (1-p)^{(n-\frac xa)},$$ where $f(x)$ is $B(n,p)$ and $a$ is positive constant.
What is the simplest way to calculate $g(x)$?
Background
I'm considering this question under the same condition with this question, where $X$ is distributed as $Binomial$ and I want to know the distribution of $aX$. $a$ is a real and positive number.
I know
$aX \sim \frac{1}{|a|}f(\frac xa)$ ($f$ means the distribution of $X$),so I tried to calculate the probability of $aX$ by $\frac{1}{|a|}f(\frac xa) = {n \choose x/a} p^{\frac ax} (1-p)^{(n-\frac xa)}$. But, this was not easy for me because $x/a$ is not a integer.
I think with $\Gamma$ function $nCr$ can be calculated for any  real number $r (< n)$. But is there any straightforward way to calculate 'scaled' binomial distribution?

REPLY [2 votes]: For a random variable $X$ of binomial distribution of parameters $n,p$ the possible values taken are $0,1,2, \cdots, n$ with probabilities$$P(X=k)={n \choose k}p^k(1-p)^{n-k}.$$
If $a$ is a real constant and $Y=aX$ then the valueas taken by $Y$ are $1a,2a,\cdots , na$ with probabilities $$P(Y=ak)=P(X=k).$$
I don't know if this answers the question.
EDITED
Perhaps, the reason of confusion is that there is no pdf. The cdf is
$$F_Y(x)=P(aX<x)=P\left(X<\frac{x}{a}\right)=F_X\left(\frac{x}{a}\right).$$
If the derivative existed then one could get a formula similar to what you quoted for the Gaussian distribution.


TITLE: Borel regular measure: Approximate any measureable set by compact sets
QUESTION [4 upvotes]: Let $(K,\mathcal{F},\mu)$ be a measure space. Let $K$ be a compact Hausdorff space and $\mu$ be a regular finite measure. We said that it is regular if
$\mu(A) = \inf\{\mu(B): B \text{ open }, A\subset B\}$ and $\mu(U) = \sup(\mu(K) : K \text{ compact }, K \subset U\}$ for any measurable $A$ and any open $U$.
Given a measurable set $A$ and $\epsilon >0$. My Professor states that one can find a compact set $B\subset A$ such that $\mu(A\setminus B)< \epsilon$.
I don't quite see it as $A$ is not open. Is this true?

REPLY [5 votes]: Let $A \in \mathcal{F}$ be a measurable set. Fix $\epsilon>0$. By assumption, there exists an open set $B$ such that $K \backslash A \subseteq B$ and
$$\mu(B) \leq \mu(K \backslash A) + \epsilon. \tag{1}$$
The set $\tilde{K} := K \backslash B = B^c \subseteq A$ is compact and satisfies
$$\begin{align*} A \backslash \tilde{K} = A \backslash B^c &= A \cap B = B \backslash A^c = B \backslash (K \backslash A). \end{align*}$$
Looks like that:
$\hspace{120pt}$
Consequently,
$$\mu(A \backslash \tilde{K}) = \mu(B \backslash (K \backslash A)) = \mu(B) - \mu(K \backslash A) \stackrel{(1)}{\leq \epsilon}.$$
Since $\epsilon>0$ is arbitrary, this finishes the proof.


TITLE: Density in Compact-Open Equivalent to containment of subbases
QUESTION [1 upvotes]: Let $X,Y$ be Hausdorff spaces and consider the compact-open topology on $C(X,Y)$.  Let $F\subseteq C(X,Y)$ be a non-empty subset and consider the topology $\tau$ on $C(X,Y)$ with subbase
$$
B_F\triangleq \{f\in F: f(K)\subseteq V\}_{K \mbox{ compact in X}, U \mbox{ open in Y}}.
$$
Is $F$ dense in $C(X,Y)$ with this topology?

REPLY [2 votes]: Yes.  Much more generally, let $Z$ be any set, let $F\subseteq Z$ be nonempty, let $B$ be a set of subsets of $F$, and let $\tau$ be the topology on $Z$ generated by $B$.  Then every element of $\tau$ is a union of finite intersections of elements of $B$.  All of the terms of such a union intersect $F$ unless they are empty, so any non-empty element of $\tau$ intersects $F$.  That is, $F$ is dense with respect to $\tau$.


text:
\section{Preliminaries}\label{chpt:preliminaries}

All graphs in this work are finite and have no loops
or multiple edges. Let $G$ be a graph. Denote by $V(G)$ its vertex set, by $E(G)$ its edge set.
Denote the \emph{size} of a set $S$ by $|S|$. Unless stated otherwise, $|V(G)| = n$ and $|E(G)| = m$.
Let $u,v \in V(G)$, define $u$ and $v$ as \emph{adjacent} if $(u,v) \in E(G)$.

Let $V' \subseteq V(G)$. The \emph{induced subgraph} of $G$ by $V'$, denoted by $G[V']$, is the graph $G[V']= (V',E')$, where  $E' =  \{ (u,v)\in E(G) \mid u, v \in V' \}$. Analogously, for some $E' \subseteq E(G)$, let  the \emph{induced subgraph} of $G$ by $E'$, denoted by $G[E']$, be the graph $G[E']= (V',E')$, where  $V' =  \{ u, v \in V(G) \mid  (u,v)\in E' \}$.
A graph $G'$ obtained from $G$ by \emph{removing} the vertex $v \in V(G)$ is defined as $G' = (V(G) \setminus \{v\},  E')$, where $E'=\{(u,w) \in E \mid u \neq v \text{ and } w \neq v\}$

Let $v \in V(G)$, denote by $N(v)=  \{u \in V(G) \mid v \text{ and } u \text{ are adjacent} \}$ the \emph{neighborhood} of $v \in V(G)$, and by
$N[v] = N(v)\cup\{v\}$ the \emph{closed neighborhood} of $v$.
We define  $u, v \in V(G)$ as \emph{true twins} (resp. \emph{false twins}) if $N[u] = N[v]$ (resp. $N(u) = N(v)$).
A vertex $v$ of $G$ is \emph{universal} if $N[v] = V(G)$.
We define the \emph{degree} of $v \in V(G)$, denoted by \emph{$d(v)$},  as the number of neighbors of $v$ in $G$, i.e. $d(v) = |N(v)|$

A \emph{clique} or \emph{complete set} (resp.\ \emph{stable set} or \emph{independent
set}) is a set of pairwise adjacent (resp.\ nonadjacent) vertices.
We use \emph{maximum} to mean maximum-sized, whereas
\emph{maximal} means inclusion-wise maximal. The use of
\emph{minimum} and \emph{minimal} is analogous. A vertex $v \in V(G)$ is said to be \emph{simplicial} if $G[N(v)]$ is a clique.

A \emph{coloring} of a graph is an assignment of colors to its
vertices such that any two adjacent vertices are assigned
different colors. The smallest number $t$ such that $G$ admits a
coloring with $t$ colors (a \emph{$t$-coloring}) is called the
\emph{chromatic number} of $G$ and is denoted by $\chi(G)$. A
coloring defines a partition of the vertices of the graph into
stable sets, called \emph{color classes}.

A graph $G(V,E)$ is a \emph{comparability graph} if
there exists an ordering $v_1, \dots , v_n$ of $V$ such that, for
each triple $(r,s,t)$ with $r<s<t$, if $v_r v_s$ and $v_s v_t$ are
edges of $G$, then so is $v_r v_t$.\ Such an ordering is a
\emph{comparability ordering}. A graph is a \emph{co-comparability
graph} if its complement is a comparability graph.

A \emph{tree} $T$ is a connected graph that has no cycles. A \emph{rooted tree} $T_v$ is a tree in which a vertex $v \in V(T)$ is labeled as the \emph{root} of the tree. All vertices, known as \emph{nodes} of $T_v$, have implicit positions in relation to the root.

Let $u,w \in V(T_v)$, $w$ is a \emph{descendant} of $u$ if the path from $w$ to $v$ includes $u$. The node $w$ is said to be a \emph{child} of $u$ if it is a descendant of $u$ and $(w,u) \in E(T_v)$. The \emph{children} of $u$ is defined as the set that containing all child nodes of $u$. The node $u$ is said to be a \emph{leaf} of $T_v$ if it has no child in $T_v$.
The \emph{subtree} $T_u$ of $T_v$  \emph{rooted at} the node $u$ is the \emph{rooted} tree that consists of $u$ as the root  and its descendants in $T_v$ as the nodes.

A \emph{directed graph}, or \emph{digraph}, is a graph $D = (V,E)$ such that $E$ consists of ordered pairs of $V(G)$. A \emph{directed cycle} of a digraph $D$ is a sequence $v_1,v_2, \ldots,v_i$, $1 \leq i \leq n$, of vertices of $V(D)$ such that $v_1 = v_i$ and, for all $1 \leq j<i$, $(v_j,v_{j+1}) \in E(D)$. A \emph{directed acyclic graph} (\emph{DAG}) $D$ is a digraph with no directed cycles.  A \emph{topological ordering} of a DAG $D$ is a sequence $v_1,v_2,\ldots ,v_n$ of $V(D)$ such that there are no $1\leq i <j\leq n$ such that $(v_j,v_i) \in E(D)$. Determining a topological ordering of a DAG can be done in time $O(n+m)$~\cite{Knuth1}.

An \emph{ordering} $s$ of elements of a set $\mathcal{C}$, denoted by $V(s)$, consists of a sequence $e_1,e_2,\ldots,e_n$  of all elements of $\mathcal{C}$. We define $\bar{s}$ as the \emph{reversal} of $s$, that is, $\bar{s} = e_n,e_{n-1},\ldots,e_1$. We say that $e_i$ \emph{precedes} $e_j$ in $s$, denoted by $e_i < e_j$, if $i < j$. An ordered tuple $(a_1, a_2, \ldots,  a_k)$ of some elements of $\mathcal{C}$ is \emph{ordered according to} $s$ when, for all $1 \leq i < k$, if $a_i = e_j$ and $a_{i+1} = e_z$, then $j < z$. Given orderings $s_1$ and $s_2$, the ordering obtained by concatenating $s_1$ to $s_2$ is denoted by $s_1s_2$.

\subsection{Interval graphs}
The \emph{intersection graph} of a family $\mathcal{F}$ of sets is the graph $G$ such that $V(G) = \mathcal{F}$ and $S,T \in V(G)$ are adjacent if and only if $S \cap T \neq \emptyset$.
An \emph{interval graph} $G$ is the intersection graph of a family $\mathcal{R}$ of intervals of the real line; such a family is called an \emph{interval model}, or  a \emph{model}, of the graph.
We say that $\mathcal{R}$ is associated to $G$ and vice-versa.
It  is worth  mentioning that an interval graph can be associated to several models but an interval model can be associated to a unique graph.
Concerning interval graphs, there are some characterizations which are relevant to this work, that we present next.

\begin{theorem}[\cite{Olariu91}]\label{theo:can:ordering}
A graph $G$ is an interval graph if, and only if, there is an ordering $s$ of $V(G)$ such that, for any triple $(p,q,r)$ of $V(G)$ ordered according to $s$, if $(p,r) \in E(G)$, then $(q,r) \in E(G)$.
\end{theorem}

The ordering described in Theorem~\ref{theo:can:ordering} is said to be a \emph{canonical} ordering.
Figure~\ref{fig:canonico} depicts an interval graph in which the vertices are presented from left to right in one of its canonical orderings.

\begin{figure}
\centering
\subfigure[]{\label{fig:canonico}\includegraphics[width=64mm]{figures/preliminaries/qualiOrdCan.pdf}}
\hspace{0.45cm}
\subfigure[]{\label{fig:canonicoproprio}\includegraphics[width=64mm]{figures/preliminaries/qualiOrdCanP.pdf}}
\caption{(a) Canonical ordering and (b) proper canonical ordering.}
\end{figure}

Let $\mathcal{R}$ be an interval model of an interval graph $G$. Note that, if we consider a vertical line that  intersects a subset of intervals in $\mathcal{R}$, then these intervals consist of a clique in $G$. This is true because they all contain the point in which this line is defined. Moreover, if the given line traverses a maximal set of intervals, then the corresponding clique is maximal. Figure~\ref{fig:model} depicts an interval model and the vertical lines that correspond to maximal cliques of the graph in Figure~\ref{fig:canonico}.
The following is a characterization of interval graphs in terms of the maximal cliques of the graph.

\begin{figure}[htb]
\centering
\includegraphics[width=90mm]{figures/preliminaries/qualiModel.pdf}

\caption{ An interval model an the maximal cliques of the graph in Figure~\ref{fig:canonico}.}
\label{fig:model}
\end{figure}

\begin{theorem}[\cite{Roberts69}]\label{theo:clique:ordering}
A graph $G$ is an interval graph if, and only if, there is an ordering $s_C = C_1,C_2, \ldots, C_k$ of its maximal cliques such that if $v \in C_i \cap C_z$  with $1 \leq i \leq z \leq k$, then $v \in C_j$, for all $i \leq j \leq z$.
\end{theorem}

The ordering described in Theorem~\ref{theo:clique:ordering} is said to be a \emph{canonical clique} ordering. The ordering of the maximal cliques depicted in Figure~\ref{fig:model}, read from left to right, represents a canonical clique ordering.

A \emph{proper interval graph} is an interval graph that admits an interval model in which no interval properly contains another. There is a characterization of proper interval graphs which is
similar to that presented in Theorem~\ref{theo:can:ordering}, as described next.

\begin{theorem}[\cite{Roberts69}]\label{theo:procan:ordering}
A graph $G$ is a proper interval graph if, and only if, there is an ordering $s$ of $V(G)$  such that, for any triple $(p,q,r)$ of $V(G)$ ordered according to $s$, if $(p,r) \in E(G)$, then $(p,q), (q,r) \in E(G)$.
\end{theorem}

The ordering specified in the previous theorem is defined as a \emph{proper canonical} ordering. The ordering of the vertices of the graph depicted in Figure~\ref{fig:canonicoproprio} from left to right is proper canonical. Note that a proper canonical ordering is also a canonical ordering.
An important property of proper canonical orderings is the following:

\begin{lemma}[\cite{Roberts69}]
If $G$ is a connected proper interval graph. Then a proper canonical ordering of $G$ is unique up to reversion and permutation of mutual true twin vertices.
\end{lemma}

As a consequence, if a proper interval graph $G$ is disconnected, since each component has a unique proper canonical ordering, then the canonical ordering of $G$ consists of a permutation of canonical orderings of each of those components.

Let $s$ be an ordering of $V(G)$ and $s_C = C_1,C_2, \ldots, C_k$ an ordering of the maximal cliques of $G$.
The sequence $s$ is said to be \emph{ordered according} to $s_C$ if for all $u,v \in V(G)$ such that $u<v$ in $s$, there are no $ 1\leq i <j \leq k$ such that $v \in C_i \setminus C_j$ and  $u \in C_j$. As an example, note that the canonical ordering of the Figure~\ref{fig:canonico} is ordered according to  the maximal clique ordering $s_C = C_1,C_2, \ldots, C_6$ of the Figure~\ref{fig:model}.
The following lemma relates the characterization of canonical orderings and canonical clique orderings.

\begin{lemma}\label{lemma:clique:canonical}
Let $G$ be a graph and $s$ be an ordering of $V(G)$.  The ordering $s$ is a canonical ordering of $V(G)$ if, and only if, $s$ is ordered according to a canonical clique ordering of $G$.
\end{lemma}

\begin{proof}
Consider $s_C$ a canonical clique ordering of $G$. We will show that is possible to build a canonical ordering $s$ from $s_C$, respecting its clique ordering. To achieve this, first start with an empty sequence $s$. Iteratively, for each element $X$ of the sequence $s_C$, choose all simplicial vertices of $X$, adding them to $s$ in any order and removing them from $G$.
Note that some of the vertices of $X$ that were not removed from $G$, because they were not simplicial in $G$, now may be turned simplicial by the removal of vertices.
Clearly, at the end of the process, $s$ will contain all the vertices of $G$.
Suppose $s$ is not a canonical ordering, that is, there are $p,q,r \in V(G)$, $p<q<r$ in $s$, such that $(p,r) \in E(G)$ and $(q,r) \not \in E(G)$.
Let $C_p$, $C_q$ and $C_r$ be the maximal cliques of $s_C$ being processed at moment $p$, $q$ and $r$ were choose, respectively.  Note that $C_p < C_q < C_r$ in $S_c$ and, as $C_p$ is the last maximal clique in $s_C$ that contains $p$ and $(p,r) \in E(G)$,  $r \in C_p$. Besides, as $(q,r) \not \in E(G)$, $r \not\in C_q$ . Therefore, $r \in C_p \cap C_r$ and $r \not\in C_q$. A contradiction with the fact that $s_C$ is a canonical clique ordering. Hence, $s$ is a canonical ordering.

Consider $s= v_1,v_2, \ldots, v_n$ be a canonical ordering of $G$. We prove by induction in $|V(G)| = n$ that $s$ is ordered according to a canonical clique ordering. Clearly, the statement is true for $n = 1$. Suppose that the statement is true for any  $1 \leq n'< n$.
Let $s'$ be the sequence obtained from $s$ by removing $v_n$. Clearly $s'$ is also a canonical ordering and, by the induction hypothesis, $s'$ is ordered according with  a canonical clique ordering $s'_C = C_1,C_2, \ldots, C_k$. Let $C_i$, with $1 \leq i \leq k$, be the first clique of $s'_C$ such that $v_n \in N(C_i)$.
Let $C' _j = \{C_j \cap N(v_n)\} \cup \{v_n\}$, $i \leq j \leq k$.
Note that, as $s$ is a canonical ordering, for all $C_j$ of $s'_C$, $i < j \leq k$, $\{C_j \cap N(v_n)\}\cup \{v_n\}$ is a maximal clique of $G$.
If $C_i \subseteq N(v_n)$, then  $s'_C = C_1,C_2, \ldots, C'_i,C'_{i+1}, \ldots, C'_k$ is a canonical clique ordering that matches $s$. Otherwise, $s'_C = C_1,C_2, \ldots, C_i,C'_i,C'_{i+1}, \ldots, C'_k$ is a canonical clique ordering that matches $s$. Therefore, $s$ is ordered according to a canonical clique ordering of $G$.
\end{proof}

\subsubsection {PQ trees}

A \emph{$PQ$ tree}~\cite{BOOTH76} $T$ is a data structure consisting of an ordered tree that describes a family $\mathcal{F}$ of permutations of elements from a given set $\mathcal{C}$.
In a $PQ$ tree $T$, the set of leaves is $\mathcal{C}$ and the permutation being represented by $T$ is the sequence of the leaves from left to right. Regarding  internal nodes, they are classified into two types, the $P$ and the $Q$ nodes.
An \emph{equivalent} $PQ$ tree $T'$ to $T$ is a tree obtained from $T$ by any sequence of consecutive transformations, each consisting of either permuting the children of a $P$ node, or reversing the children of a $Q$ node. The family $\mathcal{F}$ of permutations of elements from $\mathcal{C}$ represented by  $T$ is that of permutations corresponding to all equivalent $PQ$ trees to $T$.

Graphically, in a $PQ$ tree, leaves and $P$ nodes are represented by circles and $Q$ nodes by rectangles. In representations of schematic $PQ$ trees, a node represented by a circle over a rectangle will denote that, in any concrete $PQ$ tree conforming the scheme, such a node is either a $P$ node, or a $Q$ node.
Figure~\ref{fig:PQT:exeOp} depicts the described operations. In Figure~\ref{fig:PQT:1}, we have a partial representation of a $PQ$ tree. Figure~\ref{fig:PQT:2} depicts an equivalent $PQ$ tree obtained from a permutation of children of a $P$ node of this tree and Figure~\ref{fig:PQT:3} exemplifies an equivalent $PQ$ tree from the reversion of the children of a $Q$ node.

\begin{figure}[htbp]
    \centering
    \subfigure[]{\label{fig:PQT:1}\includegraphics[width=37.7mm]{figures/preliminaries/PQT.pdf}}
    \subfigure[]{\label{fig:PQT:2}\includegraphics[width=37.7mm]{figures/preliminaries/PQT1_1.pdf}}\hfill
    \subfigure[]{\label{fig:PQT:3}\includegraphics[width=37.7mm]{figures/preliminaries/PQT2_1.pdf}}\\\

\caption{A $PQ$ tree (a) and an example of permutations (b) and reversions (c) of children of its nodes. }
\label{fig:PQT:exeOp}
\end{figure}

One of the applications from the seminal paper introducing $PQ$ trees is that of recognizing interval graphs.
In such an application, each  leaf of the $PQ$ tree  is a maximal clique of an interval graph $G$ and the family of permutations the tree represents is precisely all the canonical clique orderings of $G$~\cite{BOOTH76}. A $PQ$ tree can be constructed from an interval graph in time $O(n+m)$~\cite{BOOTH76}.

We will say that a  vertex $v$ belongs to a node $X$ of a $PQ$ tree, and naturally denote by $v \in X$,  if it belongs to any leaf that descends from this node. Figure~\ref{fig:pre:PQT} depicts a $PQ$ tree of the interval graph of Figure~\ref{fig:canonico} according to the maximal cliques in  Figure~\ref{fig:model}. The permutations implicitly represented by this  $PQ$ tree are:

\begin{minipage}[t]{0.9\linewidth}
    \vspace{2ex}
    \begin{minipage}[t]{0.4\linewidth}
        \centering
        \begin{itemize}
            \item $C_1,C_2,C_3,C_4,C_5,C_6$
            \item $C_1,C_2,C_3,C_4,C_6,C_5$
            \item $C_1,C_2,C_4,C_3,C_5,C_6$
            \item $C_1,C_2,C_4,C_3,C_6,C_5$
            \item $C_6,C_5,C_4,C_3,C_2,C_1$
            \item $C_5,C_6,C_4,C_3,C_2,C_1$
            \item $C_6,C_5,C_3,C_4,C_2,C_1$
            \item $C_5,C_6,C_3,C_4,C_2,C_1$
        \end{itemize}
    \end{minipage}
    \hfill
    \begin{minipage}[t]{0.4\linewidth}
            \captionsetup{type=figure}
            \vspace{-1.5ex}
            \centering
            \includegraphics[width=40mm]{figures/preliminaries/exPQT.pdf}
            \caption{A $PQ$ tree of the interval graph of Figure~\ref{fig:canonico} according to the maximal cliques in  Figure~\ref{fig:model}.}
            \label{fig:pre:PQT}
    \end{minipage}
\end{minipage}

\subsection {Thinness and proper thinness}

A graph $G$ is called a \emph{$k$-thin graph} if there is a $k$-partition $(V_1,V_2 \ldots, V_k)$ of $V(G)$ and an ordering $s$ of $V(G)$ such that, for any triple $(p,q,r)$ of $V(G)$ ordered according to $s$, if $p$ and $q$ are in a same part $V_i$ and $(p,r) \in E(G)$, then $(q,r)\in E(G)$. An ordering and a partition satisfying that property are called \emph{consistent}. That is, a graph is  $k$-thin if there is an ordering consistent with some $k$-partition of its vertex set.
The \emph{thinness} of $G$, denoted by \emph{$thin(G)$}, is the minimum  $k$ for which $G$ is a $k$-thin graph.

A graph $G$ is called a \emph{proper $k$-thin graph} if $G$ admits a $k$-partition $(V_1, \ldots, V_k)$ of $V(G)$ and an ordering $s$ of $V(G)$ consistent with the partition and, additionally, for  any triple $(p,q,r)$ of $V(G)$, ordered according to $s$, if $q$ and $r$ are in a same part $V_i$ and $(p,r) \in E(G)$, then $(p,q)\in E(G)$. Equivalently, an ordering $s$ of $V(G)$ such that $s$ and its reverse are consistent with the partition. Such an ordering and partition are called \emph{strongly consistent}.
The \emph{proper thinness} of $G$, or \emph{$pthin(G)$}, is the minimum $k$ for which $G$ is a proper $k$-thin graph.

Figures~\ref{fig:c4thin} and~\ref{fig:c4pthin} depict two bipartitions of a graph, in which the classes are represented by distinct colors, and two different vertex orderings. The ordering of Figure~\ref{fig:c4thin} is consistent with the corresponding partition but not strongly consistent, while the ordering of Figure~\ref{fig:c4pthin} is strongly consistent with the corresponding partition.

 Note that $k$-thin graphs (resp. proper $k$-thin graphs) generalize interval graphs (resp. proper interval graphs). The $1$-thin graphs (resp. proper $1$-thin graphs) are the interval graphs (resp. proper interval graphs). The parameter $\thin(G)$ (resp. $\pthin(G)$) is in a way a measure of how far a graph is from being an interval graph (resp. proper interval graph).

For instance, consider the graph $C_4$. Since $C_4$ is not an interval graph, $\pthin(C_4) \geq \thin(C_4) > 1$. Figure~\ref{fig:c4} proves that $\thin(C_4) = \pthin(C_4) = 2$.

A characterization of $k$-thin or proper $k$-thin graphs by forbidden induced subgraphs is only known for $k$-thin graphs within the class of cographs~\cite{Bono18}. Graphs with arbitrary large thinness were presented in~\cite{Carl07}, while in~\cite{Bono18} a family of interval graphs with arbitrary large proper thinness was used to show that the gap between thinness and proper thinness can be arbitrarily large. The relation of thinness and other width parameters of graphs like boxicity, pathwidth, cutwidth and linear MIM-width was shown in~\cite{Carl07,Bono18}.

Let $G$ be a graph and $s$ an ordering of its vertices. The graph $G_{s}$ has $V(G)$ as vertex set, and $E(G_{s})$ is such that for $v < w$, $(v,w) \in E(G_{s})$ if and only if there is a vertex $z$ in $G$ such that $v < w < z$, $(z,v) \in E(G)$ and $(z,w) \not \in E(G)$.
Similarly, the graph $\tilde{G}_s$ has $V(G)$ as vertex set, and $E(\tilde{G}_{s})$ is such that for $v < w$, $(v,w) \in E(\tilde{G}_{s})$ if and only if either there is a vertex $z$ in $G$ such that $v < w < z$, $(z,v) \in E(G)$ and $(z,w) \not \in E(G)$ or there is a vertex $x$ in $G$ such that $x < v < w$, $(x,w) \in E(G)$ and $(x,v) \not \in E(G)$.

\begin{theorem}\label{thm:coloring-order}\cite{Bono18,B-M-O-thin-tcs} Given a graph $G$ and an ordering ${s}$ of its vertices, a partition of $V(G)$ is consistent (resp. strongly consistent) with the ordering ${s}$ if and only if the partition is a valid coloring of $G_{s}$ (resp. $\tilde{G}_s$), which means that each part corresponds to a color in the coloring under consideration.
\end{theorem}

\begin{figure}[htbp]
    \centering
\subfigure[]{\label{fig:c4thin}\includegraphics[width=40mm]{figures/preliminaries/qualiC4thin.pdf}}\hfil
\subfigure[]{\label{fig:c4pthin}\includegraphics[width=40mm]{figures/preliminaries/qualiC4pthin.pdf}}\hfil

\caption{(a) A consistent ordering and a (b) strongly consistent ordering of $V(C_4)$, for the corresponding $2$-partitions.}
\label{fig:c4}
\end{figure}

\subsection {Precedence thinness and precedence proper thinness}

In this work, we consider a variation of the problems described in the last subsection by requiring that, given a vertex partition, the (strongly) consistent orderings hold an additional property.

A graph $G$ is \emph{\fpExt{k}} (resp. \emph{\fppExt{k}}), or \emph{\fp{k}} (resp. \emph{\fpp{k}}), if there is a $k$-partition of its vertices and a  consistent (resp. strongly consistent) ordering $s$ for which the vertices that belong to a same part are consecutive in $s$.
Such an ordering is called a
\emph{precedence consistent ordering} (resp. \emph{precedence strongly consistent ordering}) for the given partition.  We define \fpPar{G} (resp. \fppPar{G}) as the minimum value $k$ for which  $G$ is \fp{k} (resp. \fpp{k}).

The Figure~\ref{fig:C4-2ppt} illustrates a graph that is a \fpp{2} graph. The convention assumed is that the strongly consistent ordering being represented consists of the vertices ordered as they appear in the figure from bottom to top and, for vertices arranged in a same horizontal line, from left to right. Therefore, the strongly consistent ordering represented in Figure~\ref{fig:C4-2ppt} is $s =a,b,c,a',b',c'$.  The graph $C_4$ is not \fpp{2}, despite $\pthin(C_4)=2$. It can be easily verified by brute-force that, for all possible bipartitions of its vertex set and for all possible orderings $s$ in which the vertices of a same part are consecutive in $s$, the ordering and the partition are not strongly consistent. On the other hand, a \fpp{k} graph is a proper $k$-thin graph. Therefore, the class of \fpp{k} graphs is a proper subclass of that of proper $k$-thin graphs.

\begin{figure}[htbp]
    \centering
\includegraphics[width=35mm]{figures/preliminaries/qualiExemplo2FPP.pdf}

\caption{A \fpp{2} graph.}
\label{fig:C4-2ppt}

\end{figure}

If a vertex order $s$ is given, by Theorem~\ref{thm:coloring-order}, any partition which is precedence (strongly) consistent with $s$ is a valid coloring of $G_s$ (resp. $\tilde{G}_s$) such that, additionally, the vertices on each color class are consecutive according to $s$.

A greedy algorithm can be used to find a minimum vertex coloring with this property in polynomial time. Such method is described next, in Theorem~\ref{teo:kpptGreddy}.

\begin{theorem}\label{teo:kpptGreddy}
Let $G$ be a graph and $s$ an ordering of $V(G)$. It is possible to obtain a minimum $k$-partition $\mathcal{V}$ of $V(G)$, in polynomial time, such that $s$ is a precedence (strongly) consistent ordering concerning  $\mathcal{V}$.
\end{theorem}

\begin{proof}

Consider the following greedy algorithm that obtains an optimum coloring of $G_s$ (resp. $\tilde{G}_s$) in which vertices having a same color are consecutive in $s$. That is, $s$ is a precedence consistent (resp. precedence strongly  consistent) ordering concerning the partition defined by the coloring.
Color $v_1$ with color~$1$. For each $v_i$, $i>1$,  let $c$ be the last color used. Then color $v_i$ with color $c$ if there is no $v_j$, $j<i$, colored with $c$ such that $(v_j,v_i) \in E(G_s)$ (resp. $(v_j,v_i) \in E(\tilde{G_s})$). Otherwise, color $v_i$ with color $c+1$. We show, by induction on $|s| = n$, that the algorithm finds an optimal coloring in which each vertex has the least possible color.

The case where $n=1$ is trivial. Suppose that the algorithm obtains an optimum coloring of $G_s$ (resp. $\tilde{G_s}$), for orderings having size less than $n$.
Remove the last vertex $v_n$ from $s$ and $G_s$ (resp. $\tilde{G_s}$) and use the given algorithm to color the resulting graph. By the induction hypothesis, the chosen coloring for $v_1,v_2,\ldots,v_{n-1}$ is optimal. Moreover, the colors are non-decreasing and each vertex is colored with the least possible color. Now, add the removed vertex $v_n$ to $s$ and to the graph $G_s$ (resp. $\tilde{G_s}$), with its respective edges, and let the algorithm choose a coloring for it. If the color of $v_n$ is equal to the color of $v_{n-1}$ the algorithm is optimal by the induction hypothesis. Otherwise, $v_n$ is colored with a new color $c'$. Suppose the chosen coloring is not optimal. That is, it is possible  to color $v$ with an existing color.  This implies  that there is at least a neighbor $v_j$ of $v_n$, in $G_s$ (resp. $\tilde{G_s}$), that can be recolored with a smaller color. This is an absurd because the algorithm has already chosen the least possible color for all the vertices of $G_s \setminus \{v_n\}$ (resp. $\tilde{G_s}\setminus \{v_n\}$), relative to $s$.
\end{proof}

In the following sections, we will deal with the case where the vertex partition is given and the problem consists of finding the vertex ordering. From now on, we will then simply call \emph{precedence consistent ordering} (resp. \emph{precedence strongly consistent ordering}) to one that is such for the given partition.

config: arxiv


TITLE: Commutativity in a Unital Banach Algebra
QUESTION [4 upvotes]: Let $ A $ be a unital Banach algebra and $ S $ a non-empty subset of $ A $. The centralizer of $ S $ is defined as
$$
Z(S) \stackrel{\text{def}}{=} \{ a \in A ~|~ \text{$ as = sa $ for all $ s \in S $} \}.
$$
I need to show that if the elements of $ S $ commute with each other, then the elements of $ Z(Z(S)) $ commute with each other.
I know that $ Z(Z(S)) $ is a closed sub-algebra of $ A $ and that $ {\sigma_{A}}(a) = {\sigma_{Z(S)}}(a) $ for any $ a \in Z(S) $. Also, $ S \subseteq Z(Z(S)) $. But I do not see how the commutativity part follows.
Can anybody please give me a hint?

REPLY [5 votes]: Fact: If $ S $ and $ T $ are subsets of $ A $, then $ S \subseteq T $ implies $ Z(T) \subseteq Z(S) $.

If the elements of $ S $ commute with each other, then $ S \subseteq Z(S) $. Applying the fact above, we obtain $ Z(Z(S)) \subseteq Z(S) $, which then implies that $ Z(Z(S)) \subseteq Z(Z(Z(S))) $. Therefore, the elements of $ Z(Z(S)) $ commute with each other.

REPLY [4 votes]: This has nothing to do with banach algebras. It holds in every magma, i.e. set equipped with a binary operation. Also, $S \neq \emptyset$ is a useless and unnatural condition, it should be left out.
Observe that $S \subseteq T$ implies $Z(T) \subseteq Z(S)$ $(\star)$. Since $S$ is commutative, we have $S \subseteq Z(S)$. Applying $(\star)$ this we get $Z(Z(S)) \subseteq Z(S)$. Applying $(\star)$ once again, we get $Z(Z(S)) \subseteq Z(Z(Z(S)))$. But this exactly means that $Z(Z(S))$ is commutative.
Edit: Oh, Haskell and I posted the same proof, simultaneously!


text:
\section{Indiscrete Topology is not Metrizable}
Tags: Metrizable Topologies, Indiscrete Topology

\begin{theorem}
Let $S$ be a [[Definition:Set|set]] with more than one [[Definition:Element|element]].
The [[Definition:Indiscrete Topology|indiscrete topology]] on $S$ is not [[Definition:Metrizable Topology|metrizable]].
\end{theorem}

\begin{proof}
In order to be [[Definition:Metrizable Topology|metrizable]], there needs to be a [[Definition:Metric|metric]] $d$ on $S$, so that $\struct {S, d}$ is a [[Definition:Metric Space|metric space]].
As $S$ has more than one [[Definition:Element|element]], $\exists x, y \in S: x \ne y$.
Then:
:$\epsilon = \map d {x, y} > 0$
So the [[Definition:Open Ball of Metric Space|open $\epsilon$-ball]] $\map {B_{\epsilon / 2} } x$ is [[Definition:Open Set of Metric Space|$d$-open]].
Hence $\map {B_{\epsilon / 2} } x$ is in the [[Definition:Topology|topology]] which $d$ [[Metric Induces Topology|induces]].
But $x \in \map {B_{\epsilon / 2} } x$ while $y \notin \map {B_{\epsilon / 2} } x$.
Thus $\map {B_{\epsilon / 2} } x \ne \O$ and $\map {B_{\epsilon / 2} } x \ne S$.
So the [[Metric Induces Topology|topology induced by $d$]] is not the [[Definition:Indiscrete Topology|indiscrete topology]].
{{qed}}
\end{proof}

config: wiki


TITLE: What is the smallest interval of positive real numbers containing a representative from each equivalence class?
QUESTION [0 upvotes]: Let's define a relation $R$ on the $\mathbb{R}$ of real numbers as follows:
For any elements $x, y \in \mathbb{R}$, let's define $x R y$ to mean $x - y \in \mathbb{Q}$, the set of rational numbers.
This $R$ is indeed an equivalence relation and so partitions $\mathbb{R}$ into disjoint sets, called equivalence classes, where, for each $x \in \mathbb{R}$, we define the equivalence class $[x]$ of $x$ as
$$[x] \colon= \left\{ \ y \in \mathbb{R} \ \colon \ y R x \ \right\} = \left\{ \ y \in \mathbb{R} \ \colon \ y - x \in \mathbb{Q} \ \right\}.$$
Can we characterize (any of) these equivalence classes as a countable set of points
$$ \left\{ \ p_1, p_2, p_3, \ldots \right\}?$$
Now let's form a set $S$ as follows: The set $S$ contains the smallest positive element of the equivalence classes $[ x ]$, for all $x \in \mathbb{R}$.
Then is this set $S$ bounded from above in $\mathbb{R}$? If so, then what is the supremum of $S$?
In particular, can we assume that $S$ is contained in $(0, 1)$? $(0, 1]$?
Is there a name for this particular equivalence relation in the standard mathematical literature?

REPLY [0 votes]: As every non-trivial interval contains a representative
set, there is no such smallest interval.


TITLE: String theory target spaces
QUESTION [2 upvotes]: In basic string theory Lagrangians (e.g. the Polyakov or the Nambu-Goto), the variables include a function $x:X\rightarrow M$ embedding a world-sheet $X$ into some target space $M$, which can be Minkowski space or some curved target space. Is it possible to reformulate these theories to eliminate the target space? Perhaps to replace it with sections of some bundle over $X$? Although this would seem to amount to just some kind of $(1+1)$-dimensional quantum field theory?
I realize this is a somewhat open-ended question; I'm just wondering if there has been any research done toward formulating string theories that might not involve any dependence on a target space.

REPLY [4 votes]: Sure you can.  In fact, this usually goes by the name of strings without strings.  The basic observation is that when you quantise the sigma model when $M$ is, say, Minkowski spacetime, what you end up with is a quantum conformal field theory with a given central charge ($c=26$ for the bosonic string, for instance) and you identify the physical states with the semi-infinite cohomology of (a suitable extension of) the Virasoro algebra relative to the centre with values in the underlying vector space of the conformal field theory.
Now it should be clear from the above that you could side-step the quantisation of the sigma model and take as your starting point a module of Virasoro (or the suitable extension) of the right central charge so that its semi-infinite cohomology relative to the centre is nontrivial.
Of course, it may happen (e.g., the so-called Gepner models) that quantum string theories constructed in this way, can then be interpreted as the quantisation of a sigma model with some target space.  Having said that, I think it is safe to say that most such algebraically constructed quantum string theories do not have a sigma-model interpretation, though.


TITLE: find the supremum and infimum of the following set.
QUESTION [1 upvotes]: Let $A = [1,3) \cup (5,8)$. Find the supremum and infimum of $A$.
Firstly, I claim that $\sup A = 8$ and $\inf A = 1$.
Now, by definition, $8$ is the upper bound of $A$.
My next step is use this theorem, but I think there is a simple proof of this question without any theorem:
Let $A$ and $B$ be bounded subsets of $\Bbb R$. Then, $\sup (A \cup B) = \sup\{\sup A, \sup B \}$ is holds.
That is, I divide the set $A$ into two sets, say $A_1 = [1,3)$ and $A_2 = (5,8)$, then I prove that $\sup A_1 = 3$ and $\sup A_2 = 8$, and then use the above theorem, and done.
But, my question is, does there exist a simple proof that without any theorem?
How about the infimum proof? Does there exist theorem that says a similar argument same as the supremum theorem above?
Thanks in advanced.
EDIT: I've did the approach of proof of supremum as @zkutch post below.
Please correct me if I wrong. Here it is:
Claim that $\sup A = 8$. By definition, $8$ is the upper bound of $A$. We want to prove that $8$ is the least upper bound of $A$. Suppose for contradiction, that $8$ is not the least upper bound of $A$. Then, there exist a number $\epsilon \gt 0$ such that $8-\epsilon$ is also an upper bound of $A$. To contradict this, we exhibit $x \in A$ such that $8-\epsilon \lt x \lt 8$.
Since $0 \lt \frac{\epsilon}{2} \lt \epsilon$, we can see that $x = 8 - \frac{\epsilon}{2}$ satisfies $8-\epsilon \lt x \lt 8$.
Now, since $8-\epsilon$ is (by assumption) a upper bound of $A$ and $5+\epsilon \in A$, then we have $5+\epsilon \le 8-\epsilon$, showing that $x \in A$. Thus, $8-\epsilon$ is not an upper bound of $A$, a contradiction. Hence, $\sup A = 8$.

REPLY [2 votes]: Definition of $\sup$ requires two property: first there is, because $8$ is more, then any number in union. Then, for every $\varepsilon >0$ is possible to find number from $(5,8)$, which is more then $8-\varepsilon $. Can you do it?