matrix, which we use in practice, are, up to a scaling of
$h^{-d/2}=2^{(dL)/2}$, spectrally equivalent due to the well-known
$L_{2}$-stability of the piecewise $d$-linear finite element basis.

First we study the convergence behavior of these different methods. To this
end, we consider the case $d=1$, we set $q=16$, $S=8$ and $P=100$. Thus the
size $N$ of the overall problem is fixed to $100\cdot 2^{8}$ with a size of
$2^{8}$ for each subproblem. Now we study the error reduction properties of
our fault-tolerant algorithms. To this end we consider, besides the case of no
fault at all, the cases where the faults are randomly generated in each cycle
and for each processor according to the Bernoulli distribution with different
fault-probabilities $p_{\text{fault}}=0.01,0.02,0.05,0.1$ and $0.2$. This way,
on average, one, two, five, ten and twenty processors fail in each iteration.
Since the faults are randomly distributed, we run the algorithms ten times and
show the resulting convergence curves for each run in transparent colors. We
additionally show the averaged convergence curve in bold color. Note here also
that, if the overlap parameter $\gamma$ is too small compared to the fault
rate $p_{\text{fault}}$, a proper fault recovery might no longer be possible
and, depending on the specific realization of random picks of faulty
processors, the respective run of the algorithm may no longer be able to
recover and may fail. These failed runs are discarded in the computation of
the average convergence rate. For the overlap parameter $\gamma=0.5,1,1.5,2$,
the results for the $\omega_{i}$-weighted balanced two-level
Richardson/Schwarz iteration and the correspondingly preconditioned conjugate
gradient method are shown in Figure 21.

Figure 21. Number of iterations (single runs and mean) of the fault-tolerant
version of the $\omega_{i}$-weighted balanced two-level additive
Schwarz/Richardson iteration (left) and the associated preconditioned
conjugate gradient method (right) for different fault probabilities and
different overlaps $\gamma=0.5,1,1.5,2,q=16,d=1$.

We see that in the $\omega_{i}$-weighted balanced Richardson case there is a
slight preasymptotic reduction of the initial error in the first iterations,
which shortens but is more profound the larger the values of
$p_{\text{fault}}$ and of $\gamma$ are. After that an asymptotic error
reduction can be observed which is nearly the same as for the non-faulty case.
A close inspection reveals that, depending on $p_{\text{fault}}$, this
asymptotic rate becomes slightly larger in the end compared to the non-faulty
case. This is however to be expected from our theory, compare also the bound
for the (asymptotic) rate in Theorem 3.3. The preasymptotic behavior stems
from the fact that a moderate number of faults indeed restores a certain
smoothing effect in the preasymptotic regime. This observed (small)
preasymptotic smoothing effect in the faulty cases can best be explained by
looking at all the fine grid points that belong to a failing processor. For
example, the overlap $\gamma=2$ and the associated weighting
$\omega_{i}I=\frac{1}{2\gamma+1}I=\frac{1}{5}I$ yields an (asymptotically)
optimal damping parameter of
$\xi_{\textrm{opt}}=2/(\lambda_{\textrm{min}}+\lambda_{\textrm{max}})\approx
1.86$ for the balanced preconditioner. Recall that $\omega_{0}$ is chosen as
one here. Then the effective preconditioner, including damping, can be seen to
be

(4.32) $\displaystyle\xi_{\textrm{opt}}C^{-1}_{(2),D,bal}$
$\displaystyle=\xi_{\textrm{opt}}(G^{T}C^{-1}_{(1),D}G+F)=\xi_{\textrm{opt}}(\frac{1}{5}G^{T}C^{-1}_{(1)}G+F)$
$\displaystyle=\xi_{\textrm{opt}}\frac{1}{5}G^{T}C^{-1}_{(1)}G+\xi_{\textrm{opt}}F\approx
0.37\leavevmode\nobreak\ G^{T}C^{-1}_{(1)}G+1.86\leavevmode\nobreak\ F.$

On the other hand, an intuitive way of weighting the respective fine grid
corrections in the iteration would be to average just over all fine grid
contributions per point, which resembles a certain smoothing of higher
frequency error components. For our example, this would yield a weighting
factor of $\frac{1}{5}$, i.e. the associated preconditioner would then be
$\frac{1}{5}G^{T}C^{-1}_{(1)}G+F$. A comparison of this preconditioner to the
above effective preconditioner (4.32), which involves the asymptotically
optimal dampening parameter $\xi_{\textrm{opt}}$, shows that the optimally
damped version shifts the balance between fine and coarse level more towards
the coarse side to achieve optimal convergence in the asymptotic regime. But
this in turn yields worse smoothing properties in the preasymptotic regime
compared to the dampening due to averaging, since the factor $0.37$ of the
fine grid contribution does not match the fact that each point is overlapped
by five fine subdomains. However, if we now consider the faulty cases, the
occurrence of a few faults brings the expected factor due to averaging closer
to this factor $0.37$. For example, if one of five neighboring processors
fails, one would expect an averaging factor of $\frac{1}{4}$, since now only
$4=5-1$ processors contribute to the correction at all points belonging to the
failing processor. In the case of two neighboring faults the expected
weighting factor due to averaging of $\frac{1}{3}$ in the points belonging to
both failing processors is now even closer to our asymptotically optimal fine
grid weighting of $0.37$. Therefore we see an improved initial smoothing
behavior for a moderate number of neighboring faults compared to the non-
faulty case simply due to the fact that the effective weighting parameter for
the fine grid, i.e. $\xi_{\textrm{opt}}\cdot\omega_{i}$, more closely
resembles the intuitive weighting factor due to averaging when a small number
of neighboring faults is present. Note however that, for larger values of
$p_{\text{fault}}$, the faulty cases still produce asymptotic rates that are
slightly worse than those of the non-faulty case. The somewhat better
convergence of the faulty cases is therefore only a result of the better
initial smoothing. Hence one could potentially improve the overall iteration
scheme by starting with the dampening parameter due to averaging and then
(gradually) switching to the optimal damping parameter after a certain number
of iterations. Further experiments showed that the non-faulty case
$p_{\textrm{fault}}=0$ then indeed exhibits better overall average convergence
than the faulty cases and that the convergence for the faulty cases gradually
deteriorates with rising values of $p_{\textrm{fault}}$. However, a proper
switching between these two damping parameters is not straightforward and the
convergence analysis of such a linear iterative method with dynamically
changing damping is quite involved. This is future work.

For the associated conjugate gradient method the convergence behavior is
different: We see that there is a sudden reduction of the initial error in the
first few iterations by a factor of about 100, which even grows slightly with
rising values of $\gamma$. This holds for all values of $p_{\text{fault}}$.
Here indeed the same smoothing effect due to averaging as in the faulty
Richardson case comes into play. However, instead of the fixed $\xi_{opt}$,
the conjugate gradient iteration determines the optimal step size in the
preconditioned search direction in the first iteration step. This leads to a
substantial smoothing effect in the first (few) iteration(s) and thus to the
steep drop of the error as seen in Figure 21 (right). After that the
asymptotic error reduction rate gradually sets in. It becomes monotonously
worse for rising values $p_{\text{fault}}$, as is intuitively to be expected.
Again, the necessary number of iterations is substantially smaller due to the
$\kappa$-versus-$\sqrt{\kappa}$ effect of the conjugate gradient method
compared to the simple linear Richardson iteration. The conjugate gradient
approach needs approximately a quarter of the iterations of the Richardson
approach in the non-faulty case. But it can be seen that the conjugate
gradient method tends to lose its advantage for larger values of
$p_{\text{fault}}$. For example, for $\gamma=2$ and $p_{\text{fault}}=0.1$, it
merely needs approximately half the number of iterations compared to the
Richardson approach. Moreover recall that runs, for which the recovery failed
due to a larger number of faults than can be repaired with the given values of
$\gamma$, are discarded in the computation of the average convergence rate.
This is the reason why for example for $\gamma=1/2$ in Figure 21 only averaged
convergence plots for $p_{\text{fault}}=0,0.01,0.02$ could be displayed,
whereas the curves for the larger values of $p_{\text{fault}}$ are missing. We
furthermore see that for the larger overlap $\gamma=2$ also faults with larger
fault probabilities of $p_{\text{fault}}$ up to 0.1 could be recovered from
and are treated successfully. We finally see that, if $p_{\text{fault}}$ is
larger than 0, we gradually obtain better results for larger overlap values
$\gamma$ as long as the runs are successful at all. For example, the number of
iterations improves with $p_{\text{fault}}=0.05$ from 50 for $\gamma=1$ to 43
for $\gamma=1.5$ and to 37 for $\gamma=2$. In the case $p_{\text{fault}}=0$
such a gain for rising values of $\gamma$ is still there, but it is
substantially smaller. In further experiments with larger values of $P$, like
for example $P=200$, we could observe analogous results with a further
improvement in convergence for the faulty situations. This is due to the
larger subdomain sizes and the exact subdomain solves, while now larger costs
are involved of course.

Altogether, we see that the occurrence of a moderate number of faults does not
have much influence on the convergence rate of the fault-tolerant version of
the balanced two-level additive Richardson iteration, as already predicted by
our convergence theory in Subsection 3.1. We observe that, due to the error
reduction in the preasymptotic regime, the necessary number of iterations even
decreases compared to the non-faulty case. Analogous observations could be
made for the plain Richardson iteration. Note that a similar behavior was
already present in the numerical experiments of [GO20], Figure 3, for the case
of a failure rate of eight percent using a Weibull distribution. For one, two,
five, ten and twenty failing processors in each iteration, which is indeed
already an extremely large number of failures regarding the short computation
time and the employed number of 100 processors, the influence on the number of
iterations is deteriorating slightly and is thus only marginal.

This is somewhat different when considering the associated preconditioned
conjugate gradient method. Its convergence in the non-faulty case is
substantially faster (i.e. it is dependent on $\sqrt{\kappa}$ instead of just
$\kappa$), however we no longer have a sound convergence theory in the faulty
situation. Indeed, the behavior of the conjugate gradient approach is much
more sensitive to the occurrence of faults, as can be seen on the right side
of the Figure 21. Now the deviation from the non-faulty convergence rate grows
substantially with rising values of $p_{\text{fault}}$. For example, for
$\gamma=2$, the necessary number of iterations grows in the
$\omega_{i}$-weighted balanced conjugate gradient case with
$p_{\text{fault}}=0,0.01,0.02,0.05,0.1$ with $25,28,31,37,54$. Note
furthermore that this dependence on the fault probability decreases with
rising values of the overlap parameter $\gamma$. But, all in all, the fault-
tolerant version of our conjugate gradient method still exhibits excellent
convergence properties in practice.

Next let us consider the convergence behavior of our $\omega_{i}$-weighted
balanced methods for a higher dimensional example. Here we focus on $d=6$ and
again set $P=100$ and $S=8$. Thus the size $N$ of the overall problem is fixed
to $100\cdot 2^{8}$ with a size of $2^{8}$ for each subproblem. Now we study
the error reduction property of our fault-tolerant algorithms and consider
again, besides the case of no fault at all, the cases where the faults are
randomly generated in each cycle for each processor according to a Bernoulli
distribution. We again employ the different fault-probabilities
$p_{\text{fault}}=0.01,0.02,0.05,0.1,0.2$ where, on average, one, two, five,
ten and twenty processors fail in each cycle. For the overlap parameter
$\gamma=0.5,1,1.5,2$, the results for the $\omega_{i}$-weighted balanced two-
level Richardson/Schwarz iteration and the correspondingly preconditioned
conjugate gradient method are shown in Figure 22.

Figure 22. Number of iterations (single runs and mean) of the fault-tolerant
version of the $\omega_{i}$-weighted balanced two-level additive
Schwarz/Richardson iteration (left) and the associated preconditioned
conjugate gradient method (right) for different fault probabilities and
different overlaps $\gamma=0.5,1,1.5,2,q=16,d=6$.

We now observe that, for the Richardson case, the preasymptotic error
reduction is substantially longer but smoothly changes to the asymptotic
convergence, which is in contrast to the one-dimensional case. Furthermore we
see that we obtain nearly the same convergence curves for all the different
values of $p_{\text{fault}}$ for a fixed value of $\gamma$. Moreover we now
find that the number of iterations stays the same or slightly worsens for
larger values of $p_{\text{fault}}$ if $\gamma$ increases. Again we observe
that there are no results for large values of $p_{\text{fault}}$ but small
overlap $\gamma$, which stems from the failure of the recovery process due to
insufficient redundancy. Consequently, $\gamma$ should be chosen small but
nevertheless still sufficiently large to guarantee the necessary redundancy
with respect to the fault rate $p_{\text{fault}}$. This holds for the
associated conjugate gradient method as well. Moreover, for
$p_{\text{fault}}=0$, the number of iterations is not very sensitive to
$\gamma$, it even marginally improves. For larger values of $p_{\text{fault}}$
it monotonously improves with rising values of $\gamma$. The corresponding
number of iterations is still smaller compared to the Richardson case,
possibly due to the $\sqrt{\kappa}$-versus-$\kappa$ effect, but the advantage
of the conjugate gradient method now tends to be not as profound anymore.
Especially for larger fault rates $p_{\text{fault}}$ and larger values of
$\gamma$ the conjugate gradient methods tends to lose its superiority over the
Richardson iteration and can even be inferior, as the example
$\gamma=2,p_{\text{fault}}=0.2$ shows: Now the Richardson approach only needs
25 iterations, whereas the corresponding conjugate gradient method needs 40
iterations. In any case, depending on the choice of the value of
$p_{\text{fault}}$, the value of $\gamma$ must be large enough to allow for a
proper recovery after faults.

Finally, we consider the weak scaleup behavior of our $\omega_{i}$-weighted
balanced algorithms under faults. We select a substantial overlap of
$\gamma=3$ and set $d=1,q=16,S=8$. Moreover we allow the values
$p_{\text{fault}}=0,0.01,0.02,0.05,0.1,0.2$. This corresponds to
$p_{\text{fault}}\cdot P$ faults in each cycle on average for varying numbers
of $P$. The resulting number of iterations are shown in Figure 23. The results
for the average convergence rate $\rho^{ave}$ and the asymptotic convergence
rate $\rho^{asy}$ are shown in Figure 24.

Figure 23. Number of iterations (mean) of the fault-tolerant version of the
$\omega_{i}$-weighted balanced two-level additive Schwarz/Richardson iteration
(left) and the associated conjugate gradient method (right) for different
fault probabilities, $\gamma=3,S=8,q=16,d=1$. Figure 24. Average and
asymptotic rates (mean) of the fault-tolerant version of the
$\omega_{i}$-weighted balanced two-level additive Schwarz/Richardson iteration
(left) and the associated conjugate gradient method (right) for different
fault probabilities, ${\gamma=3,}$ $S=8,q=16,d=1$.

We see that the weak scaling constant associated to the iterations, i.e. the
respective number of iterations for rising numbers of $P$, first (for
$p_{\text{fault}}=0.01,0.02,0.05,0.1$) marginally improves in the Richardson
case and then slightly deteriorates again ($p_{\text{fault}}=0.2$), which can
be explained by the preasymptotic behavior. In the conjugate gradient case it
monotonously deteriorates for rising values of $p_{\text{fault}}$ as
intuitively expected, but the corresponding iteration numbers are much better
than those for the Richardson iteration. An analogous behavior can be observed
for the average convergence rate $\rho^{ave}$. In addition the corresponding
weak scaling constant for the asymptotic convergence rate $\rho^{asy}$ behaves
similarly and is only worse by a value of about 0.02 and about 0.1 than for
$\rho^{ave}$ in the Richardson and conjugate gradient case, respectively.

At last, for the six-dimensional case, the weak scaleup behavior of our
$\omega_{i}$-weighted balanced algorithms under faults, i.e. the number of
iterations and the average and the asymptotic convergence rate, are shown in
the Figures 25 and 26.

Figure 25. Number of iterations (mean) of the fault-tolerant version of the
$\omega_{i}$-weighted balanced two-level additive Schwarz/Richardson iteration
(left) and the associated conjugate gradient method (right) for different
fault probabilities, ${\gamma=3,}$ $S=8,q=16,d=6$. Figure 26. Average rate and
asymptotic rate (mean) of the fault-tolerant version of the
$\omega_{i}$-weighted balanced two-level additive Schwarz/Richardson iteration
(left) and the associated conjugate gradient method (right) for different
fault probabilities, $\gamma=3,S=8,q=16,d=6$.

We see that the algorithm exhibits good weak scaling properties also for the
six-dimensional case. For rising values of $P$, the number of iterations stays
at around 23 for the balanced Richardson iteration and is nearly independent
of the fault rate (except of the case $p_{\text{fault}}=0.2$ which needs 28
iterations). Weak scaling can also be observed for the corresponding conjugate
gradient method. Now however the weak scaling constant is dependent on the
fault rate $p_{\text{fault}}$ and increases for rising numbers of faults,
albeit with still less iterations than in the Richardson case (except for the
case $p_{\text{fault}}=0.2$). The situation is the same for the average rate
and the asymptotic rate is basically the same.

Altogether we conclude that, for a moderate number of faults and a
sufficiently large choice of $\gamma$, our fault-tolerant algorithms work and
scale well with rising numbers of $P$ and associated rising number
$p_{\text{fault}}\cdot P$ of faults. Thus we obtain fault-tolerance also in
the weak scaling regime.

##  5\. Discussion and conclusion

In the present article we proposed and studied a simple additive two-level
overlapping domain decomposition method for $d$-dimensional elliptic PDEs,
which relies on a space-filling curve approach to create equally sized
subproblems and to determine an overlap based on the one-dimensional ordering
of the space-filling curve. Moreover we employed agglomeration and a purely
algebraic Galerkin discretization in the construction of the coarse problem to
avoid $d$-dimensional geometric information. This resulted in a parallel
subspace correction iteration and an associated parallel preconditioner for
the conjugate gradient method which can be employed for any value of $P$ and
in any dimension $d$. It exhibits the same asymptotic convergence rate as a
conventional geometric domain decomposition method, i.e.
$\kappa=O(1+\frac{H}{\delta})$ with $\delta=ch$, compare [TW04, Theorem 3.13]
and (4.30), but allows for more flexibility and simplicity with respect to
$N$, $P$ and $d$ due to the space-filling curve construction. Moreover it
turned out that its balanced version according to (2.7), which, compared to
the plain version, involves two additional matrix-vector-multiplications,
three additional vector-vector-additions and one additional solve of the
coarse scale problem, was clearly superior and is therefore the recommended
approach. To gain fault-tolerance we stored on each processor, besides the
data of the associated subproblem, a copy of the coarse problem and also the
data of a fixed number of (partial) neighboring subproblems with respect to
the one-dimensional ordering of the subproblems induced by the space-filling
curve. This redundancy then allows to restore necessary data if processors
fail during the computation and to therefore restore convergence in the case
of faults. We showed theoretically and practically that the convergence rate
of such a linear iteration method for a moderate number of faults stays
approximately the same in expectation and only its order constant deteriorates
slightly due to the faults. This was also observed in practice for the
associated preconditioned conjugate gradient method. Moreover weak scaling
could be achieved in any situation. Altogether, we obtained a fault-tolerant,
parallel and efficient domain decomposition method based on space-filling
curves, which is especially suited for higher-dimensional elliptic problems.

Note here that we employed an exact subdomain solver in our domain
decomposition method. It can be replaced by a faster but iterative and thus
somewhat inexact method, like for example algebraic multigrid. This needs to
be explored in more detail in the future.

Moreover our algorithmic approach possesses a range of parameters, which
influence each other and need to be chosen properly. The determination of an
optimal set of parameters is a difficult task. Nevertheless some general
guidelines could be derived: One key parameter is the number of degrees of
freedom for the coarse grid. Here it became clear that the coarse grid size
should be chosen relative to the fine grid size. The distance between the two
levels controls the balance between the required number of iterations on the
one hand and the cost to solve the coarse system in each iteration on the
other hand. Fortunately, as the dimension increases, the size of the coarse
grid can be decreased, which reduces the cost for each iteration. Furthermore,
as seen from Lemma 2.1, it is sensible to choose another key parameter of our
scheme, namely the overlap $\gamma$, as an integer multiple of $\frac{1}{2}$,
i.e. $\gamma=\frac{1}{2}n,n\in\mathbb{N}_{+}$. This way, the different
possible scalings via $D_{i}$ and $\omega_{i}$ coincide and boil down to a
constant scaling with $1/(2\gamma+1)$ and symmetry of the associated operator
is guaranteed, at least for the Laplacian and diffusion operators with
constant coefficients. Furthermore the choice of $\gamma$ as an integer
multiple of $\frac{1}{2}$ is also natural for a uniform redundancy of stored
data, which is advantageous for the recovery and reconstruction in the case of
faults. Moreover we learned from our convergence studies and from our fault
tolerance experiments that $\gamma$ can be chosen to be quite small for any
real world setting. For example, Figures 21 and 26 showed that $\gamma=0.5$ or
$\gamma=1$ still produce excellent convergence for both considered types of
solvers for fault rates of up to 2% and 5% per iteration/cycle, respectively.
These fault rates are indeed way beyond those of any existing high performance
compute system, where merely one or very few faults currently occur on average
each day. They are also beyond the expected fault rates for future exascale
compute systems. For practical purposes this means that we will see no
deterioration of the convergence rates at all, as long as the data recovery
process is executed properly. This is guaranteed due to the overlap and the
redundant parallel storage of current data and local parts of the iterate
which allows the algorithm to recover after a fault occurs. In this respect,
iterative methods are fault-forgiving and the iteration can continue
dynamically. Moreover our aim was to derive a fault-tolerant parallel domain
decomposition solver, which can be later employed for the subproblems in the
combination method. There we encounter short run times, since the numbers of
degrees of freedom of all the arising subproblems are similar to the one-
dimensional case, i.e. of size $\approx 2^{L}$ only, compare (2.9). But this
is good news: The fault-repair mechanism is rarely needed for real-life fault
probabilities within the short run times of our solver for the small
subproblems arising in the combination method.

We next intend to employ our domain decomposition method as the inner,
parallel and fault-tolerant solver for the subproblems arising in the sparse
grid combination method. Let us recall the sparse grid combination formula
from (2.9), i.e.

(5.33) $u({x})\approx
u^{(c)}_{L}({x}):=\sum_{i=0}^{d-1}(-1)^{i}\left(\begin{array}[]{c}{d-1}\\\
{i}\end{array}\right)\sum_{|{l}|_{1}=L+(d-1)-i}u_{l}({x}).$

Here the different subproblems can be computed in parallel independently of
each other. Moreover, for layer $i$, we have

$\left(\begin{array}[]{c}{L+d-2-i}\\\ {d-1}\end{array}\right)$

different subproblems, where each subproblem has approximately the same number
$N(d,i)=\prod_{j=1}^{d}(2^{l_{j}}+1)=O(2^{L+d-1-i})$ of degrees of freedom. We
now employ an additional step of parallelization by means of the domain
decomposition treatment of each of these subproblems. To this end, we use

(5.34) $P:=\hat{P}\cdot 2^{d-1-i}$

subdomains and thus processors for each subproblem on layer $i$. This choice
of a $d$\- and $i$-dependent $P$ via a universal $\hat{P}$ in (5.34) results
in a subdomain size of roughly
$N(d,i)/P=2^{L+d-1-i}/P=2^{L+d-1-i}/(\hat{P}\cdot 2^{d-1-i})=2^{L}/\hat{P}$,
which is independent of $d$ and $i$. Then, in our elliptic situation and
except for the coarse scale problems, only small subdomain problems appear.
But, depending on $d,L$ and $\hat{P}$, there can be millions of these
subdomains for the combination method. To be precise, the amount of fine level
subdomains for the overall set of subproblems in the combination method (2.9)
is

$\frac{\hat{P}}{(d-1)!}\sum_{k=0}^{d-1}\left(2^{d-1-k}\prod_{i=1}^{d-1}(L+d-1-k-i)\right),$

where each occurring subdomain problem has approximately equal size
$2^{L}/\hat{P}$.

As an example, consider the goal of an overall discretization error of
$10^{-12}$. Then ${h\approx 10^{-6}}$ and $L=20$. Moreover we choose
$\hat{P}=2^{10}$. For this case, Table 1 gives the number of subdomain
problems arising in the combination method if our domain decomposition
approach is employed with $P$ given by (5.34) for each subproblem of layer
$i$.

$d=$ | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---
| $1\cdot\hat{P}$ | $59\cdot\hat{P}$ | $1.391\cdot\hat{P}$ | $20.889\cdot\hat{P}$ | $237.706\cdot\hat{P}$ | $1.754.744\cdot\hat{P}$
Table 1. Overall number of subdomain problems, each one of size
$2^{L}/\hat{P}$, in the combination method with domain decomposition of each
subproblem.

We see that we obtain a large number of subdomain problems to be solved in a
doubly parallel way (one level of parallelism stems from the combination
formula itself, the other stems from the domain decomposition of each
subproblem of the combination method into subdomain problems). This will allow
the use of extremely large parallel compute systems, i.e. the larger $d$ is
the larger the parallel system is that can be employed in a meaningful way.
Furthermore the use of the fault-tolerant domain decomposition method as the
inner solver for the subproblems in the combination method results in a fault-
tolerant and parallel solver for the combination method in a natural way.
There, the fault-repair mechanism is provided on the fine domain decomposition
level and not just on the coarse subproblem level of the combination method,
as it was previously done in [HHLS14, PBG14, ASHH16, OHHBP17, LOP20].

For our simple elliptic Poisson problem we encounter very short computing
times in the 10 second range for each of the subproblems arising in the
combination method, and therefore a fault occurs extremely rarely during its
run time. The true value of our fault-tolerant approach will rather become
apparent in time-dependent parabolic problems with long time horizons and long
computation times, where our elliptic DDM-solver is employed in each time step
of an implicit time-discretization method within the combination method. This
however is future work.

### Acknowledgment

Michael Griebel was supported by a research grant of the Bayerische Akademie
der Wissenschaften for the project Stochastic subspace correction as a fault-
tolerant sparse grid combination method on massive parallel compute systems
for high-dimensional parametric diffusion problems. The support of the
Leibniz-Rechenzentrum in Garching, the support of Prof. Dr. Dieter
Kranzlmüller, LRZ Garching, LMU München, Institut für Informatik, and the
support of Prof. Dr. Hans-Joachim Bungartz, TU München, Institut für
Informatik, is greatly acknowledged. Michael Griebel thanks the Institut für
Informatik of the LMU München and the Leibniz-Rechenzentrum of the Bayerische
Akademie der Wissenschaften for their hospitality.

## References

  * [A20] E. Agullo et al.  Resiliency in numerical algorithm design for extreme scale simulations.  Report Dagstuhl Seminar 20101, March 1–6, 2020.  arXiv:2010.13342v1,  submitted to the International Journal of High Performance Computing Applications.
  * [AAD11] H. Alcin, O. Allain, and A. Dervieux.  Volume-agglomeration coarse grid in Schwarz algorithm. In: J. Fort, J. Fürst, J. Halama, R. Herbin and F. Hubert (eds). Finite Volumes for Complex Applications VI, Problems and Perspectives. Springer Proceedings in Mathematics, Volume 4, Springer, Berlin, Heidelberg, 3–11, 2011.
  * [ASHH16] M. Ali, P. Strazdins, B. Harding, and M. Hegland.  Complex scientific applications made fault-tolerant with the sparse grid combination technique.  The International Journal of High Performance Computing Applications 30:335–359, 2016.
  * [P20] G. Altai. //pypi.org/project/hilbertcurve/, retrieved 06.10.2020.
  * [B13] M. Bader. Space-Filling Curves: An Introduction with Applications in Scientific Computing, Texts in Computations Science and Engineering, Volume 9, Springer-Verlag, 2013.
  * [BH03] R. Bank and M. Holst. A new paradigm for parallel adaptive meshing algorithms. SIAM Review 45(2):291–323, 2003.
  * [BDK15] H. Bouwmeester, A. Dougherty, and A. Knyazev. Nonsymmetric preconditioning for conjugate gradient and steepest descent methods. Procedia Computer Science 51:276–285, 2015.
  * [B86] J. Bramble, J. Pasciak and A. Schatz.  The construction of preconditioners for elliptic problems by substructuring, I.  Math. Comp. 47(175):103–134, 1986.
  * [BPS89] J. Bramble, J. Pasciak, and A. Schatz.  The construction of preconditioners for elliptic problems by substructuring, IV.  Math. Comp. 53(187):1–24, 1989.
  * [B00] S. Brenner.  Lower bounds for two-level additive Schwarz preconditioners with small overlap.  SIAM J. Sci. Comput. 21(5):1657–1669, 2000.
  * [BG04] H.-J. Bungartz and M. Griebel.  Sparse grids.  Acta Numerica 13:147–269, 2004
  * [BGRZ94] H.-J. Bungartz, M. Griebel, D. Röschke, and C. Zenger. Two proofs of convergence for the combination technique for the efficient solution of sparse grid problems. In: D. Keyes and J. Xu, editors, Domain Decomposition Methods in Scientific and Engineering Computing, DDM7, Contemp. Math. 180, 15–20. American Mathematical Society, Providence, 1994
  * [B71] A. Butz. Alternative algorithm for Hilbert’s space-filling curve, IEEE Transactions on Computers 20(4):424-426, 1971.
  * [C78] G. Cantor. Ein Beitrag zur Mannigfaltigkeitslehre, J. Reine Angew. Math. (Crelle’s Journal) 84:242-258, 1878.
  * [C17] P. Chernoch. Mapping N-dimensional value to a point on Hilbert curve, //stackoverflow.com/questions/499166/mapping-n-dimensional-value-to-a-point-on-hilbert-curve/10384110#10384110, retrieved 01.04.2017.
  * [C20] P. Chernoch. //github.com/paulchernoch/HilbertTransformation, retrieved 06.10.2020.
  * [CS99] X. Cai and M. Sarkis.  A restricted additive Schwarz preconditioner for general sparse linear systems.  SIAM J. Sci. Comput. 21:239–247, 1999.
  * [DW87] M. Dryja and O. Widlund.  An additive variant of the Schwarz alternating method for the case of many subregions.  Ultracomputer Note 131, Department of Computer Science, Courant Institute, New York, 1987.
  * [DW94] M. Dryja and O. Widlund.  Domain decomposition algorithms with small overlap.  SIAM J. Sci. Comput. 15(3):604–620, 1994.
  * [DJN15] V. Dolean, P. Jolivet, and F. Nataf.  An Introduction to Domain Decomposition Methods: Algorithms, Theory, and Parallel Implementation, SIAM, 2015.
  * [G12] J. Garcke. Sparse Grids in a Nutshell. In: J. Garcke and M. Griebel, editors, Sparse Grids and Applications, Volume 88 of Lecture Notes in Computational Science and Engineering, Springer, 57–80, 2012.
  * [Gri92] M. Griebel.  The combination technique for the sparse grid solution of PDEs on multiprocessor machines.  Parallel Processing Letters 2(1):61–70, 1992.
  * [GSZ92] M. Griebel, M. Schneider, and C. Zenger.  A combination technique for the solution of sparse grid problems.  In: P. de Groen and R. Beauwens, editors, Iterative Methods in Linear Algebra, IMACS, Elsevier, North Holland, 263–281. 1992.
  * [GH14] M. Griebel and H. Harbrecht.  On the convergence of the combination technique.  In: Sparse grids and Applications. Volume 97 of Lecture Notes in Computational Science and Engineering, Springer, 55–74. 2014.
  * [GKZ07] M. Griebel, S. Knapek, and G. Zumbusch. Numerical Simulation in Molecular Dynamics. Springer, Berlin, Heidelberg, 2007.
  * [GO95] M. Griebel and P. Oswald.  On the abstract theory of additive and multiplicative Schwarz algorithms.  Numer. Math. 70:163–180, 1995.
  * [GO12] M. Griebel and P. Oswald.  Greedy and randomized versions of the multiplicative Schwarz method.  Linear Algebra Appl. 437:1596–1610, 2012.
  * [GO16] M. Griebel and P. Oswald.  Schwarz iterative methods: Infinite space splittings.  Constructive Approximation 33(1):121–139, 2016.
  * [GO18] M. Griebel and P. Oswald.  Stochastic subspace correction in Hilbert space.  Constructive Approximation 48(3):501–521, 2018.
  * [GO20] M. Griebel and P. Oswald.  Stochastic subspace correction methods and fault tolerance.  Math. Comp. 89(321):279–312, 2020.
  * [GZ00] M. Griebel and G. Zumbusch.  Parallel adaptive subspace correction schemes with applications to elasticity.  Computer Methods in Applied Mechanics and Engineering 184:303–332, 2000.
  * [GZ01] M. Griebel and G. Zumbusch.  Hash based adaptive parallel multilevel methods with space-filling curves. In: H. Rollnik and D. Wolf, editors, NIC Symposium 2001, Volume 9 of NIC Series, Forschungszentrum Jülich, Germany, 479–492. 2002.
  * [HHLS14] B. Harding, M. Hegland, J. Larson, and J. Southern.  Fault tolerant computation with the sparse grid combination technique.  SIAM J. Sci. Comput. 37(03):C331–C353, 2014.
  * [HGRW16] M. Huber, B. Gmeiner, U. Rüde, and B. Wohlmuth.  Resilience for massively parallel multigrid solvers.  SIAM J. Sci. Comput. 38(5):S217–S239, 2016.
  * [H91] D. Hilbert. Über die stetige Abbildung einer Linie auf ein Flächenstück, Mathematische Annalen 38:459–460, 1891.
  * [JYS19] D. Jauk, D. Yang, and M. Schulz. Predicting faults in high performance computing systems: An in-depth survey of the state-of-the-practice. in SC ’19: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Article No. 30, 1–13, 2019.
  * [KRS13] S. Kavila, P. Raju, S. Satapathy, A. Machiraju, G. Kinnera, and K. Rasly.  A survey on fault management techniques in distributed computing.  In: S. Satapathy et al., editor, Proc. of Int. Conf. on Front. of Intell. Comput., AISC 199, 593–602, 2013.
  * [LOP20] R. Lago, M. Obersteiner, T. Pollinger, J. Rentrop, H.-J. Bungartz, T. Dannert, M. Griebel, F. Jenko, and D. Pflüger.  EXAHD – A massively parallel fault-tolerant sparse grid approach for high-dimensional turbulent plasma simulations.  In: H.-J. Bungartz, S. Reiz, B. Uekermann, P. Neumann, and W. Nagel, editors, Software for Exascale Computing - SPPEXA 2016-2019, Volume 136 of Lecture Notes in Computational Science and Engineering, Springer, 301-329, 2020.
  * [L00] J. Lawder. Calculation of mappings between one and n-dimensional values using the Hilbert space-filling curve, research report BBKCS-00-01, School of Computer Science and Information Systems, Birkbeck College, University of London, 2000.
  * [L04] H. Lebesgue. Leçons sur l’Intégration et la Recherche des Fonctions Primitives, Gauthier-Villars, 1904.
  * [M93] J. Mandel.  Balancing domain decomposition.  Comm. Numer. Methods Engrg. 9:233-241, 1993.
  * [M88] L. Mansfield.  On the use of deflation to improve the convergence of conjugate gradient iteration.  Comm. Applied Numer. Meth. 4:151-156, 1988.
  * [M90] L. Mansfield.  On the conjugate gradient solution of the Schur complement system obtained from domain decomposition.  SIAM J. Numer. Anal. 27(6):1612–1620, 1990.
  * [M00] D. Moore. Fast Hilbert curve generation, sorting, and range queries. http://www.tiac.net/ sw/2008/10/Hilbert/moore/, retrieved 01.04.2017.
  * [N79] E. Netto. Beitrag zur Mannigfaltigkeitslehre, J. Reine Angew. Math. (Crelle’s Journal) 86:263-268, (1879).
  * [N87] R. Nicolaides.  Deflation of conjugate gradients with applications to boundary value problems.  SIAM J. Numer. Anal. 24:355-365, 1987.
  * [OHHBP17] M. Obersteiner, A. Parra Hinojosa, M. Heene, H. Bungartz, and D. Pflüger. A highly scalable, algorithm-based fault-tolerant solver for gyrokinetic plasma simulations. In: ScalA ’17: Proceedings of the 8th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems, November 2017, Article No 2, 1–8, 2017.
  * [PAS14] S. Pauli, P. Arbenz, and C. Schwab, Intrinsic fault tolerance of multi-level Monte Carlo methods, In: Parallel Computing: Accelerating Computational Science and Engineering (CSE), M. Bader et al., editors, IOS Press, 2014, 471–480.
  * [P90] G. Peano. Sur une courbe qui remplit toute une aire plane. Math. Ann. 36:157-160, (1890).
  * [PBG14] D. Pflüger, H.-J. Bungartz, M. Griebel, F. Jenko, T. Dannert, M. Heene, C. Kowitz, A. Hinojosa, and P. Zaspel.  EXAHD: An exa-scalable two-level sparse grid approach for higher-dimensional problems in plasma physics and beyond.  In: L. Lopes et al, editors, Euro-Par 2014: Parallel Processing Workshops, Volume 8806 of Lecture Notes in Computer Science, Springer International Publishing, 565–576. 2014.
  * [QV99] A. Quarteroni and A. Valli.  Domain Decomposition Methods for Partial Differential Equations, Oxford Science Publications, 1999.
  * [S94] H. Sagan. Space-Filling Curves, Universitext, Springer-Verlag, New York, 1994.
  * [S70] H. Schwarz.  Über einen Grenzübergang durch alternierendes Verfahren.  Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich 15:272–286, 1870.
  * [SG10] B. Schroeder and G. Gibson. A large-scale study of failures in high-performance computing Systems. IEEE Transactions on Dependable and Secure Computing, 7(4):337-350, 2010.
  * [Sh20] A. Shavit. //github.com/adishavit/hilbert/blob/master/hilbert.c#L529, retrieved 06.10.2020.
  * [S04] J. Skilling. Programming the Hilbert curve, AIP Conference Proceedings 707:381-387, 2004.
  * [S90] B. Smith.  Domain Decomposition Algorithms for the Partial Differential Equations of Linear Elasticity.  Ph.D. Thesis, Courant Institute, New York, 1990.
  * [SBWG96] B. Smith, P. Bjorstad, and W. Gropp.  Domain Decomposition, Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, 1996.
  * [SW14] M. Snir, R. Wisniewski, et al.  Addressing failures in exascale computing.  Int. J. High Perf. Comput. Appl. 28(2):129–173, 2014.
  * [Sp20] A. Spencer. //www.math.utah.edu/cgi-bin/man2html.cgi?/usr/local/man/man3/hilbert.3, retrieved 06.10.2020.
  * [Sta19] L. Stals.  Algorithm-based fault recovery of adaptively refined parallel multilevel grids.  The International Journal of High Performance Computing Applications 33:189 – 211, 2019.
  * [T92] S. Thomas. hilbert.c, in fossies.org, URT/urt-3.1a/lib/hilbert.c, The Utah Raster Toolkit, fossies.org/linux/misc/old/URT3.1a.tar.gz/URT/urt-3.1a/lib/hilbert.c, retrieved 01.04.2017.
  * [Tre05] M. Treaster.  A survey of fault-tolerance and fault-recovery techniques in parallel systems.  ACM Computing Research Repository CoRR 501002:1–11, 2005.
  * [TW04] A. Toselli and O. Widlund. Domain Decomposition Methods - Algorithms and Theory. Springer Series in Computational Mathematics, Volume 34, Springer, Berlin, Heidelberg, 2004.
  * [VN06] C. Vuik and R. Nabben.  A comparison of deflation and the balancing preconditioner.  SIAM J. Sci. Comput. 27(5):1742–1759, 2006.
  * [W09] O. Widlund.  The development of coarse spaces for domain decomposition algorithms.  In: M. Bercovier, M. Gander, R. Kornhuber and O. Widlund, editors.  Domain Decomposition Methods in Science and Engineering XVIII. Volume 70 of Lecture Notes in Computational Science and Engineering, Springer, Berlin, Heidelberg, 241–248, 2009.
  * [YWWYZ12] Y. Yuan, Y. Wu, Q. Wang, G. Yang, W. Zheng,  Job failures in high performance computing systems: A large-scale empirical study.  Computers and Mathematics with Applications 63(2):365-377, 2012.
  * [Z91] C. Zenger.  Sparse grids.  In: Parallel algorithms for partial differential equations, Proceedings of the 6th GAMM-Seminar, Kiel/Germany, 1990,  Volume 31 of Notes Numer. Fluid Mech., Vieweg, Braunschweig, 241–251, 1991.
  * [Z03] G. Zumbusch. Parallel Multilevel Methods. Adaptive Mesh Refinement and Loadbalancing, Teubner, 2003.


* [CTW13] Arkadev Chattopadhyay, Jacobo Torán, and Fabian Wagner.  Graph isomorphism is not $\rm AC^{0}$-reducible to group isomorphism.  ACM Trans. Comput. Theory, 5(4):Art. 13, 13, 2013.  Preliminary version appeared in FSTTCS ’10; ECCC Tech. Report TR10-117.  doi:10.1145/2540088.
  * [Ded64] Paul Dedecker.  Les foncteurs $Ext_{\Pi}$, H${}_{\Pi}{}^{2}$ et $H_{\Pi}{}^{2}$ non abéliens.  C. R. Acad. Sci. Paris, 258:4891–4894, 1964.
  * [DLN+09] Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner.  Planar graph isomorphism is in log-space.  In 2009 24th Annual IEEE Conference on Computational Complexity, pages 203–214, 2009.  doi:10.1109/CCC.2009.16.
  * [DNTW09] Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner.  Graph Isomorphism for $K_{3,3}$-free and $K_{5}$-free graphs is in Log-space.  In Ravi Kannan and K. Narayan Kumar, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, volume 4 of Leibniz International Proceedings in Informatics (LIPIcs), pages 145–156, Dagstuhl, Germany, 2009. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  doi:10.4230/LIPIcs.FSTTCS.2009.2314.
  * [DS19] Bireswar Das and Shivdutt Sharma.  Nearly linear time isomorphism algorithms for some nonabelian group classes.  In René van Bevern and Gregory Kucherov, editors, Computer Science – Theory and Applications, pages 80–92, Cham, 2019. Springer International Publishing.  doi:10.1007/978-3-030-19955-5\\_8.
  * [DW22] Heiko Dietrich and James B. Wilson.  Group isomorphism is nearly-linear time for most orders.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 457–467, 2022.  doi:10.1109/FOCS52979.2021.00053.
  * [EFT94] Heinz-Dieter Ebbinghaus, J. Flum, and W. Thomas.  Mathematical Logic.  Springer, 2 edition, 1994.  doi:10.1007/978-1-4757-2355-7.
  * [Ehr61] A. Ehrenfeucht.  An application of games to the completeness problem for formalized theories.  Fund. Math., 49:129–141, 1960/61.  doi:10.4064/fm-49-2-129-141.
  * [ELGO02] Bettina Eick, C. R. Leedham-Green, and E. A. O’Brien.  Constructing automorphism groups of $p$-groups.  Comm. Algebra, 30(5):2271–2295, 2002.  doi:10.1081/AGB-120003468.
  * [ES17] Michael Elberfeld and Pascal Schweitzer.  Canonizing graphs of bounded tree width in logspace.  ACM Trans. Comput. Theory, 9(3), oct 2017.  doi:10.1145/3132720.
  * [Fag76] Ronald Fagin.  Probabilities on finite models.  The Journal of Symbolic Logic, 41(1):50–58, 1976.  doi:10.2307/2272945.
  * [Fra54] Roland Fraïssé.  Sur quelques classifications des systèmes de relations.  Publ. Sci. Univ. Alger. Sér. A, 1:35–182 (1955), 1954.
  * [GK19] Martin Grohe and Sandra Kiefer.  A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 117:1–117:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  doi:10.4230/LIPIcs.ICALP.2019.117.
  * [GK21] Martin Grohe and Sandra Kiefer.  Logarithmic Weisfeiler-Leman Identifies All Planar Graphs.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 134:1–134:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.ICALP.2021.134.
  * [GL22a] Joshua A. Grochow and Michael Levet.  On the descriptive complexity of groups without Abelian normal subgroups, 2022.  doi:10.48550/ARXIV.2209.13725.
  * [GL22b] Joshua A. Grochow and Michael Levet.  On the parallel complexity of group isomorphism via Weisfeiler–Leman.  CoRR, abs/2112.11487, 2022.  arXiv:2112.11487.
  * [GN19] Martin Grohe and Daniel Neuen.  Canonisation and definability for graphs of bounded rank width, 2019.  arXiv:1901.10330.
  * [Gom10] Walid Gomaa.  Descriptive complexity of finite abelian groups.  IJAC, 20:1087–1116, 12 2010.  doi:10.1142/S0218196710006047.
  * [GQ15] Joshua A. Grochow and Youming Qiao.  Polynomial-time isomorphism test of groups that are tame extensions - (extended abstract).  In Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, pages 578–589, 2015.  doi:10.1007/978-3-662-48971-0_49.
  * [GQ17] Joshua A. Grochow and Youming Qiao.  Algorithms for group isomorphism via group extensions and cohomology.  SIAM J. Comput., 46(4):1153–1216, 2017.  Preliminary version in IEEE Conference on Computational Complexity (CCC) 2014 (DOI:10.1109/CCC.2014.19). Also available as arXiv:1309.1776 [cs.DS] and ECCC Technical Report TR13-123.  doi:10.1137/15M1009767.
  * [Gro17] Martin Grohe.  Descriptive complexity, canonisation, and definable graph structure theory, volume 47 of Lecture Notes in Logic.  Association for Symbolic Logic, Ithaca, NY; Cambridge University Press, Cambridge, 2017.  doi:10.1017/9781139028868.
  * [GV06] Martin Grohe and Oleg Verbitsky.  Testing graph isomorphism in parallel by playing a game.  In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, volume 4051 of Lecture Notes in Computer Science, pages 3–14. Springer, 2006.  doi:10.1007/11786986_2.
  * [Hel89] Lauri Hella.  Definability hierarchies of generalized quantifiers.  Annals of Pure and Applied Logic, 43(3):235 – 271, 1989.  doi:10.1016/0168-0072(89)90070-5.
  * [Hel96] Lauri Hella.  Logical hierarchies in PTIME.  Information and Computation, 129(1):1–19, 1996.  doi:10.1006/inco.1996.0070.
  * [HEO05] D. Holt, B. Eick, and E. O’Brien.  Handbook of Computational Group Theory.  Chapman and Hall/CRC, 2005.
  * [HL74] Hermann Heineken and Hans Liebeck.  The occurrence of finite groups in the automorphism group of nilpotent groups of class $2$.  Arch. Math. (Basel), 25:8–16, 1974.  doi:10.1007/BF01238631.
  * [HQ21] Xiaoyu He and Youming Qiao.  On the Baer–Lovász–Tutte construction of groups from graphs: Isomorphism types and homomorphism notions.  Eur. J. Combin., 98:103404, 2021.  doi:10.1016/j.ejc.2021.103404.
  * [IL90] Neil Immerman and Eric Lander.  Describing graphs: A first-order approach to graph canonization.  In Alan L. Selman, editor, Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, pages 59–81. Springer New York, New York, NY, 1990.  doi:10.1007/978-1-4612-4478-3_5.
  * [Imm82] Neil Immerman.  Upper and lower bounds for first order expressibility.  Journal of Computer and System Sciences, 25(1):76–98, 1982.  doi:https://doi.org/10.1016/0022-0000(82)90011-3.
  * [Ina97] H. Inassaridze.  Non-abelian cohomology of groups.  Georgian Math. J., 4(4):313–332, 1997.  URL: https://doi-org.colorado.idm.oclc.org/10.1023/A:1022938428031, doi:10.1023/A:1022938428031.
  * [IPZ01] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  Journal of Computer and System Sciences, 63(4):512–530, 2001.  doi:10.1006/jcss.2001.1774.
  * [IQ19] Gábor Ivanyos and Youming Qiao.  Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing.  SIAM J. Comput., 48(3):926–963, 2019.  doi:10.1137/18M1165682.
  * [Isa08] I. Isaacs.  Finite Group Theory.  American Mathematical Society, 2008.
  * [JKMT03] Birgit Jenner, Johannes Köbler, Pierre McKenzie, and Jacobo Torán.  Completeness results for graph isomorphism.  J. Comput. Syst. Sci., 66(3):549–566, may 2003.  doi:10.1016/S0022-0000(03)00042-4.
  * [JKS02] Jeffrey C. Jackson, Adam R. Klivans, and Rocco A. Servedio.  Learnability beyond $\textsf{AC}^{0}$.  In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC ’02, page 776–784, New York, NY, USA, 2002. Association for Computing Machinery.  doi:10.1145/509907.510018.
  * [Kav07] T. Kavitha.  Linear time algorithms for abelian group isomorphism and related problems.  Journal of Computer and System Sciences, 73(6):986 – 996, 2007\.  doi:10.1016/j.jcss.2007.03.013.
  * [KN09] Neeraj Kayal and Timur Nezhmetdinov.  Factoring groups efficiently.  In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris Nikoletseas, and Wolfgang Thomas, editors, Automata, Languages and Programming, pages 585–596, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.  doi:10.1007/978-3-642-02927-1_49.
  * [KPS19] Sandra Kiefer, Ilia Ponomarenko, and Pascal Schweitzer.  The Weisfeiler–Leman dimension of planar graphs is at most 3.  J. ACM, 66(6), November 2019.  doi:10.1145/3333003.
  * [KST92] Johannes Köbler, Uwe Schöning, and Jacobo Torán.  Graph isomorphism is low for PP.  Comput. Complex., 2:301–330, 1992.  doi:10.1007/BF01200427.
  * [KV08] Johannes Köbler and Oleg Verbitsky.  From invariants to canonization in parallel.  In Edward A. Hirsch, Alexander A. Razborov, Alexei Semenov, and Anatol Slissenko, editors, Computer Science – Theory and Applications, pages 216–227, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.  doi:10.1007/978-3-540-79709-8_23.
  * [Lad75] Richard E. Ladner.  On the structure of polynomial time reducibility.  J. ACM, 22(1):155–171, January 1975.  doi:10.1145/321864.321877.
  * [LG09] François Le Gall.  Efficient isomorphism testing for a class of group extensions.  In Proc. 26th STACS, pages 625–636, 2009.  doi:10.4230/LIPIcs.STACS.2009.1830.
  * [LGR16] François Le Gall and David J. Rosenbaum.  On the group and color isomorphism problems.  arXiv:1609.08253 [cs.CC], 2016.
  * [Lib04] Leonid Libkin.  Elements of Finite Model Theory.  Springer, 2004.  doi:10.1007/978-3-662-07003-1_1.
  * [Lin92] Steven Lindell.  A logspace algorithm for tree canonization (extended abstract).  In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’92, page 400–404, New York, NY, USA, 1992. Association for Computing Machinery.  doi:10.1145/129712.129750.
  * [LQ17] Yinan Li and Youming Qiao.  Linear algebraic analogues of the graph isomorphism problem and the erdős-rényi model.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 463–474, 2017.  doi:10.1109/FOCS.2017.49.
  * [LSZ77] R. J. Lipton, L. Snyder, and Y. Zalcstein.  The complexity of word and isomorphism problems for finite groups.  Yale University Dept. of Computer Science Research Report # 91, 1977\.  URL: https://apps.dtic.mil/dtic/tr/fulltext/u2/a053246.pdf.
  * [LW12] Mark L. Lewis and James B. Wilson.  Isomorphism in expanding families of indistinguishable groups.  Groups - Complexity - Cryptology, 4(1):73–110, 2012.  doi:10.1515/gcc-2012-0008.
  * [Mat79] Rudolf Mathon.  A note on the graph isomorphism counting problem.  Information Processing Letters, 8(3):131–136, 1979.  doi:https://doi.org/10.1016/0020-0190(79)90004-8.
  * [Mek81] Alan H. Mekler.  Stability of nilpotent groups of class 2 and prime exponent.  The Journal of Symbolic Logic, 46(4):781–788, 1981.  URL: http://www.jstor.org/stable/2273227.
  * [Mil78] Gary L. Miller.  On the $n^{\log n}$ isomorphism technique (a preliminary report).  In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC ’78, pages 51–58, New York, NY, USA, 1978. Association for Computing Machinery.  doi:10.1145/800133.804331.
  * [MIS90] David A. Mix Barrington, Neil Immerman, and Howard Straubing.  On uniformity within $\textsf{NC}^{1}$.  Journal of Computer and System Sciences, 41(3):274–306, 1990.  doi:https://doi.org/10.1016/0022-0000(90)90022-D.
  * [NS18] Daniel Neuen and Pascal Schweitzer.  An exponential lower bound for individualization-refinement algorithms for graph isomorphism.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 138–150. ACM, 2018.  doi:10.1145/3188745.3188900.
  * [NT17] André Nies and Katrin Tent.  Describing finite groups by short first-order sentences.  Israel J. Math., 221(1):85–115, 2017.  doi:10.1007/s11856-017-1563-2.
  * [QST11] Youming Qiao, Jayalal M. N. Sarma, and Bangsheng Tang.  On isomorphism testing of groups with normal Hall subgroups.  In Proc. 28th STACS, pages 567–578, 2011.  doi:10.4230/LIPIcs.STACS.2011.567.
  * [Rob82] D. Robinson.  A Course in the Theory of Groups.  Springer, 1982.
  * [Ros09] Benjamin Rossman.  Ehrenfeucht-Fraïssé Games on Random Structures.  In Hiroakira Ono, Makoto Kanazawa, and Ruy J. G. B. de Queiroz, editors, Logic, Language, Information and Computation, 16th International Workshop, WoLLIC 2009, Tokyo, Japan, June 21-24, 2009. Proceedings, volume 5514 of Lecture Notes in Computer Science, pages 350–364. Springer, 2009.  doi:10.1007/978-3-642-02261-6\\_28.
  * [Ros13] David J. Rosenbaum.  Bidirectional collision detection and faster deterministic isomorphism testing.  arXiv:1304.3935 [cs.DS], 2013.
  * [Sav80] C. Savage.  An $O(n^{2})$ algorithm for abelian group isomorphism.  Technical report, North Carolina State University, 01 1980.
  * [Sch88] Uwe Schöning.  Graph isomorphism is in the low hierarchy.  Journal of Computer and System Sciences, 37(3):312 – 323, 1988\.  doi:10.1016/0022-0000(88)90010-4.
  * [Shr19] Tyler Shrock.  On the complexity of isomorphism in finite group theory and symbolic dynamics, 2019.  URL: https://scholar.colorado.edu/concern/graduate_thesis_or_dissertations/db78td05x.
  * [Tan13] Bangsheng Tang.  Towards Understanding Satisfiability, Group Isomorphism and Their Connections.  PhD thesis, Tsinghua University, 2013.  URL: http://papakonstantinou.org/periklis/pdfs/bangsheng_thesis.pdf.
  * [Tau55] D. R. Taunt.  Remarks on the isomorphism problem in theories of construction of finite groups.  Mathematical Proceedings of the Cambridge Philosophical Society, 51(1):16–24, 1955.  doi:10.1017/S030500410002987X.
  * [Thé80] Denis Thérien.  Classification of regular languages by congruences.  PhD thesis, University of Waterloo, 1980.  URL: https://cs.uwaterloo.ca/research/tr/1980/CS-80-19.pdf.
  * [The81] Jacquez Theévenaz.  Representations of finite groups in characteristic $p^{r}$.  J. Algebra, 72:478–500, 1981.  doi:10.1016/0021-8693(81)90305-7.
  * [Tor04] Jacobo Torán.  On the hardness of graph isomorphism.  SIAM J. Comput., 33(5):1093–1108, 2004.  doi:10.1137/S009753970241096X.
  * [Ver07] Oleg Verbitsky.  Planar graphs: Logical complexity and parallel isomorphism tests.  In Wolfgang Thomas and Pascal Weil, editors, STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, volume 4393 of Lecture Notes in Computer Science, pages 682–693. Springer, 2007.  doi:10.1007/978-3-540-70918-3\\_58.
  * [VGM09] Valery Vasil’ev, Maria Grechkoseeva, and V. Mazurov.  Characterization of the finite simple groups by spectrum and order.  Algebra and Logic, 48:385–409, 12 2009.  doi:10.1007/s10469-009-9074-9.
  * [Vik96] Narayan Vikas.  An $O(n)$ algorithm for abelian $p$-group isomorphism and an $O(n\log n)$ algorithm for abelian group isomorphism.  Journal of Computer and System Sciences, 53(1):1–9, 1996.  doi:10.1006/jcss.1996.0045.
  * [Wag11] Fabian Wagner.  Graphs of bounded treewidth can be canonized in $\textsf{AC}^{1}$.  In Proceedings of the 6th International Conference on Computer Science: Theory and Applications, CSR’11, page 209–222, Berlin, Heidelberg, 2011. Springer-Verlag.
  * [Wil12] James B. Wilson.  Existence, algorithms, and asymptotics of direct product decompositions, I.  Groups - Complexity - Cryptology, 4(1), Jan 2012.  doi:10.1515/gcc-2012-0007.
  * [Wil19] James B. Wilson.  The threshold for subgroup profiles to agree is logarithmic.  Theory of Computing, 15(19):1–25, 2019.  doi:10.4086/toc.2019.v015a019.
  * [Wol94] Marty J. Wolf.  Nondeterministic circuits, space complexity and quasigroups.  Theoretical Computer Science, 125(2):295–313, 1994.  doi:10.1016/0304-3975(92)00014-I.
  * [ZKT85] V. N. Zemlyachenko, N. M. Korneenko, and R. I. Tyshkevich.  Graph isomorphism problem.  J. Soviet Math., 29(4):1426–1481, May 1985.  doi:10.1007/BF02104746.