Residual-Based Simpler Block GMRES for Nonsymmetric Linear Systems with Multiple Right-Hand Sides

Received Nov 16, 2017; Accepted Mar 12, 2018

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

In this paper, we consider iterative methods for solving a system of linear algebraic equations:$$\begin{array}{}\text{(1)}& AX=B,\end{array}$$where $A$ is a nonsingular matrix of order $n$ and $X=[x_{\mathrm{1}},\dots ,x_s]$ and $B=[b_{\mathrm{1}},\dots ,b_s]$ are rectangular matrices of dimension $n\times s$ with $s\le n$. For solving such systems, the block GMRES [1] and its variants are very popular. Block GMRES is based on the block Arnoldi process and is formally fully analogous to the ordinary GMRES algorithm by Saad and Schultz [2].

The following notation is used throughout the paper. Subscripts denote the iteration index and superscripts distinguish between individual columns in a block. We denote by $‖·‖$ the Euclidean vector norm and the induced matrix norm and by ${‖A‖}_F$ the Frobenius norm. Moreover, for $A\in {\mathbb{R}}^{N\times n}\hspace{0.17em}\hspace{0.17em}\left(N>n\right)$ of rank $n$, $\kappa (A)={\sigma }_{\mathrm{1}}(A)/{\sigma }_n(A)$ is the spectral condition number, where ${\sigma }_{\mathrm{1}}(A)>{\sigma }_n(A)>\mathrm{0}$ are the extremal singular values of $A$.

Given an initial approximation $X_{\mathrm{0}}\in {\mathbb{R}}^{n\times s}$ to the solution of (1), let$$\begin{array}{}\text{(2)}& R_{\mathrm{0}}=B-A{X}_{\mathrm{0}},\end{array}$$and then in analogy to the unblocked case, we build a sequence of iterates $X_m\in X_{\mathrm{0}}+K_m(A,R_{\mathrm{0}})$ such that$$\begin{array}{}\text{(3)}& {‖R_m‖}_F={‖B-A{X}_m‖}_F=\underset{\tilde{X}\in X_{\mathrm{0}}+K_m\left(A,R_{\mathrm{0}}\right)}{\min }{‖R_{\mathrm{0}}-A\tilde{X}‖}_F,\end{array}$$where $K_m(A,R_{\mathrm{0}})=\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}\{R_{\mathrm{0}},A{R}_{\mathrm{0}},\dots ,A^{m-\mathrm{1}}{R}_{\mathrm{0}}\}$. Equation (3) is equivalent to minimizing every...$$\begin{array}{c}\hspace{1em}\hspace{1em}\end{array}$$$$\begin{array}{}\hspace{1em}\end{array}$$

$\mathrm{\hspace{0.17em}\hspace{0.17em}}$

 

 

 

 

 

$$\begin{array}{}\left[\begin{array}{c}\hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\end{array}\right]\end{array}$$

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

$$\begin{array}{}\left[\begin{array}{c}\hspace{0.17em}\end{array}\right]\end{array}$$

$$\begin{array}{}\hspace{1em}\end{array}$$