---
author:
- Kathryn Lund
bibliography:
- 'low\_sync\_block\_arnoldi.bib'
title: 'Adaptively restarted block Krylov subspace methods with low-synchronization skeletons'
---

Introduction and motivation {#sec:intro}
===========================

Oak Ridge National Laboratory reported in May 2022 that its Frontier supercomputer is the first machine to have achieved true exascale performance[^1]. That is, for the first time ever, a supercomputer performed more than 1 exaflop (i.e., $10^{18}$ double-precision floating-point operations) in a single second. This astounding development is clear motivation for our work. Exascale computing is no longer a next-generation dream; it is reality, and the need for highly parallelized algorithms that take full advantage of exaflop computational potential while reducing global communication between nodes is urgent.

To this end we build on the low-synchronization ("low-sync") Gram-Schmidt methods of Barlow @Bar19, Swirydowicz et al. @SwiLAetal20, Yamazaki et al. @YamTHetal20, Thomas et al. @ThoCRetal22, and Bielich et al. @BieLTetal22, as well as our own earlier work with block versions of these methods @CarLR21 [@CarLRetal22]. Gram-Schmidt methods are an essential backbone in orthogonalization routines like QR factorization and in iterative methods like Krylov subspace methods for linear systems, matrix functions, and matrix equations @Saa03a [@Gue13; @Sim16]. Block Krylov subspace methods in particular make better use of L3 cache via matrix-matrix operations and feature often in communication-avoiding Krylov subspaces, such as $s$-step @Car15 [@Hoe10], enlarged methods @GriMN16, and randomized methods @BalGr21.

As in most realms of life, there is no such thing as a free lunch here. While low-sync variations have the potential to speed up highly parallelized implementations of Gram-Schmidt @YamTHetal20, they introduce new floating-point errors and thus potential instability, due to the reformulation of inner products and normalizations. Instability surfaces in the loss of orthogonality between basis vectors and can lead to breakdowns or wildly inaccurate approximations in downstream applications @Hig02 [@HucNe19]. Stability bounds for some low-sync variants have been established, but it often takes much longer to carry out a rigorous stability analysis than to derive and deploy new methods @Bar19 [@CarLR21; @CarLRetal22; @ThoCRetal22]. It can also happen that a backward error bound is established and later challenged by an obscure edge case @GirLRetal05 [@SmoBL06]. With this tension in mind, we have not only extended low-sync variants of block Gram-Schmidt to block Arnoldi but also developed a benchmarking tool for the community to explore the efficiency, stability, and accuracy of these new algorithms, in a similar vein as the `BlockStab`[^2] comparison tool developed in tandem with a recent block Gram-Schmidt survey @CarLRetal22. We refer to this new tool as <span>`LowSyncBlockArnoldi`</span>[^3] and encourage the reader to explore the tool in parallel with the text.

Established in this earlier work is the fact that block variants of low-sync Gram-Schmidt are less stable than their column-wise counterparts. However, when these skeletons are transferred to block Arnoldi and used to solve linear systems, we gain the option to restart the process. Restarting can at mitigating stability issues in communication-avoiding algorithms @Car18 [@Car20]. As long as each node redundantly computes residual or error estimates and checks the stability via local quantities, restarting does not introduce additional synchronization points. Furthermore, adaptive restarting allows for robustness, as we can use basic look-ahead heuristics to foresee a breakdown and salvage progress without giving up completely at the first sign of trouble.

Given the modularity of our framework, we are also able to treat generalized block inner products, as described in @FroLS17 [@FroLS20]. We focus in particular on the classical and global inner products.

The paper is organized as follows. In Section \[sec:background\] we summarize terms, definitions, and concepts from high-performance (HPC) computing, generalized block inner products, block Gram-Schmidt algorithms, and block Krylov subspace methods with static restarting. We present new low-synchronization block Arnoldi skeletons in Section \[sec:low\_sync\], and derive an adaptive restarting heuristic in Section \[sec:stab\_repro\]. Section \[sec:examples\] features a more in-depth discussion of the <span>`LowSyncBlockArnoldi`</span>benchmarking tool as well as examples demonstrating how to compare different block Arnoldi variants. We summarize our findings in Section \[sec:conclusion\].

Background {#sec:background}
==========

This work is the generalized inner product framework of Frommer, Lund, and Szyld @FroLS17 [@FroLS20] and the skeleton-muscle framework for block Gram-Schmidt (BGS) by Carson, Lund, Rozložník, and Thomas @CarLR21 [@CarLRetal22]. Throughout the text, we focus on solving a linear system with multiple right-hand sides $$\label{eq:AX=B}
    A {\bm{X}}= {\bm{B}},$$ where $A \in {{\mathbb{C}}^{n \times n}}$ is large and sparse (i.e., with ${\mathcal{O}\left(n\right)}$ nonzero entries) and ${\bm{B}}\in {{\mathbb{C}}^{n \times s}}$ is tall-skinny (i.e., $s \ll n$) matrix.

We employ standard numerical linear algebra notation throughout. In particular, $A^*$ denotes the Hermitian transpose of $A$, ${\left\lVert\cdot\right\rVert}$ refers to the Euclidean 2-norm, unless otherwise specified, and ${\widehat{{\bm{e}}}}_k$ denotes the $k$th standard unit vector with the $k$th entry equal to $1$ and all others $0$.

In the following subsections, we define key concepts in HPC, block Gram-Schmidt methods, and block Krylov subspace methods.

Communication in high-performance computing {#sec:comm_hpc}
-------------------------------------------

As floating-point operations have become faster and less energy-intensive, <span>*communication*</span>– the memory operations levels of cache on a node or between parallelized processors on a network– has become a bottleneck in distributed computing. How expensive a memory operation is depends on the physical aspects of a specific system, specifically the <span>*latency*</span>, or the amount of time needed to pack and transmit a message, and the <span>*bandwidth*</span>, or how much information can be transmitted at a time. To improve algorithm performance in bandwidth-limited algorithms like Krylov subspace methods, it is therefore advantageous to increase the <span>*computational intensity*</span>, or the ratio between floating-point and memory operations @BalCDetal14. We pay particular attention to <span>*synchronization points*</span> ("sync points"), i.e., the steps in an algorithm that initiate a broadcast or reduce pattern to synchronize a quantity on all processors. Reducing calls to kernels with sync points is a straightforward way to improve computational intensity @AnzBFetal20.

Sync points in Krylov subspace methods arise primarily in the orthonormalization procedure, such as Arnoldi or Lanczos, both of which are reformulations of the Gram-Schmidt method, a standard method for orthonormalizing a basis one (block) vector at a time. For large $n$, vectors are typically partitioned row-wise and distributed among processors, meaning that any time an operation like an inner product or normalization is performed– which is at least once per (block) vector in Gram-Schmidt– a sync point is inevitable.

Other possibly communication-intensive kernels include applications of the operator $A$[^4] and applications of ${\bm{\mathcal{V}}}_m$, an $n \times ms$ Krylov basis matrix. We count each operation separately from sync points (block inner products and vector norms) in <span>`LowSyncBlockArnoldi`</span>; see Section \[sec:examples\].

Generalized block inner products {#sec:block_inner_prod}
--------------------------------

A <span>*block vector*</span> is a tall-skinny matrix ${\bm{X}}\in {\mathbb{C}}^{n \times s}$, and a <span>*block matrix*</span> is a matrix of $s \times s$ matrices, e.g., $${\mathcal{H}}=
\begin{bmatrix}
    H_{1,1} & H_{1,2}   &   \cdots  & H_{1,p} \\
    H_{2,1} & H_{2,2}   &   \cdots  & H_{2,p} \\
    \vdots  &   \vdots  &   \ddots  & \vdots \\
    H_{q,1} & H_{q,2}   &   \cdots  & H_{q,p}
\end{bmatrix}
\in {\mathbb{C}}^{qs \times ps}.$$ We use a mixture of <span><span style="font-variant:small-caps;">Matlab</span></span>- and block-indexing notation to handle block objects. In particular, we write ${\bm{\mathcal{V}}}_k$ to denote the first $k$ block vectors of the block-partitioned matrix ${\bm{\mathcal{V}}}= \begin{bmatrix} {\bm{V}}_1 & {\bm{V}}_2 & \cdots & {\bm{V}}_m \end{bmatrix}$ instead of (i.e., the first $ks$ columns). In a similar vein, $s \times s$ block entries of ${\mathcal{H}}$ are denoted as $H_{j,k}$ instead of as $H_{(j-1)s+1:js,(k-1)s+1:ks}$. We denote block generalizations of the standard unit vectors ${\widehat{{\bm{e}}}}_k$ as ${\widehat{\bm{E}}}_k := {\widehat{{\bm{e}}}}_k \otimes I_s$, where $\otimes$ is the Kronecker product and $I_s$ the identity matrix of size $s$.

Blocking is a <span>*batching*</span> technique that can reduce the number of calls to the operator $A$ applied to individual column vectors, maximize computational intensity by filling up the local cache with BLAS3 operations, and reduce the total number of sync points by performing inner products and normalization en masse @BakDJ06 [@Bir15]. In the context of Krylov subspaces, blocking can also lead to enriched subspaces by sharing information across column vectors instead of treating each right-hand side as an isolated problem. How much information is shared across columns depends on the choice of block inner product.

Let ${\mathbb{S}}$ be a $^*$-subalgebra of ${{\mathbb{C}}^{s \times s}}$ with identity; i.e., $I \in {\mathbb{S}}$ and when $ S,T \in {\mathbb{S}}$, $\alpha \in {\mathbb{C}}$, then $\alpha S +T, ST, S^* \in {\mathbb{S}}$.

\[def:block\_IPS\] A mapping ${{{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}\cdot,\cdot {\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}}}$ from ${\mathbb{C}}^{n\times s} \times {{\mathbb{C}}^{n \times s}}$ to ${\mathbb{S}}$ is called a <span>*block inner product onto ${\mathbb{S}}$*</span> if it satisfies the following conditions for all ${\bm{X}},{\bm{Y}},{\bm{Z}}\in {{\mathbb{C}}^{n \times s}}$ and $C \in {\mathbb{S}}$:

(i) *${\mathbb{S}}$-linearity*: ${{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{X}}+{\bm{Y}},{\bm{Z}}C {\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}} = {{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{X}},{\bm{Z}}{\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}} C + {{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{Y}},{\bm{Z}}{\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}} C$; \[S:linearity\]

(ii) *symmetry*: ${{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{X}},{\bm{Y}}{\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}} = {{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{Y}},{\bm{X}}{\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}}^*$; \[S:symmetry\]

(iii) *definiteness*: ${{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{X}},{\bm{X}}{\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}}$ is positive definite if ${\bm{X}}$ has full rank, and ${{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{X}},{\bm{X}}{\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}} = 0$ if and only if ${\bm{X}}= 0$. \[S:definiteness\]

\[def:scal\_quot\] A mapping ${N}$ which maps all ${\bm{X}}\in {{\mathbb{C}}^{n \times s}}$ with full rank on a matrix ${N}({\bm{X}}) \in {\mathbb{S}}$ is called a <span>*scaling quotient*</span> if for all such ${\bm{X}}$, there exists ${\bm{Y}}\in {{\mathbb{C}}^{n \times s}}$ such that ${\bm{X}}= {\bm{Y}}{N}({\bm{X}})$ and ${{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{Y}},{\bm{Y}}{\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}} = I_s$.

The scaling quotient is closely related to the intraorthogonalization routine discussed in Section \[sec:bgs\]. Block notions of orthogonality and normalization arise organically from Definitions \[def:block\_IPS\] and \[def:scal\_quot\].

\[def:block\_ortho\_norm\] Let ${\bm{X}}, {\bm{Y}}\in {{\mathbb{C}}^{n \times s}}$ and $\{{\bm{X}}_j \}_{j=1}^m \subset {{\mathbb{C}}^{n \times s}}$.

(i) ${\bm{X}}, {\bm{Y}}$ are <span>*block orthogonal*</span>, if ${{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{X}},{\bm{Y}}{\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}} = 0_s$.

(ii) ${\bm{X}}$ is <span>*block normalized*</span> if ${N}({\bm{X}}) = I_s$.

(iii) ${\bm{X}}_1, \ldots, {\bm{X}}_m$ are <span>*block orthonormal*</span> if ${{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{X}}_i,{\bm{X}}_j {\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}} = \delta_{ij} I_s$.

A set of vectors $\{{\bm{X}}_j\}_{j=1}^m \subset {{\mathbb{C}}^{n \times s}}$ <span>*block spans*</span> a space ${\mathscr{K}}\subseteq {{\mathbb{C}}^{n \times s}}$, and we write ${\mathscr{K}}= \operatorname{\operatorname{span}^{\mathbb{S}}}\{{\bm{X}}_j\}_{j=1}^m$ if $${\mathscr{K}}= \Big\{\sum_{j=1}^{m} {\bm{X}}_j \Gamma_j : \Gamma_j \in {\mathbb{S}}\mbox{ for } j = 1, \ldots, m \Big\}.$$ The set $\{{\bm{X}}_j\}_{j=1}^m$ constitutes a <span>*block orthonormal basis*</span> for ${\mathscr{K}}= \operatorname{\operatorname{span}^{\mathbb{S}}}\{{\bm{X}}_j\}_{j=1}^m$ if it is block orthonormal.

In this work, we consider only the <span>*classical*</span> and <span>*global*</span> block paradigms, described in Table \[tab:block\_inner\_products\]. These paradigms represent the two extremes of information-sharing, with the classical approach maximizing information shared among columns and the global approach minimizing it; see, e.g., @FroLS20 [Theorem 3.3]. Moreover, the global paradigm leads to a lower complexity per iteration in Krylov subspace methods, because what are matrix-matrix products in the classical paradigm get reduced to scaling operations in the global one. Many other paradigms are also possible; see, e.g., @Dre20 [@DreEn19].

<span>M<span>.2</span>| M<span>.1</span>| M<span>.25</span>| M<span>.3</span></span> & ${\mathbb{S}}$ & ${{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{X}},{\bm{Y}}{\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}}$ & $N({\bm{X}})$\
classical (<span>`cl`</span>) & ${{\mathbb{C}}^{s \times s}}$ & ${\bm{X}}^*{\bm{Y}}$ & $R$, where ${\bm{X}}= {\bm{Q}}R$, and ${\bm{Q}}\in {{\mathbb{C}}^{n \times s}}, {\bm{Q}}^*{\bm{Q}}= I_s$\
global (<span>`gl`</span>) & ${\mathbb{C}}I_s$ & $\tfrac{1}{s}\operatorname{trace}{({\bm{X}}^*{\bm{Y}})}I_s$ & $\tfrac{1}{\sqrt{s}}{{\left\lVert{\bm{X}}\right\rVert}_{\text{F}}}I_s$

Block Gram-Schmidt {#sec:bgs}
------------------

Block Gram-Schmidt (BGS) is a routine for orthonormalizing a set of block vectors $\{{\bm{X}}_j \}_{j=1}^m \subset {{\mathbb{C}}^{n \times s}}$. Writing $${\bm{\mathcal{X}}}:= \begin{bmatrix} {\bm{X}}_1 & {\bm{X}}_2 & \cdots & {\bm{X}}_m\end{bmatrix} \in {\mathbb{C}}^{n \times ms},$$ we define a BGS method as one that returns a block orthonormal ${\bm{\mathcal{Q}}}\in {\mathbb{C}}^{n \times ms}$ and a block upper triangular ${\mathcal{R}}\in {\mathbb{C}}^{ms \times ms}$ such that ${\bm{\mathcal{X}}}= {\bm{\mathcal{Q}}}{\mathcal{R}}$. Important measures in the analysis of BGS methods are the condition number of ${\bm{\mathcal{X}}}$, $$\label{eq:cond(X))}
    \kappa({\bm{\mathcal{X}}}) := \frac{\sigma_{\max}({\bm{\mathcal{X}}})}{\sigma_{\min}({\bm{\mathcal{X}}})},$$ i.e., the ratio between the largest and smallest singular values of ${\bm{\mathcal{X}}}$, and the <span>*loss of orthogonality (LOO)*</span>, $$\label{eq:loo}
    {\left\lVertI - {{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{\mathcal{Q}}},{\bm{\mathcal{Q}}}{\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}}\right\rVert},$$ where ${{{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}\cdot,\cdot {\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}}}$ is a generalized inner product as described in Section \[sec:block\_krylov\].

When we discuss the stabiliy of BGS methods, we refer to bounds on the loss of orthogonality in terms of machine precision, ${\varepsilon}$. We assume IEEE double precision here, so ${\varepsilon}= {\mathcal{O}\left(10^{-16}\right)}$.

For categorizing BGS variants, we recycle the skeleton-muscle notation from @CarLRetal22 [@Hoe10], where <span>*skeleton*</span> refers to the *inter*orthogonalization routine between block vectors, and the <span>*muscle*</span> refers to the *intra*orthogonalization routine between the columns of a single block vector. As a prototype, consider the Block Modified Gram-Schmidt (<span>`BMGS`</span>) skeleton, given by Algorithm \[alg:BMGS\]. Here, <span>`IntraOrtho`</span>denotes a generic muscle that takes ${\bm{X}}\in {\mathbb{C}}^{n \times s}$ and returns ${\bm{Q}}\in {\mathbb{C}}^{n \times s}$ and $R \in {\mathbb{C}}^{s \times s}$ such that ${{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{Q}},{\bm{Q}}{\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}} = I_s$ and ${\bm{X}}= {\bm{Q}}R$. For the classical paradigm, this could be any QR factorization: a column-wise Gram-Schmidt routine, Householder QR (<span>`HouseQR`</span>), Cholesky QR (<span>`CholQR`</span>), etc. As for the global paradigm, there is only one possible muscle, given by the global scaling quotient, which effectively reduces to normalizing block vectors with a scaled Frobenius norm.

\[htbp\]

\[1\]

We regard a single call to either ${{{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}\cdot,\cdot {\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}}}$ or <span>`IntraOrtho`</span>as one sync point, which is only possible in practice if single-reduce algorithms like <span>`CholQR`</span>@YamNYetal15 or <span>`TSQR`</span>/ <span>`AllReduceQR`</span>@DemGHetal12 [@MorYZ12] are employed for <span>`IntraOrtho`</span>.

Block Krylov subspace methods {#sec:block_krylov}
-----------------------------

The <span>*$m$th block Krylov subspace for $A$ and ${\bm{B}}$ (with respect to ${\mathbb{S}}$)*</span> is defined as $$\label{eq:block_krylov}
    {{\mathscr{K}}^{{\mathbb{S}}}}_m(A, {\bm{B}}) := \operatorname{\operatorname{span}^{\mathbb{S}}}\{{\bm{B}}, A{\bm{B}}, \ldots, A^{m-1}{\bm{B}}\}.$$

Block Arnoldi is often used to compute a basis for ${{\mathscr{K}}^{{\mathbb{S}}}}_m(A, {\bm{B}})$, and it is typically implemented with <span>`BMGS`</span>as the skeleton; see Algorithm \[alg:BMGS-Arnoldi\]. `BMGS-Arnoldi` accrues a high number of sync points due to the inner `for`-loop, where an increasing number of inner products is performed per block column.

\[htbp\]

\[1\] \[line:BMGS\]

Performing $m$ steps of a block Arnoldi routine returns the <span>*block Arnoldi relation*</span> $$\label{eq:block_arnoldi}
    A {\bm{\mathcal{V}}}_m = {\bm{\mathcal{V}}}_m {\mathcal{H}}_m + {\bm{V}}_{m+1} H_{m+1,m},$$ where ${\bm{\mathcal{V}}}_m$ ${\mathbb{S}}$-spans ${{\mathscr{K}}^{{\mathbb{S}}}}_m(A, {\bm{B}})$ and ${\mathcal{H}}_m$ denotes the $ms \times ms$ submatrix of ${\mathcal{H}}_{m+1,m}$.

### Block full orthogonalization methods with low-rank modifications {#sec:bfom_mod}

We define $$\label{eq:Xm}
    {\bm{X}}_m := {\bm{\mathcal{V}}}_m \big( {\mathcal{H}}_m + {\mathcal{M}}\big)^{{-1}}{\widehat{\bm{E}}}_1 {B},$$ where ${\widehat{\bm{E}}}_1 = {\widehat{{\bm{e}}}}_1 \otimes I_s$ is a standard block unit vector, as the <span>*(modified) block full orthogonalization method (BFOM)*</span> for approximating . When ${\mathcal{M}}= 0$, we recover BFOM, which minimizes the error in the $A$-weighted ${\mathbb{S}}$-norm for $A$ hermitian positive definite @FroLS17. There are infinitely many choices for ${\mathcal{M}}$, but perhaps only a few useful ones, some of which are discussed in @FroLS20. We will concern ourselves here with just ${\mathcal{M}}= {\mathcal{H}}_m^{{-*}}\big({\widehat{\bm{E}}}_m H_{m+1,m}^* H_{m+1,m}\big) {\widehat{\bm{E}}}_m^*$, which gives rise to a block generalized minimal residual method (BGMRES) @Sim96 [@SimGa96a; @SimGa96b]. As in @FroLS20, we implement as a modified BFOM here, with an eye towards downstream applications like $f(A){\bm{B}}$ where the BFOM form is explicitly needed. In practice, there may be computational savings with a modular implementation; see, e.g., @Gutknecht2007 [@GutSc08; @GutSc09].

### Static restarting and cospatial factors {#sec:restarting}

Restarting is a well established technique for reconciling a growing basis with memory limitations. Define the residual of as $$\label{eq:Rm}
    {\bm{R}}_m := {\bm{B}}- A {\bm{X}}_m.$$ The basic idea of restarts is to use ${\bm{R}}_m$ to build a new Krylov subspace, which we then use to approximate the error ${\bm{E}}_m := A^{{-1}}{\bm{B}}- {\bm{X}}_m$, which solves $A {\bm{E}}= {\bm{R}}_m$ in exact arithmetic. Building a new Krylov subspace from ${\bm{R}}_m$ directly is not a great idea, because it would require an extra computation with $A$. Furthermore, we need a cheap, accurate, and ideally locally computable way to approximate ${\left\lVert{\bm{R}}_m\right\rVert}$ from one cycle to the next in order to monitor convergence. In @FroLS20 a static restarting method for low-rank modified BFOM is introduced that satisfies these requirements. By "static," we mean the basis size $m$ is fixed from one restart cycle to the next, in contrast to adaptive or dynamic restart cycle lengths. We restate @FroLS20 [Theorem 4.1], which enables an efficient residual approximation and restarting procedure.

\[thm:restarts\] Suppose ${\mathcal{M}}= {\bm{M}}{\widehat{\bm{E}}}_m^*$, where ${\bm{M}}\in {\mathbb{C}}^{ms \times s}$ and ${\widehat{\bm{E}}}_m = {\widehat{{\bm{e}}}}_m \otimes I_s$. Define ${\bm{U}}_m := {\bm{\mathcal{V}}}_{m+1} \begin{bmatrix} {\bm{M}}\\ -H_{m+1,m} \end{bmatrix}$ and let ${\bm{\Xi}}_m := ({\mathcal{H}}_m + {\mathcal{M}})^{{-1}}{\widehat{\bm{E}}}_1 {B}$ be the block coefficient vector for the approximation ${\bm{X}}_m = {\bm{\mathcal{V}}}_m {\bm{\Xi}}_m$ of the system . With ${\bm{R}}_m$ as in it then holds that $$\label{eq:cosptial_UXi}
        {\bm{R}}_m = {\bm{U}}_m \big({\widehat{\bm{E}}}_m^* {\bm{\Xi}}_m\big).$$

We refer to the $s \times s$ matrix ${\widehat{\bm{E}}}_m^* {\bm{\Xi}}_m$ as a <span>*cospatial factor*</span>, and as the <span>*cospatial residual relation*</span>. The term <span>*cospatial*</span> refers to the fact that the columns of ${\bm{R}}_m$ and those of ${\bm{U}}_m$ span the same space. Moreover, in exact arithmetic, it is not hard to see that $$\label{eq:normF_Rm}
    {{\left\lVert{\bm{R}}_m\right\rVert}_{\text{F}}} = {{\left\lVert\begin{bmatrix} {\bm{M}}\\ -H_{m+1,m} \end{bmatrix} \big({\widehat{\bm{E}}}_m^* {\bm{\Xi}}_m\big)\right\rVert}_{\text{F}}},$$ and the right-hand term can be computed locally (and possibly redundantly on each processor) for $m \ll n$.

If the approximate residual norm does not meet the desired tolerance, then we can compute the Arnoldi relation for ${\mathscr{K}}_m(A, {\bm{U}}_m)$ to obtain ${\bm{\mathcal{V}}}_{m+1}^{(2)}$, ${\mathcal{H}}_m^{(2)}$, $H_{m+1,m}^{(2)}$, and ${B}^{(2)}$, where the superscript here and later denotes association to the restarted Krylov subspace. We then approximate ${\bm{E}}_m$ as $${\bm{D}}_m := {\bm{\mathcal{V}}}_m^{(2)} ({\mathcal{H}}_m^{(2)} + {\mathcal{M}}^{(2)})^{{-1}}{\widehat{\bm{E}}}_1 {B}^{(2)} \big({\widehat{\bm{E}}}_m^* {\bm{\Xi}}_m\big),$$ and update ${\bm{X}}_m$ as $${\bm{X}}_m^{(2)} := {\bm{X}}_m + {\bm{D}}_m.$$ The process is repeated, applying Theorem \[thm:restarts\] iteratively, until the desired residual tolerance is reached.

The analysis in @FroLS17 [@FroLS20] is carried out in exact arithmetic. Therefore, when we replace Algorithm \[alg:BMGS-Arnoldi\] with low-sync versions in Section \[sec:low\_sync\], all the results summarized in this section still hold, because all block Gram-Schmidt variants generate the same QR factorization in exact arithmetic.

Low-synchronization variants of block Arnoldi {#sec:low_sync}
=============================================

To distinguish between block Arnoldi variants, we default to the name of the underlying block Gram-Schmidt skeleton. We specify a <span>*configuration*</span> as `ip`-$\texttt{skel}\circ(\texttt{musc})$: inner product, skeleton, and muscle, respectively. This naturally leads to bit of an "alphabet soup," for which we ask the reader's patience, as it is crucial to precisely define algorithmic configurations for benchmarking. Please refer often to Table \[tab:skeletons\], which summarizes acronyms for all the Gram-Schmidt skeletons we consider in this text. Note that the coefficient in front of the number of sync points per cycle is often used to describe low-sync methods; e.g., <span>`BCGS-PIP`</span>is a "one-sync" method, while <span>`BMGS-SVL`</span>is a "three-sync" method.

<span>M<span>.15</span>|M<span>.25</span>|M<span>.1</span>|M<span>.15</span>|M<span>.175</span></span> & & & &\
<span>`BMGS`</span>& Block Modified Gram-Schmidt & \[sec:block\_krylov\] & & ${\mathcal{O}\left({\varepsilon}\right)} \kappa$, ${\mathcal{O}\left({\varepsilon}\right)} \kappa < 1$\
<span>`BCGS-PIP`</span>& Block Classical GS, Pythagorean with Inner Product& \[sec:bcgs\_p\] & & ${\mathcal{O}\left({\varepsilon}\right)} \kappa^2$, ${\mathcal{O}\left({\varepsilon}\right)} \kappa^2 < 1$\
& & & &\
<span>`BMGS-SVL`</span> / <span>`BMGS-LTS`</span>& Schreiber & Van Loan / Lower Triangular Solve & \[sec:svl\_lts\] & & ${\mathcal{O}\left({\varepsilon}\right)} \kappa$, ${\mathcal{O}\left({\varepsilon}\right)} \kappa < 1$\
<span>`BMGS-CWY`</span> / <span>`BMGS-ICWY`</span>& Compact WY / Inverse Compact WY & \[sec:cwy\_icwy\] & &\
<span>`BCGSI+LS`</span>& Inner Reorthogonalization (+), Low-Sync & \[sec:bcgs\_iro\_ls\] & &

The methods presented here are closely related to but not quite the same as the block methods used by Yamazaki et al. in @YamTHetal20, where <span>`BMGS`</span>, <span>`BCGS-PIP`</span>, and <span>`BCGSI+LS`</span>are employed as Gram-Schmidt skeletons in $s$-step Arnoldi (also known as communication-avoiding Arnoldi) @BalCDetal14 [@Car15; @Hoe10], which is used to solve a linear system with a single right-hand side. Recall that we are solving , i.e., multiple right-hand sides simultaneously.

\[rem:pseudocode\] In the pseudocode for each algorithm, intermediate quantities like ${\bm{W}}$ and ${\bm{U}}$ are defined explicitly each iteration for readability. In general, we purposefully avoid redefining quantities in a given iteration and instead only set an output (i.e., entries in ${B}$, ${\bm{\mathcal{V}}}_m$, or ${\mathcal{H}}_{m+1,m}$) once all computations pertaining to that value are complete. This approach simplifies mathematical analysis. Exceptions include Algorithms \[alg:BMGS\] and \[alg:BMGS-Arnoldi\], where ${\bm{W}}$ is redefined inside the `for`-loop as projected components are subtracted away from it. In practice, it is preferable to save storage by overwriting block vectors of ${\bm{\mathcal{V}}}_m$ instead of allocating separate memory for ${\bm{W}}$ and ${\bm{U}}$, for which there anyway may not be space.

<span>`BCGS-PIP`</span>and <span>`BCGS-PIO`</span> {#sec:bcgs_p}
--------------------------------------------------

A simple idea for reducing the number of sync points in <span>`BMGS`</span>is to condense the `for`-loop in lines 4-7 of Algorithm \[alg:BMGS-Arnoldi\] into a single inner product and subtraction, $$\begin{aligned}
    {\mathcal{H}}_{1:k,k} & = {{{\savebox{\@brx}{\(\m@th{\langle}\)}    \mathopen{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}{\bm{\mathcal{V}}}_k,{\bm{W}}{\savebox{\@brx}{\(\m@th{\rangle}\)}    \mathclose{\copy\@brx\kern-0.5\wd\@brx\usebox{\@brx}}}}_{{\mathbb{S}}}} \\
    {\bm{W}}& = {\bm{W}}- {\bm{W}}{\mathcal{H}}_{1:k,k}\end{aligned}$$ This exchange gives rise to what is commonly referred to as the block classical Gram-Schmidt (<span>`BCGS`</span>) method. It is, however, rather unstable, with a loss of orthogonality worse than ${\mathcal{O}\left({\varepsilon}\right)} \kappa^2([{\bm{B}}\,\, A{\bm{\mathcal{V}}}_m])$ @CarLR21. However, by making a correction based on the, we can guarantee a loss of orthogonality bounded by ${\mathcal{O}\left({\varepsilon}\right)} \kappa^2([{\bm{B}}\,\, A{\bm{\mathcal{V}}}_m])$, as long as ${\mathcal{O}\left(\sqrt{{\varepsilon}}\right)} \kappa([{\bm{B}}\,\, A{\bm{\mathcal{V}}}_m]) \leq 1$.

One version of the corrected algorithm is given as Algorithm \[alg:BCGSPIP-Arnoldi\]. The acronym "PIP" stands for "Pythagorean (variant) with Inner Product," due to how the factor $H_{k+1,k}$ is computed. An alternative formulation based off <span>`BCGS-PIO`</span>(where "PIO" stands for "Pythagoren with IntraOrthogonalization") is also possible and is given as Algorithm \[alg:BCGSPIO-Arnoldi\]. Note that in line 5, we use $\sim$ to denote that a full block vector need not be computed or stored here, just the $2s \times 2s$ scaling quotient $\Omega$. For subtle reasons, <span>`BCGS-PIO`</span>appears to be less reliable in practice (see Section \[sec:stab\_repro\]).

\[H\]

\[1\]

\[H\]

\[1\]

<span>`BMGS-SVL`</span>/ <span>`BMGS-LTS`</span> {#sec:svl_lts}
------------------------------------------------

Barlow developed and analyzed one of the first stabilized low-sync Gram-Schmidt methods by using the Schreiber-Van Loan representation of products of Householder transformations @Bar19 [@SchVa89]. Under modest conditions, this method– which we denote here as <span>`BMGS-SVL`</span>– has loss of orthogonality like <span>`BMGS`</span>. a formal analysis for the former remains open. We present Arnoldi versions of <span>`BMGS-SVL`</span>and <span>`BMGS-LTS`</span>as , with different colors highlighting the small differences between the methods. In both methods, the main inner product in line 4 is performed as in <span>`BCGS`</span>. Meanwhile ${\mathcal{T}}$ acts as a kind of buffer, storing the loss of orthogonality per iteration, which is used in successive iterations to make small corrections to the computation in line 4. Balabanov and Grigori use a similar technique to stabilize randomized sketches of inner products, where instead of explicitly computing and storing ${\mathcal{T}}$, they solve least squares problems to compute ${\mathcal{H}}_{1:k,k}$ @BalGr21 [@BalGr22].

\[htbp!\]

\[1\]

<span>`BMGS-CWY`</span>/ <span>`BMGS-ICWY`</span> {#sec:cwy_icwy}
-------------------------------------------------

A column-wise version of this algorithm was first presented by Świrydowicz et al. as @SwiLAetal20 [Algorithm 8]. To the best of our knowledge, we are the first to develop a block-wise formulation, which we refer to here as `BMGS-CWY-Arnoldi`, where CWY stands for "compact WY," an alternative way to represent Householder transformations used to originally derive this algorithm. A related Arnoldi algorithm, not treated in either @SwiLAetal20 or @ThoCRetal22, is based on the inverse CWY (ICWY) form, and is given simultaneously with <span>`BMGS-CWY`</span>in Algorithm \[alg:BMGSCWY-Arnoldi\].

It is important to note that `BMGS-CWY-Arnoldi` would not reduce to @SwiLAetal20 [Algorithm 8] or @ThoCRetal22 [Algorithm 6.1] for $s=1$, as we have one total sync point, due to the lack of a reorthonormalization step for ${\bm{V}}_k$. Algorithm \[alg:BMGSCWY-Arnoldi\] was largely derived by transforming <span>`BMGS-CWY`</span>and <span>`BMGS-ICWY`</span>from @CarLRetal22 into a block Arnoldi routine. The most challenging part is tracking how the ${\mathcal{R}}$ factor in the Gram-Schmidt formulation maps to ${\mathcal{H}}_{m+1,m}$ and determining where to scale by the off-diagonal entry $H_{k,k-1}$ each iteration. It is also possible to compute only with ${\mathcal{R}}$ and reconstruct ${\mathcal{H}}_{m+1,m}$ after ${\bm{\mathcal{V}}}_{m+1}$ is finished; this approach proved to be much less stable in practice, however, due to the growing condition number of ${\mathcal{R}}$.

\[htbp!\]

\[1\]

<span>`BCGSI+LS`</span> {#sec:bcgs_iro_ls}
-----------------------

One of the most intriguing of all the low-sync algorithms is DCGS2 @BieLTetal22, referred to as <span>`CGSI+LS`</span>in @CarLRetal22. This algorithm is a reformulation of reorthogonalized CGS with a single sync point derived by "delaying" normalization to the next iteration, where operations are batched in a kind of $s$-step approach (where $s = 2$). The column-wise version exhibits ${\mathcal{O}\left({\varepsilon}\right)}$ loss of orthogonality; a rigorous proof of the backward stability bounds remains open, however. The block version, <span>`BCGSI+LS`</span>, does not exhibit perfect ${\mathcal{O}\left({\varepsilon}\right)}$ LOO; see numerical results in @CarLRetal22.

Bielich et al. present a column-wise Arnoldi based on DCGS2 as Algorithm 4 in @BieLTetal22. Our Algorithm \[alg:BCGSIROLS-Arnoldi\] is a direct block generalization of this algorithm with slight reformulations to match the aesthetics of Algorithm \[alg:BMGSCWY-Arnoldi\] and principles of Remark \[rem:pseudocode\]. Note that, as in Algorithm \[alg:BMGSCWY-Arnoldi\], we are able to compute ${\mathcal{H}}_m$ directly, but we must track an auxiliary matrix ${\bm{J}}$ and scale several quantities by $H_{k-1,k-2}$. An alternative version of Algorithm \[alg:BCGSIROLS-Arnoldi\] based more directly on <span>`BCGSI+LS`</span>from @CarLRetal22 [Algorithm 7] is included in the code but not described here.

\[htbp!\]

\[1\]

Adaptive restarting {#sec:stab_repro}
===================

Reproducibility and stability are not mutually exclusive. This realization is precisely the motivation for an adaptive restarting routine and can be demonstrated by a simple example.

Consider the <span>`tridiag`</span>test case from Section \[sec:tridiag\] with $n = 100$. Notably, both $A$ and ${\bm{B}}$ are deterministic quantities; neither is defined with random elements. In <span><span style="font-variant:small-caps;">Matlab</span></span>, it is possible to specify the number of threads on which a script is executed via the built-in `maxNumCompThreads` function.[^5] We solve $A {\bm{X}}= {\bm{B}}$ with Algorithms \[alg:BCGSPIP-Arnoldi\] and \[alg:BCGSPIO-Arnoldi\] while varying the multithreading setting from 1 to 16 on a standard node of the Mechthild cluster; see the beginning of Section \[sec:examples\] for more details about the cluster. For both algorithms, we employ a variant of <span><span style="font-variant:small-caps;">Matlab</span></span>'s Cholesky routine <span>`chol`</span>, which stores a flag when <span>`chol`</span>determines a matrix is too ill-conditioned to be factorized. This flag is fed to the linear solver driver of <span>`LowSyncBlockArnoldi`</span>(`bfom`), which halts the process when the flag is true. Through the following discussion, we refer to this flag as the "<span>`NaN`</span>-flag,"

Figure \[fig:tridiag\_multithread\] displays the loss of orthogonality and $\kappa([{\bm{B}}\,\, A {\bm{\mathcal{V}}}_k])$ for different thread counts. The condition numbers for all thread counts and both methods are hardly affected, except for some slight deviation for <span>`BCGS-PIP`</span>and 16 threads. The LOO plots are more telling: for both methods, changing the thread count directly affects the LOO and how many iterations the method can compute before encountering a <span>`NaN`</span>-flag. We allowed for a maximum basis size of $m=50$, but no method can compute that far. <span>`BCGS-PIO`</span>with 8 threads gives up first at 16 iterations; <span>`BCGS-PIP`</span>with 1 and 4 threads makes it all the way to 35 iterations. Among the <span>`BCGS-PIO`</span>methods, there are orders of magnitude differences between the attained LOO.

: the problem is static, and the same code has been run every time. The only variable is the thread count.

There are two subtle issues that affect reproducibility in this case: 1) the configuration of math kernel libraries according to the parameters of the operating system and hardware,[^6] and 2) guaranteed stability bounds. As for stability bounds, it is important to note that both <span>`BCGS-PIO`</span>and <span>`BCGS-PIP`</span>have a complete backward stability analysis @CarLR21. Both methods have ${\mathcal{O}\left({\varepsilon}\right)} \kappa^2([{\bm{B}}\,\, A {\bm{\mathcal{V}}}_k])$ loss of orthogonality, as long as $\kappa([{\bm{B}}\,\, A {\bm{\mathcal{V}}}_k]) \leq {\mathcal{O}\left(\frac{1}{\sqrt{{\varepsilon}}}\right)} = {\mathcal{O}\left(10^8\right)}$ and as long as the <span>`IntraOrtho`</span>for <span>`BCGS-PIO`</span>behaves no worse than <span>`CholQR`</span>. (For this test, we used <span>`HouseQR`</span>, <span><span style="font-variant:small-caps;">Matlab</span></span>'s built-in `qr` routine, which is unconditionally stable and therefore behaves better than <span>`CholQR`</span>@Hig02.) For both methods, $\kappa([{\bm{B}}\,\, A {\bm{\mathcal{V}}}_k])$ exceeds ${\mathcal{O}\left(10^8\right)}$ around iteration 15. At that point, the assumptions for the LOO bounds are no longer satisfied. The fact that either algorithm continues to compute something useful after that point is a lucky accident.

  -- --
     
     
     
  -- --

Computing $\kappa([{\bm{B}}\,\, A {\bm{\mathcal{V}}}_k])$ every iteration to check whether the LOO bounds are satisfied is not practical. We therefore propose a simple adaptive restarting regime based on whether <span>`chol`</span>raises a <span>`NaN`</span>-flag, which happens whenever <span>`chol`</span> a numerically non-positive definite matrix. When a <span>`NaN`</span>-flag is raised, we give up computing a new basis vector and go back to the last safely computed basis vector, which is then used to restart. Simultaneously, the maximum basis size $m$ is also reduced. It is possible that an algorithm exhausts its maximum allowed restarts and basis size before converging; indeed, we have observed this often for <span>`BCGS-PIP`</span>in examples not reported here. At the same time, there are many scenarios in which restarting is an adequate band-aid, thus allowing computationally cheap, one-sync algorithms line <span>`BCGS-PIP`</span>to salvage progress and converge, oftentimes faster than competitors. See Section \[sec:examples\] for demonstrations.

The restarted framework outlined in Section \[sec:restarting\] does not change fundamentally with adaptive cycle lengths; only the notation becomes more complicated. We omit the details here.

Numerical benchmarks {#sec:examples}
====================

Our treatment of BGS and block Krylov methods is hardly exhaustive. It is not our goal to determine the optimal block Arnoldi configuration at this stage, but rather to demonstrate the functionality of a benchmarking tool for the fair comparison of possible configurations on different problems. To this end, we restrict ourselves to the options below:

-   inner products: <span>`cl`</span>(classical), <span>`gl`</span>(global)

-   skeletons: Table \[tab:skeletons\]

-   muscles: <span>`CholQR`</span>, which has ${\mathcal{O}\left({\varepsilon}\right)} \kappa^2$ loss of orthogonality guaranteed only for ${\mathcal{O}\left({\varepsilon}\right)} \kappa^2 < 1$, but is a simple, single-reduce algorithm. In practice, we would recommend <span>`TSQR`</span>/<span>`AllReduceQR`</span>@DemGHetal12 [@MorYZ12], which has ${\mathcal{O}\left({\varepsilon}\right)}$ loss of orthogonality and the same number of sync points, but is difficult to program in <span><span style="font-variant:small-caps;">Matlab</span></span>due to limited parallelization and message-passing features. Other low-sync muscles are programmed in <span>`LowSyncBlockArnoldi`</span>as well, and the user can easily integrate their own. Note that <span>`BCGS-PIP`</span>does not require a muscle, and <span>`BMGS-CWY`</span>, <span>`BMGS-ICWY`</span>, and <span>`BCGSI+LS`</span>only call a muscle once, in the first iteration of a new basis. <span>`BMGS-SVL`</span>and <span>`BMGS-LTS`</span>are forced to use their column-wise counterparts <span>`MGS-SVL`</span>and <span>`MGS-LTS`</span>(both 3-sync), respectively, and global methods are forced to use the global muscle (i.e., ).

-   modification: `none` (FOM), `harmonic` (GMRES)

All results are generated by the <span>`LowSyncBlockArnoldi`</span><span><span style="font-variant:small-caps;">Matlab</span></span>package. A single script (`paper_script.m`) comprises all the calls for generating the results in this manuscript. <span>`LowSyncBlockArnoldi`</span>is written as modularly as possible, to facilitate the exchange of inner products, skeletons, muscles, and modifications. While the timings reported certainly do not reflect the optimal performance for any of the methods, they do reflect a fair comparison across implementations and provide insights for possible speed-ups when these methods are ported to more complex architectures. The code is also written so that sync points (<span>`inner_prod`</span>and <span>`intra_ortho`</span>) and other potentially communication-intensive operations (<span>`matvec`</span>and <span>`basis_eval`</span>) are separate functions that can be tuned individually.

Every test script (including the example from Section \[sec:stab\_repro\]) has been executed in <span><span style="font-variant:small-caps;">Matlab</span></span>R2019b on 16 threads of a single, standard node of Linux Cluster Mechthild at the Max Planck Institute for Dynamics of Complex Technical Systems in Magdeburg, Germany.[^7] A standard node comprises 2 Intel Xeon Silver 4110 (Skylake) CPUs with 8 Cores each (64KB L1 cache, 1024KB L2 cache), a clockrate of 2.1 GHz (3.0 GHz max), and 12MB shared L3 cache each. We further focus on small problems that easily fit in the L3 Cache, which is easy to guarantee with sparse $A$, $n \leq 10^4$, and $s \leq 10$. Given that the latency between CPUs on a single node is small relative to exascale machines, we expect small improvements observed in these test cases to translate to bigger gains in a more complex setting.

For the timings, we measure the total time spent to reach a specified error tolerance. We run each test 5 times and average over the timings. We also calculate several intermediate measures, namely counts for $A$-calls, applications of ${\bm{\mathcal{V}}}_k$, and sync points. In addition, we plot the convergence history in terms of the following quantities per iteration: relative residual, relative error, $\kappa([{\bm{B}}\, \, A {\bm{\mathcal{V}}}_k])$, and loss of orthogonality (LOO) . When a ground truth solution ${\bm{X}}_*$ is provided, the error is calculated as $${{\left\lVert{\bm{X}}_k - {\bm{X}}_*\right\rVert}_{\text{F}}} / {{\left\lVert{\bm{X}}_*\right\rVert}_{\text{F}}},$$ For all our examples, ${\bm{X}}_*$ is computed by <span><span style="font-variant:small-caps;">Matlab</span></span>'s built-in `backslash` operator. The residual is approximated by and is scaled by ${{\left\lVert{\bm{B}}\right\rVert}_{\text{F}}}$. A summary of the parameters for all benchmarks can be found in Table \[tab:parameters\]. Except for <span>`tridiag`</span>and <span>`lapl_2d`</span>, all examples are taken from the SuiteSparse Matrix Collection @DavH11. Via the `suite_sparse.m` script, it is possible to run tests on any benchmark from this collection.

                                         $\kappa(A)$                                              
  ------------------------- ------------------------------------- --------- ------ ------ ------- ------------
  <span>`tridiag`</span>      ${\mathcal{O}\left(10^3\right)}$     $1000$    $2$    $70$    FOM    $10^{-10}$
  <span>`1138_bus`</span>     ${\mathcal{O}\left(10^6\right)}$     $1138$    $5$    $30$   GMRES   $10^{-6}$
  `circuit_2`                 ${\mathcal{O}\left(10^5\right)}$     $4510$    $5$    $10$   GMRES   $10^{-6}$
  `rajat03`                   ${\mathcal{O}\left(10^7\right)}$     $7602$    $5$    $10$   GMRES   $10^{-6}$
  `Kaufhold`                 ${\mathcal{O}\left(10^{14}\right)}$   $8765$    $5$    $10$   GMRES   $10^{-6}$
  `t2d_q9`                    ${\mathcal{O}\left(10^3\right)}$     $9801$    $5$    $10$   GMRES   $10^{-6}$
  <span>`lapl_2d`</span>      ${\mathcal{O}\left(10^3\right)}$     $10000$   $10$   $25$    FOM    $10^{-6}$

  : Test properties and parameter choices. \[tab:parameters\]

<span>`tridiag`</span> {#sec:tridiag}
----------------------

The operator $A$ is defined as a sparse, tridiagonal matrix with $1$ on the off-diagonals and $-1, -2, \ldots, -n$ on the diagonal, where $n$ is also the size of $A$. Clearly $A$ is symmetric. The right-hand side ${\bm{B}}$ has two columns, where the first has identical elements $\frac{1}{\sqrt{n}}$ and the second is $1, 2, \ldots, n$. This example is actually procedural, in the sense that a user can choose a desired $n$. At the same time, a larger $n$ necessarily leads to a worse condition number.

Figure \[fig:tridiag\] presents the total run time per configuration as well as operator counts as a bar chart; see Table \[tab:tridiag\] in the Appendix for more details. The fastest methods are the stabilized low-sync variants. Despite being the computationally cheapest classical method per iteration, <span>`cl`</span>-<span>`BCGS-PIP`</span>is notably slower than <span>`cl`</span>-<span>`BMGS`</span>, because its inherent instability requires restarting $3$ times (and therefore additional applications of $A$ and ${\bm{\mathcal{V}}}_k$) before converging. The method with the fewest ${\bm{\mathcal{V}}}_k$ evaluations is <span>`cl`</span>-<span>`BMGS`</span>, which is to be expected, since the basis is split up and applied one block column at a time in the inner-most loop; see Algorithm \[alg:BMGS\].

The fastest global method, <span>`gl`</span>-<span>`BCGS-PIP`</span>, is significantly slower even than the slowest classical method. In fact, all global methods require over 6 times as many total iterations as the fastest classical method to converge; this is in line with the theory of Section \[sec:block\_krylov\]. In this particular case, the floating-point savings per iteration do not outweigh the sheer amount of time needed for all the extra $A$-calls. Nevertheless, the one-sync global methods (<span>`gl`</span>-<span>`BCGS-PIP`</span>, <span>`gl`</span>-<span>`BMGS-CWY`</span>, <span>`gl`</span>-<span>`BMGS-ICWY`</span>, and <span>`gl`</span>-<span>`BCGSI+LS`</span>) have relatively low sync counts, compared even to <span>`cl`</span>-<span>`BMGS`</span>.

Figures \[fig:tridiag\_gl\_conv\] and \[fig:tridiag\_cl\_conv\] display convergence histories for a subset of the methods in Table \[tab:tridiag\]. The convergence histories for all global <span>`BMGS`</span>variants are very similar; we omit <span>`BMGS-SVL`</span>and <span>`BMGS-CWY`</span>, as they are visually identical to <span>`BMGS-LTS`</span>and <span>`BMGS-ICWY`</span>, respectively. <span>`BMGS`</span>is identical to <span>`BMGS-SVL`</span>and <span>`BMGS-LTS`</span>and is therefore also omitted.

Both the classical and global variants of <span>`BCGS-PIP`</span>show the robustness of the adaptive restarting procedure in action. In the global case, the LOO exceeds ${\mathcal{O}\left(10^{-10}\right)}$ and reaches ${\mathcal{O}\left(1\right)}$ in <span>`cl`</span>-<span>`BCGS-PIP`</span>. Despite the loss of orthogonality, restarting allows the methods to recover and eventually converge. All other low-sync variants remain stable, only restarting once the basis size limit of $m = 70$ has been reached. Although hardly perceptible, <span>`BMGS-ICWY`</span>does have a slightly worse LOO than that of <span>`BMGS-LTS`</span>, which can be seen by zooming in on the last few iterations of the global plots in Figure \[fig:tridiag\_gl\_conv\] or of the classical plots in Figure \[fig:tridiag\_cl\_conv\].

We also note that the residual estimate for all methods follows the same qualitative trend as that of the error. In the worst case, <span>`cl`</span>-<span>`BCGS-PIP`</span>, the residual is nearly 3 orders of magnitude lower than the error in some places, which could lead to premature convergence. For all other methods, the difference is between 1 and 2 orders of magnitude. We would thus recommend setting the residual tolerance a couple orders of magnitude lower in practice, to ensure that the true error is accurate enough.

  -- --
     
     
     
  -- --

  -- --
     
     
     
  -- --

<span>`1138_bus`</span> {#sec:1138_bus}
-----------------------

Now we turn to a slightly more complicated matrix. The matrix $A$ comes from a power network problem and is real and symmetric positive definite, while from the uniform distribution. Moreover we apply an incomplete LU (ILU) preconditioner with no fill, using <span><span style="font-variant:small-caps;">Matlab</span></span>'s built-in `ilu`.

Even with the preconditioner, none of the global methods converges. We adjusted the thread count to see if it would aid convergence, to no avail. This is perhaps an extreme case of @FroLS20 [Theorem 3.3], wherein the global method is much less accurate than the classical method in the first cycle and cannot manage to catch up even after restarting. A preconditioner better attuned to the structure of the problem may alleviate stagnation for global methods, but we do not explore this here.

In Figure \[fig:1138\_bus\_perf\] we see the performance results for the convergent classical methods; more details can be found in Table \[tab:1138\_bus\]. Most notably, the one-sync methods <span>`BMGS-CWY`</span>, <span>`BMGS-ICWY`</span>, and <span>`BCGSI+LS`</span>improve over <span>`BMGS`</span>only slightly in terms of timings. <span>`BCGS-PIP`</span>is much slower, due to a quick loss of orthogonality and need to restart more often. However, it is clear that sync counts for all one-sync methods are drastically reduced compared to that of <span>`BMGS`</span>.

We examine the convergence histories of <span>`cl`</span>-<span>`BCGS-PIP`</span>and <span>`cl`</span>-<span>`BMGS-ICWY`</span>more closely in Figure \[fig:1138\_bus\_conv\]. Although not discernible on the graph, we found that <span>`cl`</span>-<span>`BCGS-PIP`</span>actually restarts every 28 iterations, meaning in the first cycle it encountered a <span>`NaN`</span>-flag and reduced the maximum basis size to $m = 28$ for all subsequent cycles. Instability in the first cycle thus hinders <span>`cl`</span>-<span>`BCGS-PIP`</span>greatly. On the other hand, <span>`BMGS-ICWY`</span>(as well as the other variants) is stable enough to exhaust the entire basis size allowance, which allows for further error reduction in the first cycle.

  -- --
     
  -- --

`circuit_2` {#sec:circuit_2}
-----------

The next example comes from a circuit simulation problem. The matrix $A$ is real but not symmetric or positive definite. We again apply an ILU preconditioner with no fill.

All the one-sync classical and global methods converge, and their performance data is presented in Figure \[fig:circuit\_2\_perf\] with further details in Table \[tab:circuit\_2\]. In fact, some global methods, like <span>`gl`</span>-<span>`BCGS-PIP`</span>, are even faster than some classical methods, due to the fact that they require the same number of iterations to converge, and therefore fewer floating-point operations.

Figure \[fig:circuit\_2\_conv\] demonstrates how close in accuracy the global and classical <span>`BCGS-PIP`</span>variants are for this problem. The global method even has a slightly better LOO, but it should be noted that global LOO is measured according to a different inner product than classical LOO; see Section \[sec:block\_inner\_prod\] and .

  -- --
     
  -- --

`rajat03` {#sec:rajat03}
---------

Another circuit simulation problem highlights slightly different behavior. In this case, $A$ is again real but neither symmetric nor positive definite, and we again use an ILU preconditioner with no fill.

Figure \[fig:rajat03\_perf\] summarizes the performance results, with details given in Table \[tab:rajat03\]. It should be noted right away that <span>`cl`</span>-<span>`BCGS-PIP`</span>fails to converge for this problem, while <span>`gl`</span>-<span>`BCGS-PIP`</span>does not, and takes second place in terms of the timings. More specifically, <span>`cl`</span>-<span>`BCGS-PIP`</span>encounters a <span>`NaN`</span>-flag it cannot resolve, which means that every time it reduces the basis size, it cannot avoid a <span>`NaN`</span>-flag. However, because global methods do not use Cholesky at all, non-positive definite factors do not pose a problem, unless their trace is numerically zero, which occurs with very low probability. Otherwise, <span>`cl`</span>-<span>`BMGS-CWY`</span>shows a small improvement over <span>`cl`</span>-<span>`BMGS`</span>.

Table \[tab:rajat03\] confirms that none of the methods requires restarting despite how high the condition number becomes in later iterations; see also Figure \[fig:rajat03\_conv\]. It is again interesting to see how close the error and residual plots are between the global and classical methods. In fact, the residual for the global method underestimates convergence by a couple orders of magnitude.

  -- --
     
  -- --

`Kaufhold` {#sec:kaufhold}
----------

This example treats a nearly numerically singular matrix with an extremely high condition number. Also notable, the norm of $A$ is nearly ${\mathcal{O}\left(10^{15}\right)}$. The matrix is real, but neither symmetric nor positive definite, and it was designed to trigger a bug in Gaussian elimination in a 2002 version of <span><span style="font-variant:small-caps;">Matlab</span></span>. We again apply an ILU preconditioner with no fill.

Figure \[fig:Kaufhold\_perf\] shows <span>`cl`</span>-<span>`BCGS-PIP`</span>to be the fastest of the classical one-sync methods, but the improvement over <span>`cl`</span>-<span>`BMGS`</span>is small. The global methods are all much slower. A look at the convergence histories in Figure \[fig:Kaufhold\_conv\] shows a stubborn error curve despite significant progress in the initial iterations. For both <span>`BCGS-PIP`</span>methods the LOO is moderately high in the first cycle, matching the high condition numbers, but the situation is not bad enough to trigger a <span>`NaN`</span>-flag, and the LOO drops after restarting.

  -- --
     
  -- --

`t2d_q9` {#sec:t2d_q9}
--------

We now examine a nonlinear diffusion problem, specifically a biquadratic mesh of a temperature field. The matrix $A$ is real but not symmetric or positive definite, and we again use an ILU preconditioner with no fill.

Figure \[fig:t2d\_q9\_perf\] shows that both <span>`BCGS-PIP`</span>are the fastest overall, with <span>`cl`</span>-<span>`BMGS`</span>in second-to-last place; see Table \[tab:t2d\_q9\] for more details. Interestingly, even <span>`gl`</span>-<span>`BMGS`</span>is faster than <span>`cl`</span>-<span>`BMGS`</span>in this scenario.

Both <span>`BCGSI+LS`</span>variants are rather slow in this example. Despite having just one sync per iteration, <span>`BCGSI+LS`</span>does generally have a higher complexity than its one-sync counterparts, which manifests here as a disadvantage.

The convergence behavior for the <span>`BCGS-PIP`</span>variants is given in Figure \[fig:t2d\_q9\_conv\]. Here we see that despite the global condition number having a high variation relative to the classical method, the global LOO is overall much less. This phenomenon is not unique to this example, however, it just happens to be more noticeable.

  -- --
     
  -- --

<span>`lapl_2d`</span> {#sec:lapl_2d}
----------------------

Our last problem is taken directly from @FroLS17 [Section 5.4], a discretized two-dimensional Laplacian matrix. $A$ is thus banded, real, and symmetric positive definite. We do not apply a preconditioner, and look at all skeletons considered in the text.

Figure \[fig:lapl\_2d\_perf\] shows the performance results; more details can be found in Table \[tab:lapl\_2d\]. All one-sync classical methods except for <span>`cl`</span>-<span>`BCGSI+LS`</span>beat <span>`cl`</span>-<span>`BMGS`</span>, along with a number of global methods. The slowest classical methods are the three-sync ones, and some one-sync global methods follow behind. The fastest method, <span>`cl`</span>-<span>`BCGS-PIP`</span>also happens to have the highest $A$ count and applications of ${\bm{\mathcal{V}}}_k$, due to its high number of restarts. Both <span>`cl`</span>-<span>`BMGS-CWY`</span>and <span>`cl`</span>-<span>`BMGS-ICWY`</span>, however, have fewer sync counts, as well as $A$ counts and ${\bm{\mathcal{V}}}_k$ counts, and are very close in terms of timings.

The methods with the highest sync counts are <span>`cl`</span>-<span>`BMGS-SVL`</span>and <span>`cl`</span>-<span>`BMGS-LTS`</span>. The reason is that they cannot use <span>`CholQR`</span>as a muscle,[^8] and this problem requires many iterations to converge. <span>`LowSyncBlockArnoldi`</span>is written to count sync points within the muscles as well, and with <span>`MGS-SVL`</span>and <span>`MGS-LTS`</span>each contributing $1 + 3s$ per call, the total number of sync points eventually passes that of <span>`cl`</span>-<span>`BMGS`</span>, which can use a communication-light muscle like <span>`CholQR`</span>.

Conclusions and outlook {#sec:conclusion}
=======================

Stability bounds and floating-point analysis are challenging to work out rigorously, and it is therefore simultaneously important to search for counterexamples and edge cases while trying to prove conjectured bounds. In general, rigorous loss of orthogonality and backward error bounds for all these methods could lead to new insights and improvements in the quest for a reliable, scalable Krylov subspace solver. Our flexible benchmarking tool can aid in that process, and it can easily be extended to accommodate new algorithm .

At the same time, low-sync block Arnoldi algorithms with adaptive restarting are clearly already useful and robust enough for a wide variety of problems, especially where $A$ is reasonably conditioned and memory limitations cap basis sizes. In every benchmark, we have observed that at least one low-sync method outperformed both the classical and global <span>`BMGS`</span>-based Arnoldi methods.

For scenarios where the basic adaptive restarting procedure is not sufficient to rescue convergence, it might be possible to improve the heuristics with a cheap estimate of the loss of orthogonality computed, e.g., a randomized sketched inner product @BalGr22. With such a cheap estimate, we could not only decrease the basis size when there are problems, but increase it again in later cycles. Randomized algorithms themselves are known to reduce communication, and a thorough comparison and combination of the methods proposed here and in @BalGr22 could lead to powerful Krylov subspace method well suited for exascale architectures.

Declarations
============

#### Ethical Approval and Consent to participate

The author certifies that this manuscript has been submitted to only one journal at this time, that the work is original, and that the results are not fabricated or skewed. The work is entirely the author's own, and to the best of the author's ability, the work is complete in its own right and without error or misappropriation.

#### Consent for publication

As the sole author, K. Lund provides consent for publication.

#### Human and Animal Ethics

Not applicable.

#### Availability of supporting data

All code and scripts to reproduce plots can be found at <https://gitlab.mpi-magdeburg.mpg.de/lund/low-sync-block-arnoldi>.

#### Competing interests

The author has no relevant financial or non-financial interests to disclose.

#### Funding

K. Lund is a contracted employee of Max Planck Institute for Dynamics of Complex Technical Systems and did not receive any additional funding to support this project.

#### Authors' contributions

K. Lund is the sole author of the manuscript and associated code.

#### Acknowledgments

The author is indebted to Stéphane Gaudreault, Teodor Nikolov, and Erin Carson for stimulating discussions that inspired this work. The author is also grateful to Jens Saak and Martin Köhler for answering questions about the Mechthild cluster and multithreading in MATLAB

Raw data from tests
===================

  -------------------------------------------------------------------------------------------------- ---------- ------- --- ----- ----- ------ -------
           <span>`gl`</span>-${\texttt{BMGS}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>           2.20e+00   0.00    9   621   621   1242   22401
         <span>`gl`</span>-${\texttt{BMGS-SVL}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>         2.05e+00   6.59    9   621   621   1863   1872
         <span>`gl`</span>-${\texttt{BMGS-LTS}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>         2.03e+00   7.90    9   621   621   1863   1872
         <span>`gl`</span>-${\texttt{BCGSI+LS}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>         1.84e+00   16.53   9   621   630   2493    639
         <span>`gl`</span>-${\texttt{BMGS-CWY}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>         1.58e+00   28.26   9   621   630   1872    639
        <span>`gl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>         1.48e+00   32.86   9   621   630   1872    639
         <span>`gl`</span>-${\texttt{BCGS-PIP}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>         1.37e+00   37.79   9   621   621   1863    630
   <span>`cl`</span>-${\texttt{BCGS-PIP}\xspace}\circ {\texttt{CholQR}\xspace}$-<span>`FOM`</span>    5.33e-01   75.77   3   172   172   516     175
     <span>`cl`</span>-${\texttt{BMGS}\xspace}\circ {\texttt{CholQR}\xspace}$-<span>`FOM`</span>      4.08e-01   81.44   2   94    94    188    2881
   <span>`cl`</span>-${\texttt{BMGS-CWY}\xspace}\circ {\texttt{CholQR}\xspace}$-<span>`FOM`</span>    2.80e-01   87.28   2   94    96    284     98
   <span>`cl`</span>-${\texttt{BMGS-SVL}\xspace}\circ {\texttt{MGS-SVL}\xspace}$-<span>`FOM`</span>   2.79e-01   87.32   2   96    96    288     584
   <span>`cl`</span>-${\texttt{BMGS-LTS}\xspace}\circ {\texttt{MGS-LTS}\xspace}$-<span>`FOM`</span>   2.69e-01   87.805-713-0782     584
   <span>`cl`</span>-${\texttt{BCGSI+LS}\xspace}\circ {\texttt{CholQR}\xspace}$-<span>`FOM`</span>    2.56e-01   88.805-713-0782     98
   <span>`cl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ {\texttt{CholQR}\xspace}$-<span>`FOM`</span>   2.23e-01   89.805-713-0782     98
  -------------------------------------------------------------------------------------------------- ---------- ------- --- ----- ----- ------ -------

  : Results from <span>`tridiag`</span>example. \[tab:tridiag\]

  --------------------------------------------------------------------------------------------------- ---------- ------- --- ----- ----- ----- ------
   <span>`cl`</span>-${\texttt{BCGS-PIP}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    1.84e+00   0.00    8   224   224   672   232
     <span>`cl`</span>-${\texttt{BMGS}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>      9.25e-01   49.75   3   88    88    176   1427
   <span>`cl`</span>-${\texttt{BCGSI+LS}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    7.97e-01   56.70   3   88    91    355    94
   <span>`cl`</span>-${\texttt{BMGS-CWY}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    7.82e-01   57.50   3   88    91    267    94
   <span>`cl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>   7.78e-01   57.70   3   88    91    267    94
  --------------------------------------------------------------------------------------------------- ---------- ------- --- ----- ----- ----- ------

  : Results from <span>`1138_bus`</span>example. \[tab:1138\_bus\]

  --------------------------------------------------------------------------------------------------- ---------- ------- --- ---- ---- ---- -----
         <span>`gl`</span>-${\texttt{BCGSI+LS}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         1.26e-01   0.00    2   20   22   82   24
     <span>`cl`</span>-${\texttt{BMGS}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>      1.19e-01   5.76    2   20   20   40   132
           <span>`gl`</span>-${\texttt{BMGS}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>           1.18e-01   6.88    2   20   20   40   132
         <span>`gl`</span>-${\texttt{BMGS-CWY}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         1.15e-01   9.35    2   20   22   62   24
   <span>`cl`</span>-${\texttt{BCGSI+LS}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    1.14e-01   9.92    2   20   22   82   24
        <span>`gl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         1.10e-01   13.06   2   20   22   62   24
   <span>`cl`</span>-${\texttt{BMGS-CWY}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    1.02e-01   19.32   2   20   22   62   24
         <span>`gl`</span>-${\texttt{BCGS-PIP}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         9.96e-02   21.14   2   20   20   60   22
   <span>`cl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>   9.77e-02   22.67   2   20   22   62   24
   <span>`cl`</span>-${\texttt{BCGS-PIP}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    8.55e-02   32.29   2   20   20   60   22
  --------------------------------------------------------------------------------------------------- ---------- ------- --- ---- ---- ---- -----

  : Results for `circuit_2` example. \[tab:circuit\_2\]

  --------------------------------------------------------------------------------------------------- ---------- ------- --- --- ---- ---- ----
         <span>`gl`</span>-${\texttt{BCGSI+LS}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         9.54e-02   0.00    1   9   10   37   11
        <span>`gl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         8.55e-02   10.41   1   9   10   28   11
         <span>`gl`</span>-${\texttt{BMGS-CWY}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         8.11e-02   14.96   1   9   10   28   11
           <span>`gl`</span>-${\texttt{BMGS}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>           7.67e-02   19.58   1   9   9    18   55
   <span>`cl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>   7.16e-02   24.91   1   8   9    25   10
     <span>`cl`</span>-${\texttt{BMGS}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>      6.91e-02   27.60   1   8   8    16   45
   <span>`cl`</span>-${\texttt{BCGSI+LS}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    6.66e-02   30.21   1   8   9    33   10
         <span>`gl`</span>-${\texttt{BCGS-PIP}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         6.09e-02   36.19   1   9   9    27   10
   <span>`cl`</span>-${\texttt{BMGS-CWY}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    5.26e-02   44.92   1   8   9    25   10
  --------------------------------------------------------------------------------------------------- ---------- ------- --- --- ---- ---- ----

  : Results for `rajat03` example. \[tab:rajat03\]

  --------------------------------------------------------------------------------------------------- ---------- ------- --- ---- ---- ----- -----
         <span>`gl`</span>-${\texttt{BCGSI+LS}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         7.24e-01   0.00    6   55   61   226   67
        <span>`gl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         6.65e-01   8.22    6   55   61   171   67
         <span>`gl`</span>-${\texttt{BMGS-CWY}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         6.61e-01   8.73    6   55   61   171   67
           <span>`gl`</span>-${\texttt{BMGS}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>           6.21e-01   14.21   6   55   55   110   351
         <span>`gl`</span>-${\texttt{BCGS-PIP}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         5.29e-01   26.93   6   55   55   165   61
     <span>`cl`</span>-${\texttt{BMGS}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>      2.36e-01   67.47   2   19   19   38    121
   <span>`cl`</span>-${\texttt{BCGSI+LS}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    2.02e-01   72.805-713-0782
   <span>`cl`</span>-${\texttt{BMGS-CWY}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    1.89e-01   73.95   2   19   21   59    23
   <span>`cl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>   1.86e-01   74.27   2   19   21   59    23
   <span>`cl`</span>-${\texttt{BCGS-PIP}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    1.60e-01   77.84   2   19   19   57    21
  --------------------------------------------------------------------------------------------------- ---------- ------- --- ---- ---- ----- -----

  : Results for `Kaufhold` example. \[tab:kaufhold\]

  --------------------------------------------------------------------------------------------------- ---------- ------- ---- ----- ----- ----- -----
         <span>`gl`</span>-${\texttt{BCGSI+LS}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         2.02e+00   0.00    15   144   159   591   174
     <span>`cl`</span>-${\texttt{BMGS}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>      1.86e+00   7.51    14   139   139   278   913
        <span>`gl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         1.84e+00   8.53    15   144   159   447   174
         <span>`gl`</span>-${\texttt{BMGS-CWY}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         1.84e+00   8.83    15   144   159   447   174
           <span>`gl`</span>-${\texttt{BMGS}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>           1.71e+00   15.17   15   144   144   288   939
   <span>`cl`</span>-${\texttt{BCGSI+LS}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    1.65e+00   18.09   14   139   153   570   167
   <span>`cl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>   1.54e+00   23.67   14   139   153   431   167
   <span>`cl`</span>-${\texttt{BMGS-CWY}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    1.49e+00   25.86   14   139   153   431   167
         <span>`gl`</span>-${\texttt{BCGS-PIP}\xspace}\circ{\texttt{gl}}$-<span>`GMRES`</span>         1.43e+00   28.92   15   144   144   432   159
   <span>`cl`</span>-${\texttt{BCGS-PIP}\xspace}\circ{\texttt{CholQR}\xspace}$-<span>`GMRES`</span>    1.26e+00   37.64   14   139   139   417   153
  --------------------------------------------------------------------------------------------------- ---------- ------- ---- ----- ----- ----- -----

  : Results for `t2d_q9` example. \[tab:t2d\_q9\]

  -------------------------------------------------------------------------------------------------- ---------- ------- ----- ------ ------ ------ -------
         <span>`gl`</span>-${\texttt{BCGSI+LS}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>         5.34e+01   0.00    47    1162   1209   4695   1256
        <span>`gl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>         4.60e+01   13.92   47    1162   1209   3533   1256
         <span>`gl`</span>-${\texttt{BMGS-CWY}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>         4.57e+01   14.41   47    1162   1209   3533   1256
   <span>`cl`</span>-${\texttt{BMGS-SVL}\xspace}\circ {\texttt{MGS-SVL}\xspace}$-<span>`FOM`</span>   4.39e+01   17.77   45    1121   1121   3363   34890
   <span>`cl`</span>-${\texttt{BMGS-LTS}\xspace}\circ {\texttt{MGS-LTS}\xspace}$-<span>`FOM`</span>   4.29e+01   19.63   45    1121   1121   3363   34890
         <span>`gl`</span>-${\texttt{BCGS-PIP}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>         4.07e+01   23.70   47    1162   1162   3486   1209
   <span>`cl`</span>-${\texttt{BCGSI+LS}\xspace}\circ {\texttt{CholQR}\xspace}$-<span>`FOM`</span>    4.06e+01   23.91   45    1121   1166   4529   1211
     <span>`cl`</span>-${\texttt{BMGS}\xspace}\circ {\texttt{CholQR}\xspace}$-<span>`FOM`</span>      3.97e+01   25.60   45    1121   1121   2242   15697
         <span>`gl`</span>-${\texttt{BMGS-SVL}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>         3.94e+01   26.21   47    1162   1162   3486   3533
           <span>`gl`</span>-${\texttt{BMGS}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>           3.89e+01   27.15   47    1162   1162   2324   16237
         <span>`gl`</span>-${\texttt{BMGS-LTS}\xspace}\circ {\texttt{gl}}$-<span>`FOM`</span>         3.88e+01   27.24   47    1162   1162   3486   3533
   <span>`cl`</span>-${\texttt{BMGS-CWY}\xspace}\circ {\texttt{CholQR}\xspace}$-<span>`FOM`</span>    3.72e+01   30.25   45    1121   1166   3408   1211
   <span>`cl`</span>-${\texttt{BMGS-ICWY}\xspace}\circ {\texttt{CholQR}\xspace}$-<span>`FOM`</span>   3.66e+01   31.44   45    1121   1166   3408   1211
   <span>`cl`</span>-${\texttt{BCGS-PIP}\xspace}\circ {\texttt{CholQR}\xspace}$-<span>`FOM`</span>    3.41e+01   36.12   181   2162   2162   6486   2343
  -------------------------------------------------------------------------------------------------- ---------- ------- ----- ------ ------ ------ -------

  : Results for <span>`lapl_2d`</span>example. \[tab:lapl\_2d\]

[^1]: <http://www.top500.org/news/ornls-frontier-first-to-break-the-exaflop-ceiling/>. Accessed 8 August 2022.

[^2]: <https://github.com/katlund/BlockStab>

[^3]: <https://gitlab.mpi-magdeburg.mpg.de/lund/low-sync-block-arnoldi>

[^4]: The term `matvec` is often used to refer to the multiplication of $A$ with a vector. Because we will be focusing on block vectors, we refrain from this term to avoid confusion.

[^5]: <https://mathworks.com/help/matlab/ref/maxnumcompthreads.html>. Accessed 8 August 2022.

[^6]: <https://www.intel.com/content/www/us/en/develop/documentation/onemkl-linux-developer-guide/top/obtaining-numerically-reproducible-results/reproducibility-conditions.html>. Accessed 8 August 2022.

[^7]: <https://www.mpi-magdeburg.mpg.de/cluster/mechthild>. Accessed 8 August 2022.

[^8]: Strictly speaking, they can use whatever muscle they are programmed to use, but <span>`BMGS-SVL`</span>requires <span>`MGS-SVL`</span>to be stable; see @Bar19 [@CarLRetal22].

{'source': 'arXiv_out/2208'}