# A restricted additive smoother for finite cell flow problems ††thanks:
Financial support was provided by the German Research Foundation (Deutsche
Forschungsgemeinschaft, DFG) in the framework of the collaborative research
center SFB 837 Interaction Modeling in Mechanized Tunneling.

S. Saberi High Performance Computing, Ruhr University Bochum, Universitätsstr.
150, 44801 Bochum, Germany A. Vogel 22footnotemark: 2

###### Abstract

In this work, we propose an adaptive geometric multigrid method for the
solution of large-scale finite cell flow problems. The finite cell method
seeks to circumvent the need for a boundary-conforming mesh through the
embedding of the physical domain in a regular background mesh. As a result of
the intersection between the physical domain and the background computational
mesh, the resultant systems of equations are typically numerically ill-
conditioned, rendering the appropriate treatment of cutcells a crucial aspect
of the solver. To this end, we propose a smoother operator with favorable
parallel properties and discuss its memory footprint and parallelization
aspects. We propose three cache policies that offer a balance between cached
and on-the-fly computation and discuss the optimization opportunities offered
by the smoother operator. It is shown that the smoother operator, on account
of its additive nature, can be replicated in parallel exactly with little
communication overhead, which offers a major advantage in parallel settings as
the geometric multigrid solver is consequently independent of the number of
processes. The convergence and scalability of the geometric multigrid method
is studied using numerical examples. It is shown that the iteration count of
the solver remains bounded independent of the problem size and depth of the
grid hierarchy. The solver is shown to obtain excellent weak and strong
scaling using numerical benchmarks with more than 665 million degrees of
freedom. The presented geometric multigrid solver is, therefore, an attractive
option for the solution of large-scale finite cell problems in massively
parallel high-performance computing environments.
Keywords  Finite cell method $\;\cdot\;$Stokes $\;\cdot\;$Geometric multigrid
$\;\cdot\;$unfitted finite element method $\;\cdot\;$restricted additive

##  1 Introduction

The numerical approximation of partial differential equations using classical
techniques such as the finite element method [21], the finite difference
method [33] and the finite volume method [22] involves the generation of a
boundary-conforming mesh, which is, especially for complex domains, a
laborious and cost-intensive task. A conglomerate of non-conforming methods
under the loose brand of unfitted finite element methods have recently emerged
in response to such challenges and include techniques such as the extended
finite element method [6], the finite cell method [38, 17, 52], the cut finite
element method [13] and the immersed finite element method [41, 35]. In this
work, we focus on the finite cell method, where the physical domain of
interest is embedded in a regular background computational mesh and recovered
using a sufficiently accurate integration technique. The finite cell method
has been successfully used for a variety of applications, including large
deformation structural analysis [53], elasto-plasticity [2, 1, 43], linear and
nonlinear fluid flow [49], thermo-elasticity [59], shell analysis [44],
topology optimization [37], etc., see also [52] for a review. While the
generation of a boundary conforming mesh is effectively circumvented in the
finite cell method, and while the regular nature of the computational domain
offers a wide range of optimization opportunities, the resultant system of
equations is typically severely ill-conditioned mainly on account of
unfavorably cut cells, rendering the solution of large-scale problems
specially daunting as a consequence. Therefore, the development of efficient
iterative solvers for the solution of the resultant system is a relevant
challenge to the usage of such methods.

Geometric multigrid solvers are shown to be among the most efficient iterative
methods for classical finite element methods [27] as well as the finite cell
method [42, 50, 49, 29], capable of obtaining optimal convergence rates
independent of the problem size. In this regard, the convergence of the
geometric multigrid solver heavily depends on the effectiveness of the
employed smoother operator, which is virtually always problem and
discretization dependent. A tailored smoother operator for the treatment of
cutcells was shown to be necessary for the convergence of geometric multigrid
methods for the finite cell method, see, e.g., [42, 50, 49].

In this work, we present an adaptive geometric multigrid method for the
solution of the finite cell formulation of the Stokes problem. Furthermore,
the saddle-point systems arising from the discretization of the Stokes
equations appear also in a wide range of other domains such as power network
analysis, finance and PDE optimization problems, making the presented
geometric multigrid method for the solution of the Stokes equations relevant
beyond flow applications. The Uzawa method [19, 9], multigrid methods [57, 27,
58], Krylov subspace solvers [45, 54, 46] with a variety of preconditioning
techniques including Schur complement methods [39, 55, 30, 18] and domain
decomposition methods [32, 31, 40] are among the most popular solvers for the
Stokes equations. A variety of smoothers have been proposed for the Stokes
equations, including a smoother based on incomplete LU factorization [58], the
Braess-Sarazin smoother [8] which is based on a global pressure correction
scheme and the Vanka smoother [56] which is based on the solution of local
saddle-point problems. The restricted additive Vanka (RAV) smoother was
recently proposed in [48] and its parallel scalability for large-scale
problems on distributed-memory computing clusters was studied in [47]. It was
shown that the RAV smoother is competitive with the classical Vanka smoother
in terms of convergence rate while being computationally less expensive;
moreover, it can be represented exactly in parallel with minimal communication
because of its additive nature.

The aim of this work is to develop a scalable and efficient smoother for the
finite cell formulation of the Stokes equations with focus on the solution of
large-scale problems in high-performance computing environments. To this end,
the main findings of [49], namely the appropriate treatment of cutcells in the
finite cell method and the RAV smoother in [47] are used as inspiration for
the development of the proposed smoother. The main contributions of this work
can be summarized as follows:

  * •

A restricted additive smoother in the context of an adaptive geometric
multigrid method for the finite cell formulation of the Stokes equations is
proposed

  * •

The computational and parallelization aspects of the smoother operator are
discussed, and three cache policies are proposed. In particular, it is shown
that the smoother operator can be replicated exactly in parallel with little
communication overhead and offers memory optimization opportunities

  * •

The parallel scalability and convergence of the geometric multigrid solver is
studied using numerical benchmarks with up to more than 665 million degrees of
freedom on distributed-memory machines

The remainder of this work is organized as follows. In Section 2, the finite
cell formulation of the Stokes equations is presented. The geometric multigrid
solver and the proposed smoother are discussed in detail in Section 3. The
behavior of the geometric multigrid solver with the proposed smoother is
studied in Section 4 using a number of numerical experiments in terms of
convergence, computational cost and weak and strong scalability in parallel on
distributed-memory machines. Finally, conclusions are drawn in Section 5.

##  2 Finite cell formulation

In this section, we discuss the mixed finite cell formulation of the Stokes
equations, whose strong form can be written as

$\begin{split}-\eta\nabla^{2}\bm{u}+\nabla p&=\bm{f}\quad\text{in}\;\Omega,\\\
\nabla\cdot\bm{u}&=0\quad\text{in}\;\Omega,\end{split}$ (1)

where $\Omega$ is the physical domain. $\bm{u}$ is the vector-valued fluid
velocity and $p$ is the scalar fluid pressure. $\eta$ is the kinematic
viscosity, and $\bm{f}$ is the body force function. Equation (1) along with
the boundary conditions

$\begin{split}\bm{u}&=\bm{w}\;\text{on}\;\Gamma_{D}\subset\partial\Omega,\\\
\eta\frac{\partial\bm{u}}{\partial\bm{n}}-\bm{n}p&=\bm{h}\;\text{on}\;\Gamma_{N}:=\partial\Omega\setminus\Gamma_{D},\\\
\end{split}$ (2)

forms the Stokes boundary-value problem, where $\partial\Omega$ is the
boundary of the physical domain. $\Gamma_{D}$ and $\Gamma_{N}$ denote the
Dirichlet and Neumann boundaries, respectively, such that
$\partial\Omega=\Gamma_{D}\cup\Gamma_{N}$ and
$\Gamma_{D}\cap\Gamma_{N}=\emptyset$. $\bm{w}$ and $\bm{h}$ are predefined
functions. $\bm{n}$ is the outward normal vector to the boundary with unit
length.

The boundary-conforming weak formulation of the Stokes equations can be
obtained following the standard finite element procedure, see, e.g., [21] as:

Find $(\bm{u},p)\in(\bm{V}_{w},Q)$ such that

$\begin{split}(\eta\nabla\bm{v},\nabla\bm{u})_{\Omega}-(\nabla\cdot\bm{v},p)_{\Omega}-(q,\nabla\cdot\bm{u})_{\Omega}=\\\
(\bm{v},\bm{f})_{\Omega}+(\bm{v},\bm{h})_{\Gamma_{N}},\quad\forall(\bm{v},q)\in(\bm{V}_{0},Q),\\\
\end{split}$ (3)

where $(\cdot,\cdot)_{\Omega}$ and $(\cdot,\cdot)_{\partial\Omega}$ denote the
$L^{2}$ scalar product on $\Omega$ and $\partial\Omega$, respectively and

$\begin{split}\bm{V}_{w}&:=\\{\bm{u}\in
H^{1}(\Omega)^{d}\;|\;\bm{u}=\bm{w}\;\text{on}\;\Gamma_{D}\\},\\\
\bm{V}_{0}&:=\\{\bm{v}\in
H^{1}(\Omega)^{d}\;|\;\bm{v}=\bm{0}\;\text{on}\;\Gamma_{D}\\},\\\ Q&:=\\{q\in
L^{2}(\Omega)\\},\end{split}$ (4)

where $d$ is the spatial dimension of the domain.

We derive the weak finite cell formulation of the Stokes equations next, which
involves on the one hand the extension of the physical domain to an embedding
computational domain and the weak imposition of the essential boundary
conditions on the other. The physical domain $\Omega$ is extended by a
fictitious part to the embedding domain $\Omega_{e}$ in order to circumvent
the need for a boundary-conforming mesh. $\Omega_{e}$ is typically chosen as
regular such as to enable the straightforward generation and manipulation of
the computational domain. We employ fully distributed space tree data
structures, see, e.g., [14, 4, 50] for the discretization of $\Omega_{e}$ that
are capable of the efficient handling of regular spaces with low memory
footprint and excellent load balancing. As a consequence of embedding the
physical domain in $\Omega_{e}$, the boundary of the physical domain is not
guaranteed to coincide with the computational domain, and essential boundary
conditions must be imposed weakly in the finite cell formulation in contrast
to the boundary-conforming case above, where the essential boundary conditions
were included in the function spaces. Lagrange multipliers [23, 24, 26, 11],
the penalty method [3, 60, 10] and Nitsche’s method [36, 28, 16, 20, 12] are
among the techniques used for the weak imposition of boundary conditions. We
employ the symmetric Nitsche’s method in this work. The weak finite cell
formulation of the Stokes equations can be written as, see also [49]:

Find $(\bm{u},p)\in(\bm{V_{e}},Q_{e})$ such that

$\begin{split}(\eta\nabla\bm{v},\alpha\nabla\bm{u})_{\Omega_{e}}-(\bm{v},\bm{n}\cdot\eta\nabla\bm{u})_{\Gamma_{D}}-(\bm{n}\cdot\eta\nabla\bm{v},\bm{u})_{\Gamma_{D}}+(\bm{v},\lambda\bm{u})_{\Gamma_{D}}\\\
-(\nabla\cdot\bm{v},\alpha
p)_{\Omega_{e}}+(\bm{v},\bm{n}p)_{\Gamma_{D}}+(\bm{n}q,\bm{u})_{\Gamma_{D}}-(q,\alpha\nabla\cdot\bm{u})_{\Omega_{e}}=\\\
(\bm{v},\alpha\bm{f})_{\Omega_{e}}+(\bm{v},\bm{h})_{\Gamma_{N}}-(\bm{n}\cdot\eta\nabla\bm{v},\bm{w})_{\Gamma_{D}}+(\bm{v},\lambda\bm{w})_{\Gamma_{D}}+(\bm{n}q,\bm{w})_{\Gamma_{D}},\\\
\forall(\bm{v},q)\in(\bm{V}_{e},Q_{e}),\\\ \end{split}$ (5)

where $\Omega_{e}$ is the embedding domain, $(\bm{V}_{e},Q_{e})$ are given by

$\begin{split}\bm{V}_{e}&:=\\{\bm{u}\in H^{1}(\Omega_{e})^{d}\\},\\\
Q_{e}&:=\\{q\in L^{2}(\Omega_{e})\\},\end{split}$ (6)

and $\alpha$ is a scalar penalization parameter defined as

$\begin{cases}\alpha=1\quad\text{in}\;\Omega,\\\
\alpha=0\quad\text{in}\;\Omega_{e}\setminus\Omega.\end{cases}$ (7)

The penalization parameter $\alpha$ is typically chosen as a small value
($\alpha\ll 1$) instead in the fictitious part $\Omega_{e}\setminus\Omega$ in
order to alleviate the severe numerical ill-conditioning of the resultant
system of equations. $\lambda$ is the scalar stabilization parameter in
Nitsche’s method.

Introducing the discrete spaces
$(\bm{V}_{e,h},Q_{e,h})\subset(\bm{V}_{e},Q_{e})$, the bilinear and linear
forms can be written as

$\begin{split}a(\bm{v}_{h},\bm{u}_{h})+b(\bm{v}_{h},p_{h})&=f(\bm{v}_{h})\\\
b(q_{h},\bm{u}_{h})+c(q_{h},p_{h})&=g(q_{h}),\\\ \end{split}$ (8)

where $a$, $b$, $f$ and $g$ are defined according to the weak form in Equation
(5) as

$\displaystyle a(\bm{v}_{h},\bm{u}_{h})$
$\displaystyle:=(\eta\nabla\bm{v}_{h},\alpha\nabla\bm{u}_{h})_{\Omega_{e,h}}-(\bm{v}_{h},\bm{n}\cdot\eta\nabla\bm{u}_{h})_{\Gamma_{D,h}}-(\bm{n}\cdot\eta\nabla\bm{v}_{h},\bm{u}_{h})_{\Gamma_{D,h}}$
(9) $\displaystyle+(\bm{v}_{h},\lambda\bm{u}_{h})_{\Gamma_{D,h}}$
$\displaystyle b(\bm{v}_{h},p_{h})$
$\displaystyle:=-(\nabla\cdot\bm{v}_{h},\alpha
p_{h})_{\Omega_{e,h}}+(\bm{v}_{h},\bm{n}p_{h})_{\Gamma_{D,h}}$ $\displaystyle
f(\bm{v}_{h})$
$\displaystyle:=(\bm{v}_{h},\alpha\bm{f})_{\Omega_{e,h}}+(\bm{v}_{h},\bm{h})_{\Gamma_{N,h}}-(\bm{n}\cdot\eta\nabla\bm{v}_{h},\bm{w})_{\Gamma_{D,h}}+(\bm{v}_{h},\lambda\bm{w})_{\Gamma_{D,h}}$
$\displaystyle g(q_{h})$ $\displaystyle:=(\bm{n}q_{h},\bm{w})_{\Gamma_{D}},$

where $\Omega_{e,h}$ and $\Gamma_{\cdot,h}$ are appropriate discretizations of
$\Omega_{e}$ and $\partial\Gamma$, respectively. An approximation of the
embedding domain $\Omega_{e}$ is defined by $\Omega_{e,h}$ such that
$\overline{\Omega}_{e,h}:=\cup_{i=1}^{n_{K}}K_{i}$, where
$\mathcal{T}_{e,h}:=\\{K_{i}\\}_{i=1}^{n_{K}}$ with
$\mathring{K}_{i}\cap\mathring{K}_{j}=\emptyset$ for $i\neq j$ form a
tessellation of $\Omega_{e}$ into a set of $n_{K}$ compact, connected,
Lipschitz sets $K_{i}$ with non-empty interior.

In this work, we focus on the $Q_{1}-Q_{1}$ discretization of the weak
formulation. The equal-order $Q_{p}-Q_{p}$ elements do not satisfy the inf-sup
condition, and an appropriate stabilization of the discrete form is,
therefore, necessary. We note that equal order elements, especially of lower
orders, nevertheless, remain attractive choices on account of their lower
computational cost and ease of implementation compared to most of their
conforming counterparts. The bilinear form $c$ in Equation (8) is then the
stabilization term based on a local $L^{2}$ projection of the pressure [15, 7,
34], given by

$c(q_{h},p_{h}):=-\frac{1}{\eta}(q_{h}-\Pi_{0}q_{h},p_{h}-\Pi_{0}p_{h})_{\Omega_{e,h}},$
(10)

where $\Pi_{0}$ is a local $L^{2}$-projection operator [7], where the
projection of a given function $q$ must satisfy

$\int_{\Omega_{K}}(\Pi_{0}q-q)d\bm{x}=0\;\forall K\in\mathcal{T}_{e,h},$ (11)

where $\Omega_{K}$ is the domain associated with $K$.

##  3 Geometric multigrid

In this section, we develop a monolithic adaptive geometric multigrid solver
for the mixed finite cell formulation of Stokes equations on distributed-
memory machines, where we briefly introduce the multigrid framework in the
first part and focus on the proposed smoother operator in the second. The
spatial discretization of the computational domain, as described in Section 2,
is handled by space tree data structures, where adaptive mesh refinement
towards the boundary of the physical domain and potentially other regions of
interest is employed. Given a coarse cell, mesh refinement then corresponds to
the division of the cell into its $2^{d}$ children, where $d$ is the spatial
dimension. In addition, we impose a 2:1 balance such that neighboring cells
are at most one level of refinement apart. The discrete computational domain
may, therefore, include hanging nodes, which are handled as constraints and
removed from the global system of equations. The discrete weak form in
Equation (8) results in a linear system of the form

$\mathbf{L}\mathbf{x}=\mathbf{b},$ (12)

where $\mathbf{L}:=\begin{pmatrix}\mathbf{A}&\mathbf{B}\\\
\mathbf{B}^{T}&\mathbf{C}\end{pmatrix}$ with
$\mathbf{A}\in\mathbb{R}^{n_{u}\times n_{u}}$ and
$\mathbf{B}\in\mathbb{R}^{n_{u}\times n_{p}}$ and
$\mathbf{b}:=\begin{pmatrix}\mathbf{f}\\\ \mathbf{g}\end{pmatrix}$ with
$\mathbf{f}\in\mathbb{R}^{n_{u}}$ and $\mathbf{g}\in\mathbb{R}^{n_{p}}$ are
defined according to the bilinear and linear forms of the discrete weak
problem in Equation (9), respectively. The matrix
$\mathbf{C}\in\mathbb{R}^{n_{p}\times n_{p}}$ is defined according to the
stabilization term $c$ in Equation (10).
$\mathbf{x}:=\begin{pmatrix}\mathbf{u}\\\ \mathbf{p}\end{pmatrix}$ is the
solution vector, where $\mathbf{u}\in\mathbb{R}^{n_{u}}$ and
$\mathbf{p}\in\mathbb{R}^{n_{p}}$ are the coefficients of expansion of the
velocity and pressure functions, respectively. Geometric multigrid methods
seek the solution to the system of equations in Equation (12) through a
hierarchy of coarser discretizations, $\Omega_{e,h}^{l},l=1,\ldots,L$, where
$\Omega_{e,h}^{L}$ and $\Omega_{e,h}^{1}$ are the finest and coarsest grids,
respectively. We construct $\Omega_{e,h}^{l},l=1,\ldots,L$ top down, where
given the grid $\Omega_{e,h}^{l}$, the immediate coarse grid
$\Omega_{e,h}^{l-1}$ is obtained according to Algorithm 1. This process is
repeated $L$ times, resulting in a nested grid hierarchy.

The multigrid cycle consists in the application of the smoother operator,
transfer of the residual and correction vectors through the grid hierarchy and
the solution of the coarsest problem. The grids
$\Omega_{e,h}^{l},l=1,\ldots,L$ are fully distributed such that a given cell
is uniquely owned by a single process. Therefore, it is desirable to keep the
number of local cells per process roughly equal on each grid in order to
maintain load balancing. As a consequence of adaptive mesh refinement, child
cells and their corresponding parent are not guaranteed to remain on the same
process after the application of load balancing. Therefore, data transfer
between grids is carried out in two steps as follows. The restriction of a
vector $\mathbf{v}^{l}$ on the fine grid $\Omega_{e,h}^{l}$ to
$\mathbf{v}^{l-1}$ on the coarse grid $\Omega_{e,h}^{l-1}$, is achieved
through the restriction operator
$\mathcal{R}_{l}^{l-1}:\Omega_{e,h}^{l}\to\Omega_{e,h}^{l-1}$ which can be
written as

$\mathcal{R}_{l}^{l-1}:=\mathcal{T}^{l-1}\tilde{\mathcal{R}}_{l}^{l-1}.$ (13)

$\mathcal{R}_{l}^{l-1}$ is split into the intermediate restriction operator
$\tilde{\mathcal{R}}_{l}^{l-1}:\Omega_{e,h}^{l}\to\tilde{\Omega}_{e,h}^{l-1}$
and the transfer operator
$\mathcal{T}^{l-1}:\tilde{\Omega}_{e,h}^{l-1}\to\Omega_{e,h}^{l-1}$, where
$\tilde{\Omega}_{e,h}^{l-1}$ is an intermediate process-local coarse grid,
constructed from the fine grid $\Omega_{e,h}^{l}$ such as to guarantee that
the parent of child nodes are on the same process as $\Omega_{e,h}^{l}$.
Therefore, $\tilde{\mathcal{R}}_{l}^{l-1}$ is a process-local operator that
does not require any communication. The operator $\mathcal{T}^{l-1}$ transfers
$\tilde{\mathbf{v}}^{l-1}$ to $\mathbf{v}^{l-1}$ between
$\tilde{\Omega}_{e,h}^{l-1}$ and the distributed coarse grid
$\Omega_{e,h}^{l-1}$ and involves data communication. Prolongation of a vector
$\mathbf{v}^{l-1}$ on the coarse grid $\Omega_{e,h}^{l-1}$ to $\mathbf{v}^{l}$
on the fine grid $\Omega_{e,h}^{l}$, expressed as
$\mathcal{P}_{l-1}^{l}:={\mathcal{R}_{l}^{l-1}}^{T}$, similarly takes place in
two steps, where $\mathbf{v}^{l-1}$ is first transferred to an intermediate
grid and subsequently to the fine grid.

The solution of the coarsest problem is the remaining step in the multigrid
cycle, for which a direct solver is used in this work. We note that direct
solvers typically suffer from high computational complexity on the one hand
and suboptimal concurrency opportunities on the other; therefore, the
efficient employment of direct solvers within the multigrid cycle in parallel
presupposes that, through a sufficiently deep grid hierarchy, the coarsest
problem is sufficiently small.

input : $\Omega_{e,h}^{l}$

output : $\Omega_{e,h}^{l-1}$

$\Omega_{e,h}^{l-1}\leftarrow\Omega_{e,h}^{l}$ ;

$r_{max}\leftarrow\text{max}(r_{K}\forall K\in\Omega_{e,h}^{l-1})$ ;

for  _$K\in\Omega_{e,h}^{l-1}$_ do

if  _$r_{K}==r_{max}$_ then

coarsen $K$ ;

end if

end for

Balance $\Omega_{e,h}^{l-1}$ ;

Algorithm 1 Generation of the immediate coarse grid $\Omega_{e,h}^{l-1}$ from
the fine grid $\Omega_{e,h}^{l}$. $r_{K}$ is the refinement level of $K$.
Given a a cell $K$, the coarsen operator replaces $K$ and all of its siblings
with their parent. The balance operator imposes the 2:1 balancing as explained
in Section 3

###  3.1 The restricted additive smoother

The convergence of multigrid methods heavily depends on the assumption that
highly oscillatory frequencies of the error can be effectively eliminated on
finer grids on the one hand and that slowly oscillatory frequencies can be
adequately represented on coarser grids on the other. The smoother operator
plays a major role in this regard, whose appropriate choice often determines
the performance of the multigrid method. [27]

We propose a smoother for the solution of the finite cell formulation of
Stokes equations in this section. We define the smoother operator first and
discuss its parallelization aspects and memory footprint next, where three
cache policies for the smoother operator are proposed.

A series of iterative corrections for the solution vector in Equation (12) can
be defined as

$\mathbf{x}^{k+1}=\mathbf{x}^{k}+\mathbf{S}(\mathbf{b}-\mathbf{L}\mathbf{x}^{k}),$
(14)

where $k$ denotes the iteration step and $\mathbf{S}$ denotes the smoother
operator. The smoother operator can be written as

$\mathbf{S}=\sum_{i=1}^{n_{p}}(\mathbf{\tilde{R}}_{i}^{T}\bm{\omega}_{i}\mathbf{L}_{i}^{-1}\mathbf{R}_{i}),$
(15)

and, in the context of Schwarz domain decomposition methods, see, e.g., [25],
consists in the application of corrections from a set of subdomains
$\mathcal{S}_{i},i=1,\ldots,n_{p}$, where $n_{p}$ is the number of pressure
nodes in the discrete domain. $\mathcal{S}_{i}$ is composed of the pressure
degree of freedom $p_{i}$, all the pressure degrees of freedom that are
connected to it, and all the velocity degrees of freedom that are either
connected to $p_{i}$ or to the pressure degrees of freedom connected to
$p_{i}$. The pressure DoF $p_{i}$ is said to be connected to a velocity DoF if
the corresponding entry in the $i$-th row of $\mathbf{B}^{T}$ is non-zero. The
subdomain restriction operator $\mathbf{R}_{i}$ effectively extracts the set
of DoFs in $\mathcal{S}_{i}$, and is defined as those rows of the identity
matrix $\mathbf{I}\in\mathbb{R}^{n\times n}$ that correspond to the DoFs in
$\mathcal{S}_{i}$, where $n$ denotes the total number of degrees of freedom.
$\mathbf{L}_{i}:=\mathbf{R}_{i}\mathbf{L}\mathbf{R}_{i}^{T}$ is the subdomain
block of $\mathbf{L}$ and $\bm{\omega}_{i}$ is a diagonal damping matrix. The
prolongation operator $\mathbf{\tilde{R}}_{i}^{T}$ is an injection operator
that extends a vector by padding it with zeros and only consists of the
pressure DoF $p_{i}$ and the velocity DoFs on the same pressure node. The
choice of the restriction and prolongation operators are inspired on the one
hand by the observation that the treatment of cutcells in the finite cell
formulation of the Stokes equations is essential for the convergence of
multigrid methods [49] and the favorable properties of the RAV smoother in
[48] on the other.

The application of the correction from subdomain $\mathcal{S}_{i}$ consists in
the solution of a local saddle-point problem, defined by the subdomain degrees
of freedom, and corresponds to the local subdomain block $\mathbf{L}_{i}$. We
note that in the general case, the local problem is dependent on material
parameters on the one hand and the configuration of the elements in the local
neighborhood on the other; therefore, we assume the subdomains to be spatially
dependent.

####  3.1.1 Parallelization aspects

The proposed smoother is an additive operator, i.e., the subdomain corrections
in Equation (15) are applied additively. In a parallel computing setting, the
additive nature of the smoother operator is a major advantage as the subdomain
corrections can effectively be applied simultaneously. The application of the
subdomain corrections in parallel follows the ownership of the pressure
degrees of freedom in the distributed computational domain, where
$\mathcal{S}_{i}$ is owned by the process that owns $p_{i}$. Since pressure
DoFs are uniquely owned, each subdomain is owned by exactly one process.
Consequently, a given process is responsible for $n_{p}^{\texttt{proc}}$
subdomains, where $n_{p}^{\texttt{proc}}$ denotes the number of local pressure
DoFs owned by the process.

In terms of data communication, we denote as process local a given subdomain
if all of its degrees of freedom are owned by the same process and as off
process otherwise. Process-local subdomains do not require any communication
as all the necessary data for their application is available locally on the
corresponding process. On the other hand, the degrees of freedom of off-
process subdomains, which occur near process interfaces, are only partially
owned by the corresponding process; therefore, off-process subdomains require
the communication of the non-local degrees of freedom. We note that the
pressure degrees of freedom in a given subdomain are either local or available
through the ghost layer, and only velocity degrees of freedom belonging to
subdomains on process interfaces may require data communication beyond the
ghost layer.

Given the independence between subdomains, the smoother operator in Equation
(15) can be replicated exactly in parallel, where the transfer of the non-
local DoFs of off-process subdomains is the only necessary communication.
Therefore, the smoother operator is independent of the number of processes in
parallel. We note that $n_{\mathcal{S}}^{\texttt{offp}}\ll
n_{p}^{\texttt{proc}}$, where $n_{\mathcal{S}}^{\texttt{offp}}$ is the number
of off-process subdomains, and the associated communication overhead is,
therefore, small.

####  3.1.2 Cache policies

The application of the subdomain corrections can be broken down into three
steps: the retrieving of the local subdomain problem, the solution of the
local problem and the application of the local correction. Given that the
smoother operator in Equation (15) is typically applied several times, the
optimization of these steps is clearly motivated from a computational
perspective, leading naturally to three cache policies discussed below, see
also, [47]. Given that the local subdomain problems are relatively small, we
solve the local problems down to machine accuracy by computing the LU
factorization of the local block $\mathbf{L}_{i}$ using a direct solver.

The first of the three cache policies, denoted as cache_matrix, concerns
itself with the elimination of the first step above, where the local subdomain
problem is retrieved and stored once during the initialization of the smoother
operator. Assuming that the global system of equations is stored in a sparse
matrix format, the retrieving of the subdomain degrees of freedom, which are
not, in general, stored in adjacent rows, is often costly since sparse matrix
formats are typically not optimized for such operations. We further note that
the local subdomain problem is itself sparse and can, therefore, be stored
using a sparse format in order to minimize the memory footprint of the
cache_matrix policy. The application of a given subdomain correction using the
cache_matrix policy then consists in the inversion of the local block and
updating the local residual vector with the local subdomain correction.

A more aggressive approach, denoted as cache_inverse, is to compute and store
the inverse of the local subdomain problems during the initialization of the
smoother operator. The inversion of the local blocks $\mathbf{L}_{i}$ is by
far the most computationally intensive step in the application of the
subdomain corrections; therefore, the cache_inverse policy is expected to
result in a significant computational gain. On the other hand, it should be
noted that the inverse of the local subdomain problem is in general a dense
matrix, and hence at first glance, the cache_inverse policy may seem to entail
a heavy penalty in terms of memory consumption. However, the prolongation
operator $\tilde{\mathbf{R}}^{T}_{i}$ of the proposed smoother operator offers
an optimization opportunity upon closer inspection, namely as the prolongation
operator of subdomain $\mathcal{S}_{i}$ contains only the pressure DoF $p_{i}$
and the velocity DoFs on the same node, it is only necessary to store the
corresponding rows from the local inverse. In other words, the cache_inverse
policy requires the storage of $1+d$ rows of the inverse of the local
subdomain problem, where $d$ is the spatial dimension.

The cache policies above favor computational efficiency at the cost of
increasing the memory footprint of the smoother operator. However, it may, in
particular cases, be desirable to reduce memory consumption as far as
possible, e.g., when the available main memory is extremely constrained. The
corresponding cache policy is denoted as cache_none, where all the steps
associated with the application of the smoother operator are performed on the
fly without the need to cache any extra matrices. Given the computational cost
associated with the retrieving and inversion of the local subdomain problem,
the presented cache policies are expected to offer a balance between
computational efficiency and memory footprint. The cache policies are further
investigated in Section 4.

##  4 Numerical experiments

Figure 1: The convergence of the geometric multigrid solver in the mesh study, where the grid hierarchy in Table 1 is solved. $\Omega_{e,h}^{l},l=2\ldots 7$ denotes the fine problem. All problems employ $\Omega_{e,h}^{1}$ as the coarse grid; therefore, finer problems use a deeper grid hierarchy. The reduction of the relative residual by $10^{9}$ is used as the convergence criterion Figure 2: The strong scaling of the geometric multigrid solver using different cache policies in the channel flow benchmark with $\Omega_{e,h}^{5}$ as the fine grid, see Table 1 with $n_{\texttt{proc}}=1,\ldots,512$. $t_{\mathbf{S}}$ denotes the runtime of the smoother per iteration on the fine grid, and $t_{\text{sol}}$ denotes the total solver runtime including the setup time. We note that the required memory by the cache_matrix policy exceeds the available main memory of up to two compute nodes Figure 3: The weak scaling of the geometric multigrid solver in the channel flow benchmark using the grid hierarchy in Table 1, where the number of degrees of freedom per process is kept roughly constant. $t_{\mathbf{S}}$ denotes the runtime of the smoother per iteration on the fine grid, and $t_{\text{sol}}$ denotes the total solver runtime Table 1: The grid hierarchy of the channel flow benchmark, used for the grid study as well as the strong and weak scaling studies. $n_{c}$ and $n_{\text{DoF}}$ denote the number of cells and degrees of freedom, respectively. $n_{\text{proc}}$ is the number of processes used in the weak scaling study and $n_{\text{it}}$ is the iteration count of the solver Grid | $n_{c}$ | $n_{\text{DoF}}$ | $\nicefrac{{n_{\text{DoF}}^{l}}}{{n_{\text{DoF}}^{l-1}}}$ | $n_{\text{proc}}$ | $n_{\text{it}}$
---|---|---|---|---|---
$\Omega_{e,h}^{1}$ | 262,144 | 790,275 | - | - | -
$\Omega_{e,h}^{2}$ | 526,516 | 1,583,127 | 2.00 | 3 | 14
$\Omega_{e,h}^{3}$ | 1,491,076 | 4,477,533 | 2.83 | 9 | 14
$\Omega_{e,h}^{4}$ | 4,999,612 | 15,004,455 | 3.35 | 30 | 7
$\Omega_{e,h}^{5}$ | 17,669,596 | 53,016,765 | 3.53 | 106 | 5
$\Omega_{e,h}^{6}$ | 62,884,444 | 188,665,497 | 3.56 | 376 | 5
$\Omega_{e,h}^{7}$ | 221,782,588 | 665,367,261 | 3.53 | 1330 | 5

In this section, we study the performance and scalability of the presented
geometric multigrid solver using a number of numerical benchmarks. More
specifically, the convergence of the geometric multigrid method is examined
using a mesh study in the first part. The proposed cache policies in Section
3.1.2 are studied next in terms of computational efficiency and memory
footprint, and the weak and strong scaling of the geometric multigrid solver
for large-scale problems is presented on a distributed-memory cluster.

We employ as benchmark the well-known channel flow problem, see [51], where
the inflow with a prescribed velocity profile enters a channel with dimensions
$2.2m\times 0.41m$ with a cylindrical obstacle with a diameter of $0.1m$ near
the inflow region. A no-slip wall condition is imposed on the bottom and top
sides of the channel. The kinematic viscosity of the fluid is
$\eta=\frac{1}{1000}\;\nicefrac{{m^{2}}}{{s}}$. The inflow profile is
described as

$\displaystyle u_{x}(0,y)$ $\displaystyle=\frac{4\bar{u}y(H-y)}{H^{2}}\quad$
$\displaystyle y\in[0,H],$ (16) $\displaystyle u_{y}(0,y)$
$\displaystyle=0\quad$ $\displaystyle y\in[0,H],$

where $\bar{u}=0.3\;\nicefrac{{m}}{{s}}$ and $H$ is the width of the channel.
The penalization parameter $\alpha$ in the finite cell method is chosen as
$10^{-10}$.

The computational grids, as shown in Table 1, are produced using adaptive mesh
refinement towards the boundary layers, i.e., the inflow and outflow regions,
the top and bottom walls and the surface of the cylinder. Geometric multigrid
is used as a standalone solver in order to better isolate its performance. The
reduction of the relative residual by $10^{9}$ is used as the convergence
criterion. We note that multigrid methods can be used as preconditioners in
Krylov subspace methods, which often leads to improved convergence. A
multigrid V cycle with six steps of pre- and post-smoothing is employed. A
damping factor of 0.8, which was the minimum amount observed to be necessary,
is applied to the smoother. We note that fewer smoothing steps were sufficient
for convergence; nevertheless, more smoothing steps led to more rapid
convergence and, given the relatively low computational cost of the smoother
operator, moderately more smoothing steps were observed to provide the solver
with a cost effective improvement. The reported runtime per smoother iteration
consists of the application of the smoother operator as well as the
synchronization of the residual vector.

The numerical experiments are carried out on a distributed-memory CPU cluster,
where each node is equipped with double-socket Intel Xeon Skylake Gold 6148
CPUs with 20 cores running at 2.4 GHz and 180 GB of DDR4 main memory. The
computing nodes are connected via a 100 GBit/s Intel Omni-Path Interconnect.
The numerical examples are run in pure MPI mode, where each node is filled
with up to 32 processes. An in-house C++ implementation is employed for the
numerical experiments in the following. p4est [14] and PETSc [5] are used for
grid manipulation and some linear algebra functionalities, respectively.

We focus on the convergence of the geometric multigrid solver first, where a
series of progressively finer problems with deeper grid hierarchies are
solved. The grid hierarchy in Table 1 is employed, where the fine grids
$\Omega_{e,h}^{l},l=2\ldots 7$ are solved using $\Omega_{e,h}^{1}$ as the
coarse grid; therefore, larger problems employ a deeper grid hierarchy. The
convergence of the GMG solver is shown in Figure 1. It can be seen that the
iteration count of the solver remains bounded independent of both the problem
size and the depth of the grid hierarchy. Nevertheless, the solver tends to
favor deeper grid hierarchies, and the iteration count is observed to improve
for finer problems, which employ a deeper hierarchy, until it is stabilized.
We note that aside from the depth of the grid hierarchy, the observed behavior
is associated with the improved resolution of the boundary layers on finer
grids.

We focus on the scalability of the geometric multigrid solver and the
performance of the cache policies in Section 3.1.2 next. The strong scaling of
the solver with $\Omega_{e,h}^{5}$ as the fine grid is shown in Figure 2,
where the runtime per smoother iteration as well as the total solver runtime
using an increasing number of processes is reported. The performance of the
solver with the different cache policies is shown in the same figure, where it
can be observed that cache_inverse is by far the most efficient policy in
terms of total computational runtime. The cache_matrix policy is slightly more
efficient than the cache_none policy; however, at a significantly higher cost
in terms of memory footprint, e.g., the memory requirement of cache_matrix
exceeds the available main memory of up to two compute nodes. Finally,
cache_none does not require the storage of any extra matrices, and therefore,
offers an alternative with the lowest memory footprint; however, as the
retrieving and solution of the subdomain problems are performed on the fly,
its computational cost is significantly higher in comparison. We note that in
the absence of the memory optimization for the cache_inverse policy, explained
in Section 3.1.2, the memory footprint of cache_inverse would be even larger
than cache_matrix. However, given this memory optimization opportunity and
given the massive computational gain compared to cache_none and cache_matrix
policies, the cache_inverse should clearly be preferred for the presented
smoother operator minus exceptional cases where the available main memory in
extremely limited.

It can be observed in Figure 2 that both the runtime of the smoother operator
and the total solver runtime closely follow the ideal speedup. We note that as
the smoother operator is exactly replicated in parallel, see Section 3.1.1,
the convergence and iteration count of the solver is independent of the number
of processes.

The weak scaling of the solver with the cache_inverse policy is presented is
Figure 3, where the grid hierarchy in Table 1 is solved using a progressively
increasing number of processes such that the number of degrees of freedom per
process is roughly constant. For a given number of processes, the smallest
number of nodes is used, where each node is filled with up to 32 MPI
processes. The runtime of the smoother operator is observed to remain
virtually constant, and the total solver runtime remains roughly constant. The
observed difference in the total solver runtime between the three coarsest
problems and the finer problems can be imputed mainly to the difference in the
iteration count of the solver, see Table 1. In addition, we note that the
large variation between the fine and coarse grids may lead to micro-
parallelization on the coarser grids, where there is an imbalance between the
number of operations and the number of utilized processes, and may, therefore,
affect the scalability of multigrid methods. In such cases, an agglomeration
technique, where fewer processes are assigned to coarser grids, is typically
employed. Nevertheless, the geometric multigrid solver demonstrates excellent
weak scaling for the fine problems in the presented benchmarks.

##  5 Conclusions

In this work, we proposed an adaptive geometric multigrid method for the
solution of the finite cell formulation of the Stokes equations. The finite
cell method, mainly on account of the existence of cutcells where the physical
domain intersects the background computational mesh, leads to systems of
equations that are numerically ill-conditioned; therefore, the appropriate
treatment of cutcells is a crucial aspect of the multigrid method, see also
[49]. We proposed a smoother with favorable properties from a parallel
computing perspective, and discussed its computational and parallelization
aspects. The smoother operator, on account of its additive nature, can be
replicated in parallel exactly with little communication overhead; therefore,
the GMG solver with the proposed smoother is independent of the number of
processes. Furthermore, three cache policies for the smoother operator were
proposed, offering a balance between efficiency and on-the-fly computation. It
is shown that the cache_inverse policy, where the inverse of the local
subdomain problems are computed and stored once during the initialization of
the smoother operator, is by far the most computationally efficient policy in
comparison. Moreover, the smoother operator is shown to offer an optimization
opportunity in terms of memory footprint for the cache_inverse policy;
therefore, the cache_inverse policy is clearly preferred except in rare cases
where the available main memory is extremely constrained. The convergence and
parallel scalability of the geometric multigrid solver with the presented
smoother is studied using numerical benchmarks on a distributed-memory
cluster. The convergence of the GMG solver is shown to remain bounded
independent of both the problem size and the depth of the grid hierarchy. The
strong and weak scaling of the solver is observed to closely follow the ideal
speedup using numerical examples with more than 665 million degrees of
freedom. Given the small communication overhead for the exact replication of
the smoother operator in parallel and the excellent efficiency and scalability
of the solver, the proposed geometric multigrid solver is an attractive option
for the solution of large-scale finite cell problems on high-performance
computing machines.

Acknowledgments  Financial support was provided by the German Research
Foundation (Deutsche Forschungsgemeinschaft, DFG) in the framework of
subproject C4 of the Collaborative Research Center SFB 837 Interaction
Modeling in Mechanized Tunneling, grant number 77309832. This support is
gratefully acknowledged. We also gratefully acknowledge the computing time on
the computing cluster of the SFB 837 and the Department of Civil and
Environmental Engineering at Ruhr University Bochum, which was used for the
presented numerical studies.

## References

  * [1] Alireza Abedian, Jamshid Parvizian, Alexander Düster and Ernst Rank  “Finite cell method compared to h-version finite element method for elasto-plastic problems”  In _Applied Mathematics and Mechanics_ 35 Springer, 2014, pp. 1239–1248
  * [2] Alireza Abedian, Jamshid Parvizian, Alexander Düster and Ernst Rank  “The finite cell method for the J2 flow theory of plasticity”  In _Finite Elements in Analysis and Design_ 69 Elsevier, 2013, pp. 37–47
  * [3] Ivo Babuška  “The finite element method with penalty”  In _Mathematics of computation_ 27.122, 1973, pp. 221–228
  * [4] Michael Bader  “Space-filling curves: an introduction with applications in scientific computing”  Springer Science & Business Media, 2012
  * [5] Satish Balay, William D. Gropp, Lois Curfman McInnes and Barry F. Smith  “Efficient Management of Parallelism in Object Oriented Numerical Software Libraries”  In _Modern Software Tools in Scientific Computing_ Birkhäuser Press, 1997, pp. 163–202
  * [6] Ted Belytschko, Nicolas Moës, Shuji Usui and Chandu Parimi  “Arbitrary discontinuities in finite elements”  In _International Journal for Numerical Methods in Engineering_ 50.4 Wiley Online Library, 2001, pp. 993–1013
  * [7] Pavel B Bochev, Clark R Dohrmann and Max D Gunzburger  “Stabilization of low-order mixed finite elements for the Stokes equations”  In _SIAM Journal on Numerical Analysis_ 44.1 SIAM, 2006, pp. 82–101
  * [8] Dietrich Braess and Regina Sarazin  “An efficient smoother for the Stokes problem”  In _Applied Numerical Mathematics_ 23.1 Elsevier, 1997, pp. 3–19
  * [9] James H Bramble, Joseph E Pasciak and Apostol T Vassilev  “Analysis of the inexact Uzawa algorithm for saddle point problems”  In _SIAM Journal on Numerical Analysis_ 34.3 SIAM, 1997, pp. 1072–1092
  * [10] Erik Burman  “Ghost penalty”  In _Comptes Rendus Mathematique_ 348.21, 2010, pp. 1217–1220  DOI: https://doi.org/10.1016/j.crma.2010.10.006
  * [11] Erik Burman and Peter Hansbo  “Fictitious domain finite element methods using cut elements: I. A stabilized Lagrange multiplier method”  In _Computer Methods in Applied Mechanics and Engineering_ 199.41-44 Elsevier, 2010, pp. 2680–2686
  * [12] Erik Burman and Peter Hansbo  “Fictitious domain finite element methods using cut elements: II. A stabilized Nitsche method”  In _Applied Numerical Mathematics_ 62.4 Elsevier, 2012, pp. 328–341
  * [13] Erik Burman et al.  “CutFEM: discretizing geometry and partial differential equations”  In _International Journal for Numerical Methods in Engineering_ 104.7 Wiley Online Library, 2015, pp. 472–501
  * [14] Carsten Burstedde, Lucas C Wilcox and Omar Ghattas  “p4est: Scalable algorithms for parallel adaptive mesh refinement on forests of octrees”  In _SIAM Journal on Scientific Computing_ 33.3 SIAM, 2011, pp. 1103–1133
  * [15] Clark R Dohrmann and Pavel B Bochev  “A stabilized finite element method for the Stokes problem based on polynomial pressure projections”  In _International Journal for Numerical Methods in Fluids_ 46.2 Wiley Online Library, 2004, pp. 183–201
  * [16] John Dolbow and Isaac Harari  “An efficient finite element method for embedded interface problems”  In _International journal for numerical methods in engineering_ 78.2 Wiley Online Library, 2009, pp. 229–252
  * [17] Alexander Düster, Jamshid Parvizian, Zhengxiong Yang and Ernst Rank  “The finite cell method for three-dimensional problems of solid mechanics”  In _Computer methods in applied mechanics and engineering_ 197.45-48 Elsevier, 2008, pp. 3768–3782
  * [18] Howard Elman et al.  “Block preconditioners based on approximate commutators”  In _SIAM Journal on Scientific Computing_ 27.5 SIAM, 2006, pp. 1651–1668
  * [19] Howard C Elman and Gene H Golub  “Inexact and preconditioned Uzawa algorithms for saddle point problems”  In _SIAM Journal on Numerical Analysis_ 31.6 SIAM, 1994, pp. 1645–1661
  * [20] Anand Embar, John Dolbow and Isaac Harari  “Imposing Dirichlet boundary conditions with Nitsche’s method and spline-based finite elements”  In _International journal for numerical methods in engineering_ 83.7 Wiley Online Library, 2010, pp. 877–898
  * [21] Alexandre Ern and Jean-Luc Guermond  “Theory and practice of finite elements”  Springer, 2004
  * [22] Robert Eymard, Thierry Gallouët and Raphaèle Herbin  “Finite volume methods”  In _Handbook of numerical analysis_ 7 Elsevier, 2000, pp. 713–1018
  * [23] Sonia Fernández-Méndez and Antonio Huerta  “Imposing essential boundary conditions in mesh-free methods”  In _Computer methods in applied mechanics and engineering_ 193.12-14 Elsevier, 2004, pp. 1257–1275
  * [24] Bernd Flemisch and Barbara I Wohlmuth  “Stable Lagrange multipliers for quadrilateral meshes of curved interfaces in 3D”  In _Computer Methods in Applied Mechanics and Engineering_ 196.8 Elsevier, 2007, pp. 1589–1602
  * [25] Martin Jakob Gander  “Schwarz methods over the course of time”  In _Electronic transactions on numerical analysis_ 31, 2008, pp. 228–255
  * [26] R Glowinski and Yu Kuznetsov  “Distributed Lagrange multipliers based on fictitious domain method for second order elliptic problems”  In _Computer Methods in Applied Mechanics and Engineering_ 196.8 Elsevier, 2007, pp. 1498–1506
  * [27] Wolfgang Hackbusch  “Multi-grid methods and applications”, Springer Series in Computational Mathematics  Springer Berlin, Heidelberg, 1985
  * [28] Anita Hansbo and Peter Hansbo  “An unfitted finite element method, based on Nitsche’s method, for elliptic interface problems”  In _Computer methods in applied mechanics and engineering_ 191.47-48 Elsevier, 2002, pp. 5537–5552
  * [29] John Jomo et al.  “Hierarchical multigrid approaches for the finite cell method on uniform and multi-level hp-refined grids”  In _Computer Methods in Applied Mechanics and Engineering_ 386 Elsevier, 2021, pp. 114075
  * [30] David Kay, Daniel Loghin and Andrew Wathen  “A preconditioner for the steady-state Navier–Stokes equations”  In _SIAM Journal on Scientific Computing_ 24.1 SIAM, 2002, pp. 237–256
  * [31] Axel Klawonn and Luca F Pavarino  “A comparison of overlapping Schwarz methods and block preconditioners for saddle point problems”  In _Numerical linear algebra with applications_ 7.1 Wiley Online Library, 2000, pp. 1–25
  * [32] Axel Klawonn and Luca F Pavarino  “Overlapping Schwarz methods for mixed linear elasticity and Stokes problems”  In _Computer Methods in Applied Mechanics and Engineering_ 165.1-4 Elsevier, 1998, pp. 233–245
  * [33] Randall J LeVeque  “Finite difference methods for ordinary and partial differential equations: steady-state and time-dependent problems”  SIAM, 2007
  * [34] Jian Li and Yinnian He  “A stabilized finite element method based on two local Gauss integrations for the Stokes equations”  In _Journal of Computational and Applied Mathematics_ 214.1 Elsevier, 2008, pp. 58–65
  * [35] Rajat Mittal and Gianluca Iaccarino  “Immersed boundary methods”  In _Annu. Rev. Fluid Mech._ 37 Annual Reviews, 2005, pp. 239–261
  * [36] Joachim Nitsche  “Über ein Variationsprinzip zur Lösung von Dirichlet-Problemen bei Verwendung von Teilräumen, die keinen Randbedingungen unterworfen sind”  In _Abhandlungen aus dem mathematischen Seminar der Universität Hamburg_ 36.1, 1971, pp. 9–15  Springer
  * [37] J Parvizian, A Düster and E Rank  “Topology optimization using the finite cell method”  In _Optimization and Engineering_ 13.1 Springer, 2012, pp. 57–78
  * [38] Jamshid Parvizian, Alexander Düster and Ernst Rank  “Finite cell method”  In _Computational Mechanics_ 41.1 Springer, 2007, pp. 121–133
  * [39] Suhas V Patankar and D Brian Spalding  “A calculation procedure for heat, mass and momentum transfer in three-dimensional parabolic flows”  In _Numerical prediction of flow, heat transfer, turbulence and combustion_ Elsevier, 1972, pp. 54–73
  * [40] Luca F Pavarino  “Indefinite overlapping Schwarz methods for time-dependent Stokes problems”  In _Computer methods in applied mechanics and engineering_ 187.1-2 Elsevier, 2000, pp. 35–51
  * [41] Charles S Peskin  “The immersed boundary method”  In _Acta numerica_ 11 Cambridge University Press, 2002, pp. 479–517
  * [42] Frits Prenter et al.  “Multigrid solvers for immersed finite element methods and immersed isogeometric analysis”  In _Computational Mechanics_ 65 Springer, 2019, pp. 1–32
  * [43] M Ranjbar et al.  “Using the finite cell method to predict crack initiation in ductile materials”  In _Computational Materials Science_ 82 Elsevier, 2014, pp. 427–434
  * [44] Ernst Rank et al.  “Geometric modeling, isogeometric analysis and the finite cell method”  In _Computer Methods in Applied Mechanics and Engineering_ 249 Elsevier, 2012, pp. 104–115
  * [45] Torgeir Rusten and Ragnar Winther  “A preconditioned iterative method for saddlepoint problems”  In _SIAM Journal on Matrix Analysis and Applications_ 13.3 SIAM, 1992, pp. 887–904
  * [46] Yousef Saad  “Iterative methods for sparse linear systems”  siam, 2003
  * [47] S Saberi, G Meschke and A Vogel  “An Efficient Parallel Adaptive GMG Solver for Large-Scale Stokes Problems”  In _European Conference on Parallel Processing_ , 2023, pp. 694–709  Springer
  * [48] S. Saberi, G. Meschke and A. Vogel  “A restricted additive Vanka smoother for geometric multigrid”  In _Journal of Computational Physics_ 459 Elsevier, 2022, pp. 111123
  * [49] S. Saberi, G. Meschke and A. Vogel  “Adaptive geometric multigrid for the mixed finite cell formulation of Stokes and Navier–Stokes equations”  In _International Journal for Numerical Methods in Fluids_ 95.7 Wiley Online Library, 2023, pp. 1035–1053  DOI: https://doi.org/10.1002/fld.5180
  * [50] S. Saberi, A. Vogel and G. Meschke  “Parallel Finite Cell Method with Adaptive Geometric Multigrid”  In _Euro-Par 2020: Parallel Processing_ Cham: Springer International Publishing, 2020, pp. 578–593  Springer
  * [51] Michael Schäfer et al.  “Benchmark computations of laminar flow around a cylinder”  In _Flow simulation with high-performance computers II_ Springer, 1996, pp. 547–566
  * [52] Dominik Schillinger and Martin Ruess  “The Finite Cell Method: A review in the context of higher-order structural analysis of CAD and image-based geometric models”  In _Archives of Computational Methods in Engineering_ 22.3 Springer, 2015, pp. 391–455
  * [53] Dominik Schillinger et al.  “Small and large deformation analysis with the p-and B-spline versions of the Finite Cell Method”  In _Computational Mechanics_ 50.4 Springer, 2012, pp. 445–478
  * [54] David Silvester and Andrew Wathen  “Fast iterative solution of stabilised Stokes systems part II: using general block preconditioners”  In _SIAM Journal on Numerical Analysis_ 31.5 SIAM, 1994, pp. 1352–1367
  * [55] David Silvester, Howard Elman, David Kay and Andrew Wathen  “Efficient preconditioning of the linearized Navier–Stokes equations for incompressible flow”  In _Journal of Computational and Applied Mathematics_ 128.1-2 Elsevier, 2001, pp. 261–279
  * [56] S Pratap Vanka  “Block-implicit multigrid solution of Navier-Stokes equations in primitive variables”  In _Journal of Computational Physics_ 65.1 Elsevier, 1986, pp. 138–158
  * [57] Rüdiger Verfürth  “A multilevel algorithm for mixed problems”  In _SIAM journal on numerical analysis_ 21.2 SIAM, 1984, pp. 264–271
  * [58] Gabriel Wittum  “Multi-grid methods for Stokes and Navier-Stokes equations”  In _Numerische Mathematik_ 54.5 Springer, 1989, pp. 543–563
  * [59] Nils Zander et al.  “The finite cell method for linear thermoelasticity”  In _Computers & Mathematics with Applications_ 64.11 Elsevier, 2012, pp. 3527–3541
  * [60] T Zhu and SN Atluri  “A modified collocation method and a penalty formulation for enforcing the essential boundary conditions in the element free Galerkin method”  In _Computational Mechanics_ 21.3 Springer, 1998, pp. 211–222


# Anatomy of OntoGUM—Adapting GUM to the OntoNotes Scheme to Evaluate
Robustness of SOTA Coreference Algorithms

Yilun Zhu Department of Linguistics, Georgetown University  Sameer Pradhan
Linguistic Data Consortium, University of Pennsylvania  cemantix.org  Amir
Zeldes Department of Linguistics, Georgetown University

###### Abstract

SOTA coreference resolution produces increasingly impressive scores on the
OntoNotes benchmark. However lack of comparable data following the same scheme
for more genres makes it difficult to evaluate generalizability to open domain
data. Zhu et al. (2021) introduced the creation of the OntoGUM corpus for
evaluating geralizability of the latest neural LM-based end-to-end systems.
This paper covers details of the mapping process which is a set of
deterministic rules applied to the rich syntactic and discourse annotations
manually annotated in the GUM corpus. Out-of-domain evaluation across 12
genres shows nearly 15-20% degradation for both deterministic and deep
learning systems, indicating a lack of generalizability or covert overfitting
in existing coreference resolution models.

##  1 Introduction

Coreference resolution is the task of grouping referring expressions that
point to the same entity, such as noun phrases and the pronouns that refer to
them. The task entails detecting correct mention or ‘markable’ boundaries and
creating a link with previous mentions, or antecedents. A coreference chain is
a series of decisions which groups the markables into clusters. As a key
component in Natural Language Understanding (NLU), the task can benefit a
series of downstream applications such as Entity Linking, Dialogue Systems,
Machine Translation, Summarization, and more Poesio et al. (2016).

In recent years, deep learning models have achieved high scores in coreference
resolution. The end-to-end approach Lee et al. (2017, 2018) jointly scoring
mention detection and coreference resolution currently not only beats earlier
rule-based and statistical methods but also outperforms other deep learning
approaches Wiseman et al. (2016); Clark and Manning (2016a, b). Additionally,
language models trained on billions of words significantly improve performance
by providing rich word and context-level information for classifiers (Lee et
al., 2018; Joshi et al., 2019a, b).

Genre |  Documents |  Tokens |  Mentions |  Proper |  Pron. |  Other |  Clusters
---|---|---|---|---|---|---|---
academic |  16 |  15,112 |  1,232 |  283 |  262 |  687 |  421
bio |  20 |  17,963 |  2,312 |  934 |  796 |  582 |  487
conversation |  5 |  5,701 |  1,027 |  40 |  728 |  259 |  176
fiction |  18 |  16,312 |  2,740 |  259 |  1,700 |  781 |  469
interview |  19 |  18,060 |  2,622 |  501 |  1,223 |  898 |  608
news |  21 |  14,094 |  1,803 |  796 |  340 |  667 |  477
reddit |  18 |  16,286 |  2,297 |  117 |  1,336 |  844 |  578
speech |  5 |  4,834 |  601 |  171 |  245 |  185 |  134
textbook |  5 |  5,379 |  466 |  108 |  165 |  193 |  133
vlog |  5 |  5,189 |  882 |  22 |  600 |  260 |  149
voyage |  17 |  14,967 |  1,339 |  564 |  300 |  475 |  348
whow |  19 |  16,927 |  2,057 |  53 |  1,001 |  1,003 |  491
Total |  168 |  150,824 |  19,378 |  3,848 |  8,696 |  68,34 |  4,471
Table 1: Genre-breakdown Statistics of OntoGUM.

However, scores on the identity coreference layer of the benchmark OntoNotes
dataset Pradhan et al. (2013) do not reflect the generalizability of these
systems. Moosavi and Strube (2017) pointed out that lexicalized coreference
resolution models, including neural models using word embeddings, face a
covert overfitting problem because of a large overlap between the vocabulary
of coreferring mentions in the OntoNotes training and evaluation sets. This
suggests that higher scores on OntoNotes-test may not indicate a better
solution to the coreference resolution task.

To investigate the generalization problem of neural models, several projects
have tested other datasets consistent with the OntoNotes scheme. Moosavi and
Strube (2018) conducted out-of-domain evaluation on WikiCoref Ghaddar and
Langlais (2016), a small dataset employing the same coreference definitions.
Results showed that neural models (with fixed embeddings) do not achieve
comparable performance (16.8% degradation in score) to scores on OntoNotes.
More recently, the e2e model using BERT Joshi et al. (2019b) showed gains on
the GAP corpus Webster et al. (2018) using contextualized embeddings; however
GAP only contains name-pronoun coreference, a very specific subset of
coreference, and is limited in domain to the same single source -- Wikipedia.

Though previous work has already identified the overfitting problem, it has
three main shortcomings. First, the scale of out-of-domain evaluation has been
small and homogeneous: WikiCoref only contains 30 documents with $\sim$60K
tokens, much smaller than the OntoNotes test set, and the single genre Wiki
domain in both WikiCoref and GAP is arguably not very far from some OntoNotes
materials. Second, pretrained LMs, e.g. BERT Devlin et al. (2019), popularized
after the WikiCoref paper, can learn better representations of markables and
surrounding sentences. Aside from GAP, which targets a highly specific
subtask, no study has investigated whether contextualized embeddings encounter
the same overfitting problem identified by Moosavi and Strube. Third, previous
work may underestimate the performance degradation on WikiCoref in particular
due to bias: In Moosavi and Strube (2018), embeddings were also trained on
Wikipedia themselves, potentially making it easier for the model to learn
coreference relations in Wikipedia text, despite limitations in other genres.

In this paper, we explore the generalizability of existing coreference models
on a new benchmark dataset, which we make freely available. Compared with work
using WikiCoref and GAP, our contributions can be summarized as follows:

  * •

We propose OntoGUM, the largest open, gold standard dataset consistent with
OntoNotes, with 168 documents ($\sim$150K tokens, 19,378 mentions, 4,471 coref
chains) in 12 genres,111Written: News/Fiction/Bio/Academic/Forum/Travel/How-
to/Textbook; Spoken: Interview/Political/Vlog/Conversation. including
conversational genres, which complement OntoNotes for training and evaluation.

  * •

We show that the SOTA neural model with contextualized embeddings encounters
nearly 15% performance degradation on OntoGUM, showing that the overfitting
problem is not overcome by contextualized language models.

  * •

We give a genre-by-genre analysis for two popular systems, revealing relative
strengths and weaknesses of current approaches and the range of easier/more
difficult targets for coreference resolution.

##  2 Related Work

#### OntoNotes and similar corpora

OntoNotes is a human-annotated corpus with documents annotated with multiple
layers of linguistic information including syntax, propositions, named
entities, word senses, and within-document coreference (Weischedel et al.,
2011; Pradhan et al., 2013). It covers three languages---English, Chinese and
Arabic. The English subcorpus has 3,493 documents and $\sim$1.6 million words
annotated for coreference. WikiCoref, which is annotated for anaphoric
relations, has 30 documents from English Wikipedia Ghaddar and Langlais
(2016), containing 7,955 mentions in 1,785 chains, following OntoNotes
guidelines.

#### GUM

The Georgetown University Multilayer (GUM) corpus (Zeldes, 2017) is an open-
source corpus of richly annotated texts from 12 genres, including 168
documents and over 150K tokens. Though it originally contains more coreference
phenomena than OntoNotes using more exhaustive guidelines, it also contains
rich syntactic, semantic and discourse annotations which allow us to create
the OntoGUM dataset described below. The syntactic annotations, which consist
of manually annotated Universal Dependencies trees de Marneffe et al. (2021),
are particularly useful in analyzing and converting the GUM corpus. We also
note that due to its smaller size (currently about 10% the size of the
OntoNotes coreference dataset), it is not possible to train SOTA neural
approaches directly on this dataset while maintaining strong performance.

#### Other corpora

As mentioned above, GAP is a gender-balanced labeled corpus of ambiguous
pronoun-name pairs, used for out-of-domain evaluation but limited in
coreferent types and genre. Several other comprehensive coreference datasets
exist as well, such as ARRAU Poesio et al. (2018) and PreCo Chen et al.
(2018), but these corpora cannot be used for out-of-domain evaluation because
they do not follow the OntoNotes scheme. Their conversion has not been
attempted to date.

#### Coreference resolution systems

Prior to the introduction of deep learning systems, the coreference task was
approached using deterministic linguistic rules (Lee et al., 2013; Recasens et
al., 2013) and statistical approaches (Durrett and Klein, 2013, 2014). More
recently, three neural models achieved SOTA performance on this task: 1)
ranking the candidate mention pairs (Wiseman et al., 2015; Clark and Manning,
2016a), 2) modeling global features of entity clusters (Clark and Manning,
2015, 2016b; Wiseman et al., 2016), and 3) end-to-end (e2e) approaches with
joint loss for mention detection and coreferent pair scoring Lee et al. (2017,
2018); Fei et al. (2019). The e2e method has become the dominant one, gaining
the best scores on OntoNotes. To investigate differences between deterministic
and deep learning models on unseen data, we evaluate the two approaches on
OntoGUM.

##  3 Dataset Conversion

GUM’s annotation scheme subsumes all markables and coreference chains
annotated in OntoNotes, meaning we do not need human annotation to recognize
additional mentions in the conversion process, though mention boundaries
differ subtly (e.g. for appositions and verbal mentions). Since GUM has gold
syntax trees, we were able to process the entire conversion automatically.
Additionally, most coreference evaluations use gold speaker information in
OntoNotes, which is available in GUM (for fiction, reddit and spoken data) and
could be assembled automatically as well.

The conversion is divided into two parts: removing coreference relations not
included in the OntoNotes scheme, and removing or adjusting markables. For
coreference relation deletion, we cut chains by removing expletive cataphora,
and identifying the definiteness of nominal markables, since indefinites
cannot be anaphors in OntoNotes - this was done based on the lemma of
determiners attached to the head token of the span (or lack of a determiner)
and the POS tag of the head. In addition to modifying existing mention
clusters, we also remove particular coreference relations and mention spans,
such as Noun-Noun compounding (only included in OntoNotes for proper-name
modifiers), bridging anaphora, copula predicates, nested entities
(‘i-within-i’= single mentions containing coreferring pronouns), and
singletons, i.e. mentions that are not referred to again (all not included in
OntoNotes). We note that singletons are removed as the final step, in order to
catch singletons generated during the conversion process. We also contract
verbal markable spans to their head verb, and merge appositive constructions,
which are explicitly marked in GUM, into single mentions, following the
OntoNotes guidelines. The order of conversion steps are shown in Table 2.

Order of conversion steps
---
> Remove bridging & cataphora
> Contract verbal spans
> Merge appositions
> Remove NN compounding
> Remove copula
> Remove nested entities
> Adjust chains by definiteness
> Remove singletons
Table 2: The order of the steps in the dataset conversion from GUM to
OntoNotes scheme.

###  3.1 Coreference relations

#### Cataphora

Cataphora encompasses pronominal elements, including demonstratives, e.g.
those, which precede an occurrence of a non-pronominal element that occurs
within the same utterance and resolves their discourse referent. GUM specifies
cataphora in the coreference annotation while OntoNotes only annotates
pronominal markables and discards the resolved non-pronominal elements.

Unlike other relations, cataphora ‘points forward’, i.e. it is resolved by
finding a subsequent lexical phrase corresponding to an earlier underspecified
pronoun. As in (3.1), the pronoun it (bolded in the box) is resolved by the
subsequent markable within the same utterance.

Before: it ’s good [border-style=solid,none,solid,solid,border-color=black]to
be able to do well [border-style=solid,solid,solid,none,border-color=black]at
the World Cup , to be placed , but it also means that you get a really good
opportunity to know where you ’re at in that two year gap between the
Paralympics .

After: it ’s good [border-style=solid,none,solid,solid,border-color=black]to
be able to do well [border-style=solid,solid,solid,none,border-color=black]at
the World Cup , to be placed , but it also means that you get a really good
opportunity to know where you ’re at in that two year gap between the
Paralympics .

Because GUM annotates coreference types for each relation, We create a
heuristic algorithm to process cataphora. As in (3.1), the expletive pronoun
(dashed box) is removed from the cluster it originally belongs to, leaving it
as a singleton. Other coreference relations remain the same in that cluster.

#### Definiteness

A definite marker indicates the referent is identifiable in a given context
while indefinite markers often function to introduce new entities not
mentioned before. Following these tendencies, OntoNotes does not allow
coreference relations between an indefinite nominal and any kind of
antecedents. GUM, however, only considers whether the markables refer to the
same entity or not. For example, the indefinite noun phrase a farm several
miles outside of town in (3.1) can occur in the middle of the coreferring
chain.

Before: Rachel Rook took Carroll home to meet her parents two months after she
first slept with him ... her parents lived on a farm several miles outside of
town ... He knew that they never left the farm ...

After: Rachel Rook took Carroll home to meet her parents two months after she
first slept with him ... her parents lived on a farm several miles outside of
town ... He knew that they never left the farm ...

We use the POS tags, dependency labels, and lemmas to distinguish definite and
indefinite markables. A definite nominal markable satisfies one of the
following cases: (1) it is a pronoun; (2) the head noun is possessed; (3) it
is a proper noun; and (4) anything which has the dependency relation det with
a definite determiner lemma such as the, that, etc. The converted document
looks like (3.1), where the indefinite nominal phrase and its original
antecedent (dashed box) fall in different clusters and the indefinite markable
is the first mention in the new cluster222If the markable home also has an
antecedent, the coreference relation is not affected by the chain-breaking
operation..

###  3.2 Markables

#### Noun-Noun compounding

In Universal Dependencies (UD), a noun compound is a relation that connects
common noun modifiers. GUM marks the noun compounding span in coreference
annotations while OntoNotes annotation guidelines do not permit any common
noun compound modifiers. As in (3.2), the two compounds are marked in one
coreference chain.

Before: Allergan Inc. said it received approval to sell the PhacoFlex
intraocular lens, the first foldable silicone lens available for cataract
surgery . The lens’ foldability enables it to be inserted in smaller incisions
than are now possible for cataract surgery . After: ... available for cataract
surgery ... possible for cataract surgery .

To convert the dataset, the conversion program recursively removes the
compounding construction from a coreference chain and create a singleton span
for that compound, as the two dashed markable spans in (3.2).

#### Bridging and split antecedents

Bridging coreference occurs when two entities do not corefer exactly, but the
basis for the identifiability of one referent is the previous mention of one
or more previous referents. Particularly, in GUM, an anaphor may have multiple
antecedents and each antecedent creates a part-whole relationship with the
referent (split antecedent). This part-whole relation, however, is not a valid
coreference relation in OntoNotes because two nominal mentions are not
semantically identical.

Before: Claire Bailey-Ross ... Andrew Beresford ... Daniel Smith ... In this
paper, we report upon the novel insights ... We will discuss the potential
implications ...

[column sep=0.15cm] ... & Claire Bailey-Ross & ... & we
[edge unit distance=1ex]42bridge:aggr

After: Claire Bailey-Ross ... Andrew Beresford ... Daniel Smith ... In this
paper, we report upon the novel insights ... We will discuss the potential
implications ...

As in the example (3.2), the three proper nouns link to the collective nominal
we. With the rich coreference annotation in GUM, all coreference relations
identified as bridge, including both split antecedent and other types of
bridging anaphora, are removed, possibly leaving the nominals with the
original bridging relations as singletons. The example (3.2) shows the
coreference relations after the conversion process. The proper names are
unlinked (dashed boxes) from the original cluster while the pronouns are not
affected.

#### Copula

Copula predicates are annotated in GUM while are not markables in OntoNotes.
If two markables are coreferred, the conversion process utilizes the UD
annotations to identify whether or not a copula construction is between the
two mention spans. If the root is within the second span and it is the head of
cop, we decide to remove the second span from the coreference chain.

Before: The viewing experience of art is a complex one ... The time it takes
...

[column sep=0.15cm] ... experience ... & is & a & complex & one
5root [edge unit distance=1ex]52cop [edge unit distance=2ex]51nsubj

After: The viewing experience of art is a complex one ... The time it takes
...

For example, in (3.2), the head noun one in the second span a complex one is
the root and the head of the copula is. Additionally, it corefers with a
markable that is the subject of the copula construction. Therefore, we unlink
the second span from the cluster and connect the first span with the markable
that the second span refers to. The post-conversion annotations are marked in
(3.2).

#### Nested entity

A proper noun may be included in a larger proper noun mention span, as in the
nested proper noun America within the span Bank of America. In OntoNotes, all
proper names are considered to be atomic, so that America will not be
annotated in the above example. Differently from OntoNotes, GUM allows all
nested entities to be considered as valid referents. Because a nominal mention
is a candidate referent, its possessive modifier, which is also considered as
a candidate referent, should be removed from the coreference relation.

Before: I ’m about to go visit and would like to know [border-
style=solid,none,solid,solid,border-color=black]the best way to communi-
[border-style=solid,solid,solid,none,border-color=black]cate with her if it ’s
helpful .

After: I ’m about to go visit and would like to know [border-
style=solid,none,solid,solid,border-color=black]the best way to communi-
[border-style=solid,solid,solid,none,border-color=black]cate with her if it ’s
helpful .

For example, in (3.2), it and the best way to communicate with her if it’s
helpful refer to the same entity, while the pronoun is within the span of the
noun phrase, so we remove it as in (3.2). In general, the conversion process
removes the nested entity when it is included by its antecedent.

#### Singletons

Singletons are markables that are not referred to by other mentions in a
document. GUM explicitly annotates all nominal spans while OntoNotes only
considers co-referring noun phrases as valid mention spans. Exemplified in
(3.2), the dashed box indicates that the span is not referred to in the
context.

Before: a unique collection of 17th Century Zurbarán paintings

The singleton removal process is the last layer for the conversion because
previous steps may delete coreference relations and create new markables that
are not referred to again.

###  3.3 Agreement study

To evaluate conversion accuracy, three annotators, including an original
OntoNotes project member, conducted an agreement study on 3 documents,
containing 2,500 tokens and 371 output mentions. Re-annotating from scratch
based on OntoNotes guidelines, the conversion achieves a span detection score
of $\sim$96 and CoNLL coreference score of $\sim$92, approximately the same as
human agreement scores on OntoNotes. After adjudication, the conversion was
found to make only 8/371 errors, in addition to 2 errors due to mistakes in
the original GUM data, meaning that degradation due to conversion errors is
marginal, and consistency should be close to the variability in OntoNotes
itself.

Genre | MUC |  B3 |  CEAFϕ4 |  | Mention Detection
---|---|---|---|---|---
P | R | F1 | P | R | F1 | P | R | F1 | Avg. F1 | P | R | F1
| dcoref
academic | 35.1 | 37.5 | 36.2 | 32.6 | 34.4 | 33.5 | 35.7 | 37.5 | 36.6 | 35.4 | 48.3 | 51.3 | 49.8
bio | 58.0 | 61.6 | 59.8 | 36.8 | 43.6 | 39.9 | 32.1 | 33.5 | 32.8 | 44.1 | 58.9 | 62.3 | 60.6
conversation | 62.2 | 52.9 | 57.1 | 40.5 | 36.7 | 38.5 | 37.1 | 38.2 | 37.6 | 44.4 | 76.6 | 67.8 | 72.0
fiction | 57.7 | 43.9 | 49.9 | 50.4 | 33.2 | 40.0 | 37.1 | 49.0 | 42.2 | 44.0 | 68.2 | 59.0 | 63.3
interview | 57.3 | 53.3 | 55.2 | 29.3 | 21.6 | 24.8 | 22.4 | 24.6 | 23.5 | 27.6 | 64.3 | 60.3 | 62.2
news | 57.6 | 55.2 | 56.4 | 45.7 | 42.3 | 44.0 | 39.6 | 32.5 | 35.7 | 45.3 | 44.0 | 50.2 | 46.9
reddit | 59.6 | 65.1 | 62.3 | 38.3 | 53.5 | 44.6 | 32.9 | 34.0 | 33.5 | 46.8 | 60.5 | 64.6 | 62.5
speech | 50.6 | 56.2 | 53.2 | 40.1 | 43.9 | 41.9 | 46.5 | 38.6 | 42.2 | 45.8 | 63.5 | 64.2 | 63.9
textbook | 36.0 | 34.2 | 35.1 | 32.7 | 31.0 | 31.9 | 23.9 | 39.9 | 29.9 | 32.3 | 18.1 | 45.8 | 26.0
vlog | 63.6 | 69.4 | 66.4 | 56.4 | 60.8 | 58.5 | 31.4 | 36.2 | 33.6 | 52.8 | 76.4 | 76.8 | 76.6
voyage | 34.7 | 37.1 | 35.9 | 30.7 | 28.7 | 29.7 | 29.7 | 35.8 | 32.5 | 32.7 | 46.6 | 62.4 | 53.3
whow | 35.8 | 24.2 | 28.9 | 30.0 | 24.5 | 27.0 | 29.9 | 34.0 | 31.8 | 29.2 | 50.0 | 42.9 | 46.2
All OntoGUM | 45.7 | 47.0 | 46.3 | 17.1 | 38.1 | 37.6 | 33.4 | 37.3 | 35.3 | 39.7 | 56.2 | 59.1 | 57.6
OntoNotes | 57.5 | 61.8 | 59.6 | 68.2 | 68.4 | 68.3 | 47.7 | 43.4 | 45.5 | 57.8 | 66.8 | 75.1 | 70.7
| Joshi et al. (2019a)
academic | 84.5 | 53.0 | 65.1 | 83.3 | 48.5 | 61.3 | 83.2 | 47.0 | 60.1 | 62.2 | 91.0 | 55.2 | 68.7
bio | 85.8 | 74.7 | 79.8 | 61.4 | 64.3 | 62.8 | 65.4 | 49.9 | 56.6 | 66.4 | 87.7 | 74.5 | 80.5
conversation | 85.0 | 73.4 | 78.7 | 67.9 | 64.5 | 66.2 | 70.2 | 51.1 | 59.1 | 68.0 | 93.0 | 77.9 | 84.8
fiction | 87.0 | 62.5 | 73.0 | 78.8 | 54.1 | 64.1 | 62.5 | 53.1 | 57.4 | 64.8 | 91.1 | 67.7 | 77.7
interview | 83.9 | 71.8 | 77.4 | 76.1 | 60.4 | 67.3 | 72.9 | 50.6 | 59.7 | 68.2 | 85.9 | 70.4 | 77.3
news | 65.3 | 65.8 | 65.5 | 60.1 | 59.6 | 59.9 | 58.9 | 54.3 | 56.5 | 60.6 | 71.9 | 70.5 | 71.2
reddit | 76.7 | 67.4 | 71.7 | 67.5 | 60.3 | 63.7 | 69.5 | 40.5 | 51.1 | 61.7 | 85.3 | 68.1 | 75.8
speech | 83.3 | 63.4 | 72.0 | 71.2 | 56.6 | 63.1 | 77.3 | 57.3 | 65.8 | 67.0 | 91.9 | 69.4 | 79.0
textbook | 50.0 | 66.6 | 57.1 | 45.2 | 65.7 | 53.6 | 55.6 | 55.6 | 55.6 | 55.5 | 60.0 | 72.2 | 65.5
vlog | 86.1 | 86.1 | 86.1 | 78.4 | 79.8 | 79.1 | 63.6 | 47.7 | 54.5 | 73.3 | 89.4 | 85.4 | 87.4
voyage | 69.0 | 70.4 | 69.7 | 52.7 | 64.1 | 57.9 | 65.9 | 53.0 | 58.8 | 62.1 | 78.9 | 75.5 | 77.2
whow | 84.8 | 40.9 | 55.2 | 83.4 | 39.2 | 53.3 | 71.4 | 57.4 | 63.6 | 57.4 | 93.2 | 52.4 | 67.1
All OntoGUM | 79.7 | 66.3 | 72.4 | 69.5 | 58.58 | 63.7 | 67.7 | 50.7 | 58.0 | 64.6 | 85.4 | 69.2 | 76.5
OntoNotes | 85.8 | 84.8 | 85.3 | 78.3 | 77.9 | 78.1 | 76.4 | 74.2 | 75.3 | 79.6 | 89.1 | 86.5 | 87.8
Table 3: Results on the OntoGUM’s test dataset with the deterministic coref
model (top) and the SOTA coreference model (bottom). The underlined text is
the lowest score across 12 genres and bold text is the highest.

##  4 Experiments

We evaluate two systems on the 12 OntoGUM genres, using the official
CoNLL-2012 scorer Pradhan et al. (2012, 2014). The primary score is the
average F1 of three metrics -- MUC, B3, and CEAFϕ4.

#### Deterministic coreference model

We first run the deterministic system (dcoref, part of Stanford CoreNLP,
Manning et al. 2014) on the OntoGUM benchmark, as it remains a popular option
for off-the-shelf coreference resolution. As a rule-based system, it does not
require training data, so we directly test it on OntoGUM’s test set. However,
POS tags, lemmas, and named-entity (NER) information are predicted by CoreNLP,
which does have a domain bias favoring newswire. The system’s multi-sieve
structure and token-level features such as gender and number remain unchanged.
We expect that the linguistic rules will function similarly across datasets
and genres, notwithstanding biases of the tools providing input features to
those rules.

#### SOTA neural model

Combining the e2e approach with a contextualized LM and span masking is the
current SOTA on OntoNotes. The system utilizes the pretrained SpanBERT-large
model, fine-tuned on the OntoNotes training set. Hyperparameters are identical
to the evaluation of OntoNotes test to ensure comparable results between the
benchmarks. We note that while we choose the SOTA system as a ‘best case
scenario’, most off-the-shelf neural NLP toolkits (e.g. spaCy) actually use
somewhat simpler e2e models than SpanBERT-large, due to memory/performance
constraints.

##  5 Results

Genres |  PRON (R) |  Other (R) |  Total |  CoNLL |  Span
---|---|---|---|---|---
vlog |  600 (.66) |  309 (.34) |  909 |  1 |  1
interview |  1223 (.45) |  1485 (.55) |  2708 |  2 |  6
conversation |  729 (.61) |  323 (.39) |  1052 |  3 |  2
speech |  245 (.40) |  364 (.60) |  609 |  4 |  4
bio |  796 (.34) |  1529 (.66) |  2325 |  5 |  3
fiction |  1700 (.61) |  1091 (.39) |  2791 |  6 |  5
academic |  262 (.21) |  997 (.79) |  1259 |  7 |  10
voyage |  300 (.22) |  1053 (.78) |  1353 |  8 |  7
reddit |  1337 (.55) |  1077 (.45) |  2414 |  9 |  8
news |  340 (.19) |  1483 (.81) |  1823 |  10 |  9
whow |  1001 (.47) |  1129 (.53) |  2130 |  11 |  11
textbook |  165 (.34) |  315 (.66) |  480 |  12 |  12
Table 4: Mention-type counts (ratios) & ranks of SOTA scores by genre (CoNLL
score + span detection).

#### OntoGUM vs. OntoNotes

The last rows in each half of Table 3 give overall results for the systems on
each benchmark. e2e+SpanBERT encounters a substantial degradation of 15 points
(19%) on OntoGUM, likely due to lower test set lexical and stylistic overlap,
including novel mention pairs. We note that its average score of 64.6 is
somewhat optimistic, especially given that the system receives access to gold
speaker information wherever available (including in fiction, conversation and
interview, some of the better scoring genres), which is usually unrealistic.
dcoref, assumed to be more stable across genres, also sees losses on OntoGUM
of over 18 points (30%). We believe at least part of the degradation may be
due to mention detection, which is trained on different domains for both
systems (see the last three columns in the table). These results suggest that
input data from CoreNLP degrades substantially on OntoGUM, or that some types
of coreferent expressions in OntoGUM are linguistically distinct from those in
OntoNotes, or both, making OntoGUM a challenging benchmark for systems
developed using OntoNotes.

#### Comparing genres

Both systems degrade more on specific genres. For example, while vlog (with
gold speaker information) fares well for both systems, neither does well on
textbook, and even the SOTA system falls well below (or around) 60s for the
news, whow and textbook genres. This might be surprising for vlog, which
contains transcripts of spontaneous unedited speech from YouTube Creative
Commons vlogs quite unlike OntoNotes data; conversely the result is less
expected for carefully edited texts which are somewhat similar to data in
OntoNotes: OntoNotes contains roughly 30% newswire text, and it is not
immediately clear that GUM’s news section, which comes from recent Wikinews
articles, differs much in genre. Examples (5)--(5) illustrate incorrectly
predicted coreference chains from both sources and the type of language they
contain.

I’ve been here just crushing ultrasounds … I’ve been like crushing these all
day today … I got sick when I was on Croatia for vacation. I have no idea what
it says, but I think they’re cough drops. (example from a radiologist’s vlog,
incorrect: ultrasounds $\neq$ cough drops)

The report has prompted calls for all edible salt to be iodised … Tasmania was
excluded from [border-style=solid,none,solid,solid,border-color=black]the
study - where a voluntary iodine for- [border-
style=solid,none,solid,none,border-color=black]tification program using
iodised salt in [border-style=solid,solid,solid,none,border-color=black]bread,
is ongoing (newswire example, incorrect span and coref: [the study - where a
voluntary...])

These examples show that errors occur readily even in quite characteristic
news writing, while genre disparity by itself does not guarantee low
performance, as in the case of the vlogs whose lanugage is markedly different.
In sum, these observations suggest that accurate coreference for downstream
applications cannot be expected in some common well edited genres, despite the
prevalence of news data in OntoNotes (albeit specifically from the Wall Street
Journal, around 1990). This motivates the use of OntoGUM as a test set for
future benchmarking, in order to give the NLP community a realistic idea of
the range of performance we may see on contemporary data ‘in the wild’.

We also suspect that prevalence of pronouns and gold speaker information
produce better scores in the results. Table 4 ranks genres by their e2e CoNLL
score, and gives the proportions of pronouns, as well as score rankings for
span detection. Because pronouns are usually easier to detect and pair than
nouns (Durrett and Klein, 2013), more pronouns usually means higher scores. On
genres with more than 50% pronouns and gold speakers (vlog, interview,
conversation, speech, fiction) e2e gets much higher results, while genres with
few pronouns ($<$30%) have lower scores (academic, voyage, news). This
diversity over 12 genres supports the usefulness of OntoGUM, which can
evaluate the genrealizability of coreference systems.

##  6 Conclusion

This paper presented the mechanics of the conversion of the GUM corpus to the
OntoGUM version using the OntoNotes coreference scheme, creating the largest
open, gold standard coreference dataset following the OntoNotes scheme, which
adds several new genres (including more spoken data) to the OntoNotes family.
The corpus is automatically converted from GUM by modifying the existing
markable spans and coreference relations using multi-layer annotations, such
as dependency trees. Results showed a lack of generalizability of existing
systems, especially in genres low in pronouns and lacking speaker information.
We suspect that at least part of the success of SOTA approaches is due to
correct mention detection and high matching scores in genres rich in pronouns,
and more so with gold speaker information. Success for other types of mentions
in OntoNotes data appears to be much more sensitive to lexical features,
performing well on the benchmark test set with high lexical overlap to the
training data, but degrading very substantially outside of it, even on
newswire texts from our OntoGUM data. This supports use of this challenging
dataset for future work, which we hope will benefit evaluations of systems
targeting the OntoNotes standard.

## References

  * Chen et al. (2018) Hong Chen, Zhenhua Fan, Hao Lu, Alan Yuille, and Shu Rong. 2018.  PreCo: A large-scale dataset in preschool vocabulary for coreference resolution.  In _Proceedings of EMNLP 2018_ , pages 172--181, Brussels.
  * Clark and Manning (2015) Kevin Clark and Christopher D. Manning. 2015.  Entity-centric coreference resolution with model stacking.  In _Proceedings of ACL-IJCNLP 2015, Long Papers_ , pages 1405--1415, Beijing, China.
  * Clark and Manning (2016a) Kevin Clark and Christopher D. Manning. 2016a.  Deep reinforcement learning for mention-ranking coreference models.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 2256--2262, Austin, Texas.
  * Clark and Manning (2016b) Kevin Clark and Christopher D. Manning. 2016b.  Improving coreference resolution by learning entity-level distributed representations.  In _Proceedings of ACL 2016, Long Papers_ , pages 643--653, Berlin.
  * de Marneffe et al. (2021) Marie-Catherine de Marneffe, Christopher D. Manning, Joakim Nivre, and Daniel Zeman. 2021.  Universal Dependencies.  _Computational Linguistics_ , 47(2):255--308.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of NAACL 2019_ , pages 4171--4186, Minneapolis, MN.
  * Durrett and Klein (2013) Greg Durrett and Dan Klein. 2013.  Easy victories and uphill battles in coreference resolution.  In _Proceedings of EMNLP 2013_ , pages 1971--1982, Seattle, WA.
  * Durrett and Klein (2014) Greg Durrett and Dan Klein. 2014.  A joint model for entity analysis: Coreference, typing, and linking.  _TACL_ , 2:477--490.
  * Fei et al. (2019) Hongliang Fei, Xu Li, Dingcheng Li, and Ping Li. 2019.  End-to-end deep reinforcement learning based coreference resolution.  In _Proceedings of ACL 2019_ , pages 660--665, Florence, Italy.
  * Ghaddar and Langlais (2016) Abbas Ghaddar and Phillippe Langlais. 2016.  WikiCoref: An English coreference-annotated corpus of Wikipedia articles.  In _Proceedings of LREC 2016)_ , pages 136--142, Portorož, Slovenia.
  * Joshi et al. (2019a) Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel S. Weld, Luke Zettlemoyer, and Omer Levy. 2019a.  SpanBERT: Improving pre-training by representing and predicting spans.  _CoRR_ , abs/1907.10529.
  * Joshi et al. (2019b) Mandar Joshi, Omer Levy, Daniel S. Weld, and Luke Zettlemoyer. 2019b.  BERT for coreference resolution: Baselines and analysis.  In _Proceedings of EMNLP-IJCNLP 2019_ , pages 5803--5808, Hong Kong, China.
  * Lee et al. (2013) Heeyoung Lee, Angel Chang, Yves Peirsman, Nathanael Chambers, Mihai Surdeanu, and Dan Jurafsky. 2013.  Deterministic coreference resolution based on entity-centric, precision-ranked rules.  _Computational Linguistics_ , 39(4):885--916.
  * Lee et al. (2017) Kenton Lee, Luheng He, Mike Lewis, and Luke Zettlemoyer. 2017.  End-to-end neural coreference resolution.  In _Proceedings of EMNLP 2017_ , pages 188--197, Copenhagen, Denmark.
  * Lee et al. (2018) Kenton Lee, Luheng He, and Luke Zettlemoyer. 2018.  Higher-order coreference resolution with coarse-to-fine inference.  In _Proceedings of NAACL 2018, Short Papers_ , pages 687--692, New Orleans, LA.
  * Manning et al. (2014) Christopher D. Manning, Mihai Surdeanu, John Bauer, Jenny Finkel, Steven J. Bethard, and David McClosky. 2014.  The Stanford CoreNLP natural language processing toolkit.  In _ACL 2014 System Demonstrations_ , pages 55--60.
  * Moosavi and Strube (2017) Nafise Sadat Moosavi and Michael Strube. 2017.  Lexical features in coreference resolution: To be used with caution.  In _Proceedings of ACL 2017, Short Papers_ , pages 14--19, Vancouver, Canada.
  * Moosavi and Strube (2018) Nafise Sadat Moosavi and Michael Strube. 2018.  Using linguistic features to improve the generalization capability of neural coreference resolvers.  In _Proceedings of EMNLP 2018_ , pages 193--203, Brussels.
  * Poesio et al. (2018) Massimo Poesio, Yulia Grishina, Varada Kolhatkar, Nafise Moosavi, Ina Roesiger, Adam Roussel, Fabian Simonjetz, Alexandra Uma, Olga Uryupina, Juntao Yu, and Heike Zinsmeister. 2018.  Anaphora resolution with the ARRAU corpus.  In _Proceedings of CRAC 2018_ , pages 11--22, New Orleans, LA.
  * Poesio et al. (2016) Massimo Poesio, Roland Stuckardt, and Yannick Versley. 2016.  _Anaphora resolution_.  Springer.
  * Pradhan et al. (2014) Sameer Pradhan, Xiaoqiang Luo, Marta Recasens, Eduard Hovy, Vincent Ng, and Michael Strube. 2014.  Scoring coreference partitions of predicted mentions: A reference implementation.  In _Proceedings of ACL 2014_ , pages 30--35, Baltimore, MD.
  * Pradhan et al. (2013) Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Hwee Tou Ng, Anders Björkelund, Olga Uryupina, Yuchen Zhang, and Zhi Zhong. 2013.  Towards robust linguistic analysis using OntoNotes.  In _Proceedings of CoNLL 2013_ , pages 143--152, Sofia.
  * Pradhan et al. (2012) Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Olga Uryupina, and Yuchen Zhang. 2012.  CoNLL-2012 shared task: Modeling multilingual unrestricted coreference in OntoNotes.  In _Joint Conference on EMNLP and CoNLL - Shared Task_ , pages 1--40, Jeju Island, Korea.
  * Recasens et al. (2013) Marta Recasens, Marie-Catherine de Marneffe, and Christopher Potts. 2013.  The life and death of discourse entities: Identifying singleton mentions.  In _Proceedings of NAACL 2013_ , pages 627--633, Atlanta, Georgia.
  * Webster et al. (2018) Kellie Webster, Marta Recasens, Vera Axelrod, and Jason Baldridge. 2018.  Mind the GAP: A balanced corpus of gendered ambiguous pronouns.  _TACL_ , pages 605--617.
  * Weischedel et al. (2011) Ralph Weischedel, Eduard Hovy, Mitchell Marcus, Martha Palmer, Robert Belvin, Sameer Pradhan, Lance Ramshaw, and Nianwen Xue. 2011.  OntoNotes: A large training corpus for enhanced processing.  In Joseph Olive, Caitlin Christianson, and John McCary, editors, _Handbook of Natural Language Processing and Machine Translation: DARPA Global Autonomous Language Exploitation_. Springer.
  * Wiseman et al. (2015) Sam Wiseman, Alexander M. Rush, Stuart Shieber, and Jason Weston. 2015.  Learning anaphoricity and antecedent ranking features for coreference resolution.  In _Proceedings of ACL-IJCNLP 2015, Long Papers_ , pages 1416--1426, Beijing, China.
  * Wiseman et al. (2016) Sam Wiseman, Alexander M. Rush, and Stuart M. Shieber. 2016.  Learning global features for coreference resolution.  In _Proceedings of NAACL 2016_ , pages 994--1004, San Diego, CA.
  * Zeldes (2017) Amir Zeldes. 2017.  The GUM corpus: Creating multilayer resources in the classroom.  _Language Resources and Evaluation_ , 51(3):581--612.
  * Zhu et al. (2021) Yilun Zhu, Sameer Pradhan, and Amir Zeldes. 2021.  OntoGUM: Evaluating contextualized SOTA coreference resolution on 12 more genres.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 461--467, Online. Association for Computational Linguistics.