On a fast deterministic block Kaczmarz method for solving large-scale linear systems

Abstract

For solving large-scale consistent systems of linear equations by iterative methods, a fast block Kaczmarz method based on a greedy criterion of the row selections is proposed. The method is deterministic and needs not compute the pseudoinverses of submatrices or solve subsystems. It is proved that the method will converge linearly to the unique least-norm solutions of the linear systems. Numerical experiments are given to illustrate that the method is more efficient and yields a significant acceleration in convergence for the tested data.

1 Introduction

We consider using block Kaczmarz-type methods to solve the large-scale consistent linear system in the following form

$$ Ax=b $$

(1.1)

with $A\in \mathbb {R}^{m\times n}$ and $b\in \mathbb {R}^{m}$, where each row of A is nonzero, and x is the n-dimensional unknown vector. Whenever the coefficient matrix A is overdetermined (i.e., m > n) or underdetermined (i.e., m < n), we are often interested in seeking the least-norm solution x_⋆.

Earlier researches on block Kaczmarz methods may date back at least to the work by Elfving [10] and the work by Eggermont et al. [9]. Differing from the Kaczmarz single-projection methods [2,3,4, 6, 12,13,14, 17, 24, 25], in general, multiple equations are used in the block Kaczmarz methods at each iteration. One kind of block Kaczmarz method selects a block of rows from the matrix A and computes the Moore-Penrose pseudoinverse of the block at each iteration. That is to say, starting from an initial guess x₀, a general format of the block Kaczmarz (BK) method can be formulated as

$$ x_{k+1} = x_{k} + A_{i_{k}}^{\dagger}(b_{i_{k}}-A_{i_{k}}x_{k}), \quad k\geq 0 $$

(1.2)

if the matrix A and the vector b are partitioned into $A=[{A_{1}^{T}}, {A_{2}^{T}},\ldots ,{A_{p}^{T}}]^{T}$ and $b=[{b_{1}^{T}}, {b_{2}^{T}},\ldots ,{b_{p}^{T}}]^{T}$, respectively, for a given integer 1 ≤ p ≤ m. In (1.2), (⋅)^‡ denotes the Moore-Penrose pseudoinverse of the corresponding matrix, and the block control sequence {i_k}_k≥ 0 is determined by i_k = (k mod p) + 1, k = 0,1,2,…. At the (k + 1)th iteration, the current iteration point x_k is projected onto the hyperplane corresponding to the solution set of $A_{i_{k}}x=b_{i_{k}}$. In the case when the coefficient matrix A is nonsingular, Bai and Liu [1] proved the convergence based on the block Meany inequality.

To improve the efficiency of block Kaczmarz methods, looking for appropriate pre-determined partitions of the row indices of the matrix A and block control sequences becomes the main goal of researches. Let $\mathcal {P}=\{\sigma _{1}, \sigma _{2}, \ldots , \sigma _{p}\}$, a partition of {1,2,…,m}, be a row paving of the matrix A. By choosing {τ_k}_k≥ 0 uniformly at random from $\mathcal {P}$, Needell and Tropp [18] proposed the randomized block Kaczmarz (RBK) method defined by

$$ x_{k+1} = x_{k} + A_{\tau_{k}}^{\dagger}(b_{\tau_{k}}-A_{\tau_{k}}x_{k}), \quad k\geq 0 $$

(1.3)

for solving linear least-squares problems. In this case, $A_{\tau _{k}}$ in (1.3) is the row submatrix of A indexed by τ_k, while $b_{\tau _{k}}$ is the subvector of b with component indices listed in τ_k. In [18], the authors also gave analysis of the expected linear rate of convergence of the RBK method. Based on the block control sequence {τ_k}_k≥ 0 determined by

$$\tau_{k}{}={}\left\{{}i\ {}\left|\ \left|b^{(i)}-A^{(i)}x_{k}\right|^{2} \geq \delta_{k}\underset{1\leq i\leq m}{\max}\left\{{}\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}{}\right\}{}\left\|A^{(i)}\right\|_{2}^{2},\ 1\leq i\leq m\right.{}\right\} $$

(1.4)

with δ_k ∈ (0,1], a pre-defined parameter for each k ≥ 0, Niu and Zheng [20] proposed the greedy block Kaczmarz (GBK) method. This method does not need to pre-determine a partition of the row indices of the matrix A. Clearly, (1.4) is modified from $\mathcal {U}_{k}$ defined by

$$ \mathcal{U}_{k}=\left\{i\ \left|\ |b^{(i)}-A^{(i)}x_{k}|^{2} \geq \epsilon_{k}\|b-Ax_{k}\|_{2}^{2}\|A^{(i)}\|_{2}^{2},\ 1\leq i\leq m\right.\right\} $$

(1.5)

with

$$ \epsilon_{k}=\frac{\theta}{\|b-Ax_{k}\|_{2}^{2}} \underset{1\leq i\leq m}{\max}\left\{\frac{|b^{(i)}-A^{(i)}x_k|^{2}}{\|A^{(i)}\|_{2}^{2}}\right\}+\frac{1-\theta}{\|A\|_{F}^{2}} $$

in the greedy randomized Kaczmarz (GRK) method ($\theta =\frac {1}{2}$) [3] and the relaxed greedy randomized Kaczmarz (RGRK) method (𝜃 ∈ [0,1]) [4]. Compared with the randomized Kaczmarz (RK) method [24], it is said in [3, 4] that the GRK and RGRK methods use a different but more effective probability criterion.

Recently, Necoara [16] proposed the randomized average block Kaczmarz (RaBK) method defined by

$$ x_{k+1}=x_{k}+\alpha_{k}\left( \underset{i\in \tau_{k}}{\sum}{\omega_{i}^{k}}\frac{b^{(i)}-A^{(i)}x_{k}}{\left\|A^{(i)}\right\|_{2}^{2}}\left( A^{(i)}\right)^{T}\right), \quad k\geq 0, $$

(1.6)

where ${\omega _{1}^{k}}, {\omega _{2}^{k}}, \ldots , \omega _{|\tau _{k}|}^{k}\in [0,1]$ are weights satisfying $\underset {i\in \tau _{k}}{\sum }{\omega _{i}^{k}}=1$ and α_k is the stepsize. Here, |τ_k| denotes the cardinality of the set τ_k. The RaBK method might be second kind of block Kaczmarz method. In (1.6), x_k+ 1 can be regarded as an average or a convex combination of the resulting projections of the Kaczmarz single-projection method applied to those rows whose indices appeared in τ_k. This kind of average block Kaczmarz methods can also be traced back to [5, 15, 22]. One can see for details in [5, 15, 16, 22] and the references therein. The RaBK method defined by (1.6) is named as a randomized method in [16], since the block control sequence {τ_k}_k≥ 0 is selected at random by two sampling methods from a pre-determined partition of the row indices of the coefficient matrix A. In [16], Necoara introduced different choices for the stepsize α_k and provided the analysis of the expected linear rate of convergence. These deterministic and randomized block Kaczmarz methods have also been extended to solve the inconsistent linear systems [8, 19, 23].

The Gaussian Kaczmarz (GK) method [11], defined by

$$ x_{k+1}=x_{k}+\frac{\eta^{T}(b-Ax_{k})}{\|A^{T}\eta\|_{2}^{2}}A^{T}\eta, \quad k\geq 0, $$

(1.7)

can be regarded as another kind of block Kaczmarz method that writes directly the increment in the form of a linear combination of all columns of A^T at each iteration, where η is a Gaussian vector with mean $0\in \mathbb {R}^{m}$ and the covariance matrix $I\in \mathbb {R}^{m\times m}$, i.e., $\eta \sim N(0,I)$. Here I denotes the identity matrix. In (1.7), all columns of A^T are used. The expected linear convergence rate was analyzed in [11] in the case that A is of full column rank.

In this paper, inspired by the GK method [11], and taking the block control sequence {τ_k}_k≥ 0 determined by

$$ \tau_k=\mathcal{U}_k,\quad k\geq 0, $$

where $\mathcal {U}_{k}$ is defined in (1.5), i.e., based on a greedy criterion of the row selections in [3, 4], we will propose a fast deterministic block Kaczmarz (FDBK) method. At (k + 1)th iteration, unlike the RK, GRK and RGRK methods [3, 4, 24] choosing one index, the FDBK method uses all indices belonging to $\mathcal {U}_{k}$. Unlike pre-partitioning the row indices of the coefficient matrix A in BK, RBK and RaBK methods [9, 10, 16, 18], in the FDBK method, the index set τ_k at each step is selected adaptively and is updated as iterations proceed. Even though this kind of choices of the index sets is similar to that used in the GBK method [20], unlike the GBK method using the Moore-Penrose pseudoinverse of the submatrix $A_{\tau _{k}}$, the FDBK method needs only to compute a linear combination of all columns of $A_{\tau _{k}}^{T}$. Unlike the GK method using the distribution generated by the pre-determined probability, the FDBK method uses the local residual distribution. The iterative format of the FDBK method can also be seen as the case when the RaBK method takes a specific stepsize and weight. Since the GRK method uses one index selected randomly from $\mathcal {U}_{k}$, while the FDBK method uses all indices in $\mathcal {U}_{k}$, in a sense, the FDBK method can be regarded as a deterministic block version of the GRK method with certain stepsize. In the extreme case where the set τ_k only contains a unique element for each k ≥ 0, the FDBK method, as well as the GRK and RGRK methods, becomes the maximum distance Kaczmarz (MDK) method [21].

In the following, we will prove that the FDBK method converges to the unique least-norm solution x_⋆ of the consistent linear system (1.1). Numerical experiments on frequently used examples will show that the FDBK method is more efficient than the GBK and the four special cases of the RaBK methods especially in terms of the CPU time.

The paper is organized as follows. In the rest of this section, we describe some notation that are used throughout this paper. In Section 2, we propose the fast deterministic block Kaczmarz method and discuss basic properties. In Section 3, we take the convergence analysis and derive the error estimates. Numerical results are reported in Section 4, and the paper is ended in Section 5 with a few conclusions.

For a matrix $M\in \mathbb {R}^{m\times n}$, we call M⁽ⁱ⁾, ∥M∥_F, M^T, M^‡ and ${\mathscr{R}}(M)$ the i throw, the Frobenius norm, the transpose, the Moore-Penrose pseudoinverse and the range space of the matrix M, respectively, and let $\lambda _{\min \limits }(M^{T}M)$ and $\lambda _{\max \limits }(M^{T}M)$ represent the smallest nonzero and the largest eigenvalue of the matrix M^TM. For a vector $u\in \mathbb {R}^{m}$, we use u⁽ⁱ⁾, u^T and ∥u∥₂ to denote its i th entry, the transpose and the Euclidean norm of the vector u, respectively. Let [m] represent the set {1,2,…,m}. For any index set υ, we use M_υ, u_υ and |υ| to denote the row submatrix of M indexed by υ, the subvector of u with component indices listed in υ and the cardinality of the set υ, respectively. Let I and e_i represent the identity matrix and the i th column of the identity matrix, respectively.

2 The fast deterministic block Kaczmarz method

The fast deterministic block Kaczmarz (FDBK) method for solving the consistent linear system (1.1) is defined as follows.

In this section, we want to discuss basic properties of the FDBK method. Let’s begin with the problem: Is the FDBK method executable unconditionally? In other words, does the iterative sequence {x_k}_k≥ 0 generated by the FDBK method exist for any initial guess x₀?

Property 1

The FDBK method described by Algorithm 1 is executable unconditionally.

Proof

For any $x_{0}\in \mathbb {R}^{n}$, ∥b − Ax₀∥₂ equals zero or not. When ∥b − Ax₀∥₂ = 0, the iterative sequence only contains x₀. When ∥b − Ax₀∥₂≠ 0, τ₀ is clearly nonempty. In this case, to show x₁ defined by (2.4) exists, what we need to do is to prove $\left \|A^{T}\eta _{0}\right \|_{2}\neq 0$ since only basic algebra operations of matrices are used. If $\left \|A^{T}\eta _{0}\right \|_{2} = 0$, or equivalently, A^Tη₀ = 0, then

$$ {\eta_{0}^{T}}(b-Ax_{0})=(A^{T}\eta_{0})^{T}(x_{\star}-x_{0})=0 $$

(2.5)

according to Ax_⋆ = b. However, by (2.1)–(2.3), we have

$$ {\eta_{0}^{T}}(b-Ax_{0}) =\underset{i\in \tau_{0}}{\sum}\left|b^{(i)}-A^{(i)}x_{0}\right|^{2} \geq \epsilon_{0}\left\|b-Ax_{0}\right\|_{2}^{2}\underset{i\in \tau_{0}}{\sum}\left\|A^{(i)}\right\|_{2}^{2} >0, $$

(2.6)

which is a contradiction to (2.5). Therefore, $\left \|A^{T}\eta _{0}\right \|_{2}\neq 0$ holds true, and accordingly x₁ can be computed via (2.4).

If x_k has been computed for some k ≥ 1, then repeat the above procedure by substituting η₀ and x₀ with η_k and x_k, respectively, we can find easily that the iterative sequence is {x₀,x₁,…,x_k} when ∥b − Ax_k∥₂ = 0, and that (2.5) and (2.6) remain true with η₀, x₀, τ₀ and 𝜖₀ replaced by η_k, x_k, τ_k and 𝜖_k in the case of ∥b − Ax_k∥₂≠ 0. Therefore, when ∥b − Ax_k∥₂≠ 0, the contradiction still happens. It follows that A^Tη_k≠ 0, which implies in the same way as described above that x_k+ 1 exists.

By the induction method, {x_k}_k≥ 0 exists for any initial point $x_{0}\in \mathbb {R}^{n}$.

This completes the proof. □

Property 2

We have η_k ⊥ b − Ax_k+ 1 for all k ≥ 0, where η_k is defined by (2.3).

Proof

In fact, for any k ≥ 0, according to the update rule (2.4), we have

$$ \begin{aligned} {\eta_{k}^{T}}\left( b-Ax_{k+1}\right)&= {\eta_{k}^{T}}\left( b-A\left( x_{k} + \frac{{\eta_{k}^{T}}(b-Ax_{k})}{\left\|A^{T}\eta_{k}\right\|_{2}^{2}}A^{T}\eta_{k}\right)\right)\\ &={\eta_{k}^{T}}\left( b-Ax_{k}\right)-\frac{{\eta_{k}^{T}}\left( b-Ax_{k}\right)}{\left\|A^{T}\eta_{k}\right\|_{2}^{2}}{\eta_{k}^{T}}AA^{T}\eta_{k}\\ &= {\eta_{k}^{T}}\left( b-Ax_{k}\right) - {\eta_{k}^{T}}\left( b-Ax_{k}\right)\\ &= 0, \end{aligned} $$

which completes the proof. □

Property 3

The format (2.4) can be written in the format of (1.6) with

$$ \alpha_{k}=\frac{\|\eta_{k}\|_{2}^{2}\|A_{\tau_{k}}\|_{F}^{2}}{\|A^{T}\eta_{k}\|_{2}^{2}},\ \ {\omega_{i}^{k}}=\frac{\|A^{(i)}\|_{2}^{2}}{\|A_{\tau_{k}}\|_{F}^{2}}, \ \ i\in\tau_{k}, \ \ k\geq 0. $$

(2.7)

Here, τ_k is defined by (2.2).

Proof

For each k ≥ 0, by the straightforward computations, the format (2.4) can be rewritten as:

$$ \begin{aligned} x_{k+1} &= x_{k} + \frac{{\eta_{k}^{T}}(b-Ax_{k})}{\|A^{T}\eta_{k}\|_{2}^{2}} \left( \underset{i\in \tau_{k}}{\sum}\left( b^{(i)}-A^{(i)}x_{k}\right)\left( A^{(i)}\right)^{T}\right)\\ &= x_{k} + \frac{\|\eta_{k}\|_{2}^{2}\|A_{\tau_{k}}\|_{F}^{2}}{\|A^{T}\eta_{k}\|_{2}^{2}} \left( \underset{i\in \tau_{k}}{\sum}\frac{\|A^{(i)}\|_{2}^{2}}{\|A_{\tau_{k}}\|_{F}^{2}}\frac{b^{(i)}-A^{(i)}x_{k}}{\|A^{(i)}\|_{2}^{2}}\left( A^{(i)}\right)^{T}\right), \end{aligned} $$

which is the format of (1.6). (2.7) follows. The proof is completed. □

3 Convergence analysis and error estimates of the FDBK method

In this section, we will devote ourselves to the proof of the following convergence theorem for the FDBK method.

Theorem 3.1

Let $A\in \mathbb {R}^{m\times n}$ be a matrix without any zero row, and $b\in \mathbb {R}^{m}$. The iteration sequence $\{x_{k}\}_{k=0}^{\infty }$, generated by the FDBK method starting from any initial guess $x_{0}\in {\mathscr{R}}(A^{T})$, exists and converges to the unique least-norm solution x_⋆ = A^‡b of the consistent linear system (1.1), with the error estimate

$$\left\|x_{k+1}-x_{\star}\right\|_{2}^{2} \leq \left( 1-\gamma_{k}\frac{\left\|A_{\tau_{k}}\right\|_{F}^{2}}{\lambda_{\max}\left( A_{\tau_{k}}A_{\tau_{k}}^{T}\right)}\frac{\lambda_{\min}\left( A^{T}A\right)}{\|A\|_{F}^{2}}\right)\left\| x_{k}-x_{\star} \right\|_{2}^{2}, \quad k\geq 0, $$

(3.1)

where

$$ \gamma_{k} = \displaystyle\frac{1}{2}\left( \frac{\|A\|_{F}^{2}}{q_{k}\left\|A_{\zeta_{k}}\right\|_{F}^{2} + (1-q_{k})\left\|A_{\tau_{k}}\right\|_{F}^{2}} + 1\right) \geq 1, \quad k\geq 0, $$

(3.2)

with

$$ \zeta_{k} = \left\{i \ \left| \ b^{(i)}-A^{(i)}x_{k} \neq 0, \ i\in [m]\right.\right\}, \quad k\geq 0, $$

(3.3)

and

$$ q_{k} = \left\{ \begin{array}{ll} \frac{\underset{i\in \zeta_{k} \backslash \tau_{k}}{\max}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\}}{\underset{1\leq i\leq m}{\max}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\}} < 1, & \text{ if } \tau_{k}\neq [m] \text{ and } \zeta_{k}\neq\tau_{k},\\ 1, & \text{ otherwise}, \end{array} \quad k \geq 0. \right. $$

(3.4)

Here the equality in (3.2) holds only when τ_k = [m] for each k ≥ 0.

Proof

The iteration sequence $\{x_{k}\}_{k=0}^{\infty }$ exists and is contained in ${\mathscr{R}}(A^{T})$ for any initial guess $x_{0}\in {\mathscr{R}}(A^{T})$ via Property 1 and (2.4), respectively. {x_k}_k≥ 0 might be a sequence containing finite members once ∥b − Ax_k∥₂ = 0 happens for some $0\leq k< +\infty$, or a sequence containing infinite members once ∥b − Ax_k∥₂≠ 0 happens for each k ≥ 0. Without loss of generality, in the following, it is often assumed that ∥b − Ax_k∥₂≠ 0 is true for each k ≥ 0.

For each k ≥ 0, P_k, defined by $P_{k} = \frac {A^{T}\eta _{k}{\eta _{k}^{T}}A}{\|A^{T}\eta _{k}\|_{2}^{2}}$, exists by Property 1. Then for the least-norm solution x_⋆ of the consistent linear system (1.1), according to the iterative format (2.4) of the FDBK method, we have

$$ \begin{aligned} x_{k+1}-x_{\star} &= x_{k}-x_{\star} + \frac{{\eta_{k}^{T}}(b-Ax_{k})}{\left\|A^{T}\eta_{k}\right\|_{2}^{2}} A^{T}\eta_{k}\\ &= x_{k}-x_{\star} - \frac{{\eta_{k}^{T}}A\left( x_{k}- x_{\star}\right)}{\left\|A^{T}\eta_{k}\right\|_{2}^{2}} A^{T}\eta_{k}\\ &= x_{k}-x_{\star} - \frac{A^{T}\eta_{k}{\eta_{k}^{T}}A}{\|A^{T}\eta_{k}\|_{2}^{2}} \left( x_{k}-x_{\star}\right)\\ &= (I-P_{k})\left( x_{k}-x_{\star}\right). \end{aligned} $$

Since ${P_{k}^{T}}=P_{k}$ and ${P_{k}^{2}}=P_{k}$, P_k is an orthogonal projector. It follows that

$$ \begin{aligned} \left\|x_{k+1}-x_{\star}\right\|_{2}^{2} &= \left\|(I-P_{k})\left( x_{k}-x_{\star}\right)\right\|_{2}^{2}\\ &= \left\|x_{k}-x_{\star}\right\|_{2}^{2} - \left\|P_{k}\left( x_{k}-x_{\star}\right)\right\|_{2}^{2}\\ &= \left\|x_{k}-x_{\star}\right\|_{2}^{2} - \left\|\frac{{\eta_{k}^{T}}A\left( x_{k}-x_{\star}\right)}{\|A^{T}\eta_{k}\|_{2}^{2}}A^{T}\eta_{k}\right\|_{2}^{2}\\ &= \left\|x_{k}-x_{\star}\right\|_{2}^{2} - \frac{\left|{\eta_{k}^{T}}(b-Ax_{k})\right|^{2}}{\left\|A^{T}\eta_{k}\right\|_{2}^{2}} \end{aligned} $$

(3.5)

by the Pythagorean Theorem.

Let $E_{k}\in \mathbb {R}^{m\times \left |\tau _{k}\right |}$ denote the matrix whose columns in turn are composed of all the vectors $e_{i}\in \mathbb {R}^{m}$ with i ∈ τ_k, then, $A_{\tau _{k}}={E_{k}^{T}}A$. Denote by $\widehat {\eta }_{k} = {E_{k}^{T}}\eta _{k}$, we have

$$ \left\|\widehat{\eta}_{k}\right\|_{2}^{2} = {\eta_{k}^{T}}E_{k}{E_{k}^{T}}\eta_{k} = \|\eta_{k}\|_{2}^{2} = \underset{i\in \tau_{k}}{\sum}\left|b^{(i)}-A^{(i)}x_{k}\right|^{2} $$

(3.6)

and

$$ \left\|A^{T}\eta_{k} \right\|_{2}^{2} = {\eta_{k}^{T}}AA^{T}\eta_{k} = \widehat{\eta}_{k}^{T}{E_{k}^{T}}AA^{T}E_{k}\widehat{\eta}_{k} = \widehat{\eta}_{k}^{T}A_{\tau_{k}}A_{\tau_{k}}^{T}\widehat{\eta}_{k} = \left\|A_{\tau_{k}}^{T}\widehat{\eta}_{k}\right\|_{2}^{2}. $$

(3.7)

Therefore, we can obtain

$$ \left\|A_{\tau_{k}}^{T}\widehat{\eta}_{k}\right\|_{2}^{2} = \widehat{\eta}_{k}^{T}A_{\tau_{k}}A_{\tau_{k}}^{T}\widehat{\eta}_{k} \leq \lambda_{\max}\left( A_{\tau_{k}}A_{\tau_{k}}^{T}\right)\left\|\widehat{\eta}_{k}\right\|_{2}^{2}. $$

(3.8)

From the definition of η_k in (2.3), we have, by (3.6), that

$$ \begin{aligned} {\eta_{k}^{T}}(b-Ax_{k}) &= \left( \underset{i\in \tau_{k}}{\sum}\left( b^{(i)}-A^{(i)}x_{k}\right){e_{i}^{T}}\right)(b-Ax_{k})\\ &= \underset{i\in \tau_{k}}{\sum}\left( \left( b^{(i)}-A^{(i)}x_{k}\right){e_{i}^{T}}(b-Ax_{k})\right)\\ &= \underset{i\in \tau_{k}}{\sum}\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}\\ &= \left\|\widehat{\eta}_{k}\right\|_{2}^{2}. \end{aligned} $$

(3.9)

Since $x_{k}, x_{\star }\in {\mathscr{R}}(A^{T})$ implies $x_{k}-x_{\star }\in {\mathscr{R}}(A^{T})$, we can obtain

$$ \|b-Ax_{k}\|_{2}^{2} = \left\|A\left( x_{k}-x_{\star}\right)\right\|_{2}^{2} \geq \lambda_{\min}\left( A^{T}A\right)\left\|x_{k}-x_{\star}\right\|_{2}^{2} $$

(3.10)

by the following well-known inequality

$$ \|Au\|_{2}^{2}\geq \lambda_{\min}\left( A^{T}A\right)\|u\|_{2}^{2},\ \ \forall u\in \mathscr{R}\left( A^{T}\right). $$

It then holds that

$$ \begin{aligned} \frac{\left|{\eta_{k}^{T}}(b-Ax_{k})\right|^{2}}{\left\|A^{T}\eta_{k}\right\|_{2}^{2}} &= \frac{\left( \underset{i\in \tau_{k}}{\sum}\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}\right)\left\|\widehat{\eta}_{k}\right\|_{2}^{2}}{\left\|A_{\tau_{k}}^{T}\widehat{\eta}_{k} \right\|_{2}^{2}}\\ &\geq \frac{\underset{i\in \tau_{k}}{\sum}\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\lambda_{\max}\left( A_{\tau_{k}}A_{\tau_{k}}^{T}\right)}\\ &\geq \frac{\underset{i\in \tau_{k}}{\sum}\left( \epsilon_{k}\|b-Ax_{k}\|_{2}^{2} \left\|A^{(i)} \right\|_{2}^{2}\right)}{\lambda_{\max}\left( A_{\tau_{k}}A_{\tau_{k}}^{T}\right)}\\ &= \frac{\epsilon_{k}\|b-Ax_{k}\|_{2}^{2}\underset{i\in \tau_{k}}{\sum}\left\|A^{(i)}\right\|_{2}^{2}}{\lambda_{\max}\left( A_{\tau_{k}}A_{\tau_{k}}^{T}\right)}\\&\geq \frac{\epsilon_{k} \left\|A_{\tau_{k}}\right\|_{F}^{2} \lambda_{\min}\left( A^{T}A\right)}{\lambda_{\max}\left( A_{\tau_{k}}A_{\tau_{k}}^{T}\right)}\left\|x_{k}-x_{\star}\right\|_{2}^{2} \end{aligned} $$

(3.11)

by (3.7)–(3.10) and the definition of τ_k in (2.2).

For each k ≥ 0, since

$$ \frac{\|b-Ax_{k}\|_{2}^{2}}{\|A\|_{F}^{2}} = \sum \limits_{i=1}^{m} \frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\frac{\left\|A^{(i)}\right\|_{2}^{2}}{\|A\|_{F}^{2}} \leq \underset{1\leq i\leq m}{\max}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\}, $$

by the definition of 𝜖_k in (2.1), we have

$$ \epsilon_{k}\|b-Ax_{k}\|_{2}^{2} = \frac{1}{2}\underset{1\leq i\leq m}{\max}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\} + \frac{1}{2}\frac{\|b-Ax_{k}\|_{2}^{2}}{\|A\|_{F}^{2}} \leq \underset{1\leq i\leq m}{\max}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\}, $$

which implies via (2.2) that l ∈ τ_k, i.e., τ_k≠∅, when

$$ \frac{\left|b^{(l)}-A^{(l)}x_{k}\right|^{2}}{\left\|A^{(l)}\right\|_{2}^{2}}=\underset{1\leq i\leq m}{\max}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\}. $$

In the case of τ_k≠[m] and ζ_k≠τ_k, where ζ_k is defined by (3.3), q_k, defined by (3.4), is a positive number less than 1, i.e., 0 < q_k < 1. According to the definition of γ_k in (3.2), we have

$$ \gamma_{k} = \displaystyle\frac{1}{2}\left( \frac{\|A\|_{F}^{2}}{q_{k}\left\|A_{\zeta_{k}}\right\|_{F}^{2} + (1-q_{k})\left\|A_{\tau_{k}}\right\|_{F}^{2}} + 1\right) > \displaystyle\frac{1}{2}\left( \frac{\|A\|_{F}^{2}}{\left\|A_{\zeta_{k}}\right\|_{F}^{2}} + 1\right) \geq 1. $$

(3.12)

Since i∉τ_k and i ∈ ζ_k if and only if i ∈ ζ_k∖τ_k, it follows that

$$ \begin{aligned} \|b-Ax_{k}\|_{2}^{2} &= \sum\limits_{i\in\tau_{k}} \frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}} \left\|A^{(i)}\right\|_{2}^{2} + \! \! \! \underset{i\in\zeta_{k}\backslash \tau_{k}}{\sum} \frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}} \left\|A^{(i)}\right\|_{2}^{2}\\ &\leq \underset{1\leq i\leq m}{\max}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\} \!\! \left( \sum\limits_{i\in\tau_{k}}\left\|A^{(i)}\right\|_{2}^{2} \! \right) \\&\quad+ \! \max \limits_{i\in\zeta_{k}\backslash \tau_{k}}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\} \!\! \left( \underset{i\in\zeta_{k}\backslash \tau_{k}}{\sum} \!\! \left\|A^{(i)}\right\|_{2}^{2} \! \right)\\ &= \underset{1\leq i\leq m}{\max}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\} \! \! \left( \sum\limits_{i\in\tau_{k}}\left\|A^{(i)}\right\|_{2}^{2} + q_{k} \!\! \underset{i\in\zeta_{k}\backslash \tau_{k}}{\sum} \!\! \left\|A^{(i)}\right\|_{2}^{2}\right)\\ &= \underset{1\leq i\leq m}{\max}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\} \! \left( q_{k}\left\|A_{\zeta_{k}}\right\|_{F}^{2} + (1-q_{k})\left\|A_{\tau_{k}}\right\|_{F}^{2}\right), \end{aligned} $$

where the last equality holds due to

$$\underset{i\in\zeta_{k}\backslash \tau_{k}}{\sum}\left\|A^{(i)}\right\|_{2}^{2} = \left\|A_{\zeta_{k}}\right\|_{F}^{2}-\left\|A_{\tau_{k}}\right\|_{F}^{2}.$$

Thus, we have

$$ \begin{aligned} \epsilon_{k}\|A\|_{F}^{2} &= \frac{1}{2}\left( \frac{\|A\|_{F}^{2}}{\left\|b-Ax_{k}\right\|_{2}^{2}}\underset{1\leq i\leq m}{\max}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\} + 1\right)\\ &\geq \frac{1}{2}\left( \frac{\|A\|_{F}^{2}}{q_{k}\left\|A_{\zeta_{k}}\right\|_{F}^{2} + (1-q_{k})\left\|A_{\tau_{k}}\right\|_{F}^{2}} + 1\right)\\ &= \gamma_{k}. \end{aligned} $$

(3.13)

In the case of τ_k≠[m] and ζ_k = τ_k, i.e., $\zeta _{k}=\tau _{k}\subsetneqq [m]$, it holds that

$$ \|b-Ax_{k}\|_{2}^{2} = \sum\limits_{i\in\zeta_{k}} \frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}} \left\|A^{(i)}\right\|_{2}^{2} \leq \underset{1\leq i\leq m}{\max}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\}\left\|A_{\zeta_{k}}\right\|_{F}^{2} $$

and that

$$ \epsilon_{k}\|A\|_{F}^{2} \geq \frac{1}{2}\left( \frac{\|A\|_{F}^{2}}{\left\|A_{\zeta_{k}}\right\|_{F}^{2}} + 1\right) = \gamma_{k} > 1. $$

(3.14)

In the case of τ_k = [m], it should be that

$$ \frac{\left|b^{(1)}-A^{(1)}x_{k}\right|^{2}}{\left\|A^{(1)}\right\|_{2}^{2}} = \frac{\left|b^{(2)}-A^{(2)}x_{k}\right|^{2}}{\left\|A^{(2)}\right\|_{2}^{2}} = {\cdots} = \frac{\left|b^{(m)}-A^{(m)}x_{k}\right|^{2}}{\left\|A^{(m)}\right\|_{2}^{2}}, $$

i.e., ζ_k = τ_k = [m]. Therefore,

$$ \underset{1\leq i\leq m}{\max}\left\{\frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\left\|A^{(i)}\right\|_{2}^{2}}\right\} = \frac{\|b-Ax_{k}\|_{2}^{2}}{\|A\|_{F}^{2}}. $$

Thanks to the definition of 𝜖_k and γ_k in (2.1) and (3.2), respectively, we can obtain

$$ \epsilon_{k}\|A\|_{F}^{2} = \gamma_{k} = 1. $$

(3.15)

Inequalities in (3.12)–(3.15) imply that

$$ \epsilon_{k}\geq \frac{1}{\|A\|_{F}^{2}}\gamma_{k}, $$

(3.16)

and that (3.2) is true and the equality in it holds only when τ_k = [m].

For any nonzero vector $\widehat {y}\in \mathbb {R}^{|\tau _{k}|}$, we have

$$\lambda_{\min}(A^{T}\!A) = \lambda_{\min}(AA^{T})\!\leq\! \frac{(E_{k}\widehat{y})^{T}\!AA^{T}\!(E_{k}\widehat{y})}{(E_{k}\widehat{y})^{T}(E_{k}\widehat{y})} = \frac{\widehat{y}^{T}\!A_{\tau_{k}}A_{\tau_{k}}^{T}\widehat{y}}{\widehat{y}^{T}\widehat{y}}\!\leq\! \lambda_{\max}(A_{\tau_{k}}A_{\tau_{k}}^{T}). $$

(3.17)

Moreover, by (2.2) and (3.16), we have

$$ \gamma_{k}\frac{\left\|A_{\tau_{k}}\right\|_{F}^{2}}{\|A\|_{F}^{2}} \leq \epsilon_{k}\left\|A_{\tau_{k}}\right\|_{F}^{2} = \underset{i\in \tau_{k}}{\sum} \epsilon_{k} \|A^{(i)}\|_{2}^{2} \leq \underset{i\in \tau_{k}}{\sum} \frac{\left|b^{(i)}-A^{(i)}x_{k}\right|^{2}}{\|b-Ax_{k}\|_{2}^{2}} \leq 1. $$

(3.18)

Since it is always true that

$$ 0<\frac{\lambda_{\min}\left( A^TA\right)}{\|A\|_F^2}\leq 1, \quad \frac{\left\|A_{\tau_k}\right\|_F^2}{\lambda_{\max}\left( A_{\tau_k}A_{\tau_k}^T\right)}\geq 1, $$

it follows from (3.17) and (3.18) that

$$ \begin{array}{@{}rcl@{}} 0&\leq& 1 - \gamma_{k}\frac{\left\|A_{\tau_{k}}\right\|_{F}^{2}}{\|A\|_{F}^{2}}\frac{\lambda_{\min}\left( A^{T}A\right)}{\lambda_{\max}\left( A_{\tau_{k}}A_{\tau_{k}}^{T}\right)} = 1 - \gamma_{k}\frac{\left\|A_{\tau_{k}}\right\|_{F}^{2}}{\lambda_{\max}\left( A_{\tau_{k}}A_{\tau_{k}}^{T}\right)}\frac{\lambda_{\min}\left( A^{T}A\right)}{\|A\|_{F}^{2}} \\&\leq& 1-\frac{\lambda_{\min}\left( A^{T}A\right)}{\|A\|_{F}^{2}}< 1. \end{array} $$

(3.19)

Now, to complete the proof, what we need to do is to prove the convergence of the sequence {x_k}_k≥ 0.

It follows from (3.5), (3.11) and (3.16) that

$$\left\|x_{k+1}-x_{\star}\right\|_{2}^{2}\leq \left( 1-\gamma_{k}\frac{\left\|A_{\tau_{k}}\right\|_{F}^{2}}{\lambda_{\max}\left( A_{\tau_{k}}A_{\tau_{k}}^{T}\right)}\frac{\lambda_{\min}\left( A^{T}A\right)}{\|A\|_{F}^{2}}\right)\left\|x_{k}-x_{\star}\right\|_{2}^{2}, \quad k\geq 0, $$

(3.20)

i.e., (3.1) holds. By (3.19) and (3.20), we can get

$$ \left\|x_{k+1}-x_{\star}\right\|_2^2\leq \left( 1-\frac{\lambda_{\min}\left( A^TA\right)}{\|A\|_F^2}\right)\left\|x_k-x_{\star}\right\|_2^2, \quad k\geq 0, $$

which deduces

$$ \left\|x_{k+1}-x_{\star}\right\|_{2}^{2}\leq \left( 1-\frac{\lambda_{\min}\left( A^{T}A\right)}{\|A\|_{F}^{2}}\right)^{k+1}\|x_{0}-x_{\star}\|_{2}^{2}, \quad k\geq 0 $$

(3.21)

via the mathematical induction method. Here, $1-\frac {\lambda _{\min \limits }\left (A^{T}A\right )}{\|A\|_{F}^{2}}$ is a nonnegative number less than 1 by (3.19). (3.21) shows us that the sequence {x_k}_k≥ 0 converges to x_⋆ as $k\to \infty$. □

4 Experimental results

In this section, we will make numerical experiments on consistent linear systems with three types of matrices for comparing the fast deterministic block Kaczmarz (FDBK) method with the following methods:

• RaBK: the randomized average block Kaczmarz method [16];

• GBK: the greedy block Kaczmarz method [20].

For the RaBK method, we consider four cases appeared in [16], and use the same sampling methods and choices of blocks, stepsizes and weights. The details are listed below.

The meanings of the partition sampling, L_k and $\lambda _{\max \limits }^{\text {block}}$ in Table 1 are described in the following.

• The partition sampling means that τ_k used is selected randomly from the row partition $\mathcal {P}_{s} = \{\sigma _{1}, \sigma _{2}, \ldots , \sigma _{s}\}$ at (k + 1)th iteration, where $s=\left \lceil \|A\|_{2}^{2}\right \rceil$, and

  $$ \sigma_{i}=\left\{\left\lfloor (i-1)\frac{m}{s} \right\rfloor+1, \left\lfloor (i-1)\frac{m}{s} \right\rfloor+2, \ldots, \left\lfloor i\frac{m}{s} \right\rfloor\right\},\quad i=1, 2, \ldots, s. $$

• $L_{k}=\left .\underset {i\in \tau _{k}}{\sum }\left .{\omega _{i}^{k}} \left (A^{(i)}x_{k}-b^{(i)}\right )^{2} \right / \left \|\underset {i\in \tau _{k}}{\sum }{\omega _{i}^{k}} \left (A^{(i)}x_{k}-b^{(i)}\right ) (A^{(i)})^{T} \right \|_{2}^{2}\right .$.

• $\lambda _{\max \limits }^{\text {block}} = \max \limits \limits _{\tau _{k}\in \mathcal {P}}\lambda _{\max \limits }(A_{\tau _{k}}^{T}A_{\tau _{k}})$, where $\mathcal {P}_{s}$ is the partition defined above.

Table 1 The sampling methods and parameters of four cases of the RaBK method in [16]

For the GBK method, we take the parameter δ_k in (1.4) as the same value as that used in [20] and also use the CGLS algorithm instead of calculating the Moore-Penrose inverse $A_{\tau _{k}}^{\dagger }$ at each iteration. The details are described as follows. For each k ≥ 0,

• • $\delta _{k}=\frac {1}{2}+\frac {1}{2}\frac {\|b-Ax_{k}\|_{2}^{2}}{\|A\|_{F}^{2}}\left (\underset {1\leq i\leq m}{\max \limits }\left \{\frac {\left |b^{(i)}-A^{(i)}x_{k}\right |^{2}}{\left \|A^{(i)}\right \|_{2}^{2}}\right \}\right )^{-1}$,

  • the stopping criterion of the CGLS algorithm is taken as 10^− 4.

The stopping criterion used for the CGLS algorithm is an appropriate error criterion to ensure that the GBK method can be carried out. In fact, on the one hand, the CPU time of the GBK method will increase with the decrease of the stopping criterion of the CGLS algorithm, and on the other hand, when the stopping criterion of the CGLS algorithm is taken as 10^− 3, the GBK method cannot converge for the overdetermined matrix generated by using the MATLAB function randn(1000,800) and used in the numerical experiments.

Three types of coefficient matrices of the consistent linear systems used in the numerical experiments are

• forty dense and well-conditioned matrices, generated by using the MATLAB function randn;

• twenty full-rank sparse matrices, selected from the SuiteSparse Matrix Collection (formerly known as the University of Florida Sparse Matrix Collection) [7];

• six rank-deficient sparse matrices, selected from the SuiteSparse Matrix Collection [7].

Thus, the dense matrices used are generated randomly, while two kinds of sparse matrices used are of deterministic.

In the numerical experiments, all zero rows, which might be appeared in four matrices, will be removed, and the lengths of all nonzero rows in each matrix are normalized to 1.

In our implementations, to ensure that each linear system (1.1) with the selected matrix A is consistent, a vector $y\in \mathbb {R}^{n}$ with its entries randomly generated by the MATLAB function randn is formed at first, and $b\in \mathbb {R}^{m}$, the right-hand-side of the linear system (1.1) is then set to be b = Ay.

For all methods, the iterations are started from x₀ = 0, and terminated once the relative solution error (RSE) satisfies

$$ \text{RSE} = \frac{\left\|x_k - x_{\star}\right\|_2^2}{\left\|x_{\star}\right\|_2^2} < 10^{-6}, $$

or the number of iteration steps exceeds 200000.

All numerical experiments are implemented in MATLAB (version R2019b) and executed on an Intel(R) Core(TM) i5-10210U CPU 1.60GHz computer with 12 GB of RAM and Windows 10 operating system.

We report the performance of the methods in terms of the number of iteration steps (denoted by “IT”) and the CPU time in seconds (denoted by “CPU”) in Tables 2, 3, 4, 5, 6, 7, and 8, where each “IT” and “CPU” of the randomized methods are the arithmetic mean of the results obtained by repeatedly running the corresponding method 50 times.

Table 2 Numerical results corresponding to the dense matrices A of Type I with m > n

Table 3 Numerical results corresponding to the dense matrices A of Type I with m > n

Table 4 Numerical results corresponding to the dense matrices A of Type I with m < n

Table 5 Numerical results corresponding to the dense matrices A of Type I with m < n

Table 6 Numerical results corresponding to the full-rank sparse matrices A of Type II with m ≥ n

Table 7 Numerical results corresponding to the full-rank sparse matrices A of Type II with m < n

Table 8 Numerical results corresponding to the rank-deficient matrices A of Type III

In the following tables, the item “> 200000” represents that the number of iteration steps exceeds 200000. In this case, the corresponding CPU time is expressed as “−−”.

To compare the degree of convergence speeds, the speed-up of the FDBK method against the other one, defined by

$$ \text{speed-up\_Method} = \frac{\text{CPU of Method}}{\text{CPU of FDBK}}, $$

is also reported. Clearly, the greater the “speed-up_Method” is than 1, the faster the convergence speed of the FDBK method against the corresponding “Method” is.

Dense and well-conditioned matrices

Numerical results corresponding to these forty matrices of Type I are listed in Tables 2, 3, 4, and 5, where Tables 2 and 3 stands for the case of thin (or tall) matrices while Tables 4 and 5 for the case of fat matrices. The numbers of columns of the matrices used in Tables 2 and 3 are fixed with 100, 150, 500 and 800, respectively, and the numbers of rows of the matrices used in Tables 4 and 5 are fixed with 100, 150, 500 and 800, respectively.

From Tables 2, 3, 4, and 5, we can observe the following phenomena:

• FDBK versus GBK: These two methods use the same criterion to construct the block at each iteration. Since the linear combination of columns of $A_{\tau _{k}}^{T}$ is used directly in the FDBK method, the decrease of the norm of the residual of the FDBK method might be not greater than that of the GBK method at each iteration, and the number of the iteration steps would be greater than that of the GBK method. But the decrement of the number of floating-point operations leads the FDBK method to have a faster convergence and own less CPU time. More specifically, the speed-up of the FDBK method against the GBK method is distributed from 1.17 to 6.20.

• FDBK versus RaBK: Compared with the four special cases of the RaBK method, data in tables shows us that the FDBK method has great advantages in terms of the CPU time in all cases and the number of iteration steps in most cases. In detail, for the matrices of 1000 × 500, 2000 × 500, 3000 × 500, 2000 × 800, 3000 × 800, 4000 × 800, 5000 × 800, 500 × 1000, 500 × 2000, 800 × 2000, 800 × 3000 and 800 × 5000, the RaBK-e-paved method owns the least number of iteration steps, and for the matrices of 1000 × 800 and 800 × 1000, the RaBK-a-paved method owns the least number of iteration steps. In these tables, the speed-up of the FDBK method against the RaBK-c method is distributed from 2.33 to 82.29, the speed-up of the FDBK method against the RaBK-a method is distributed from 2.57 to 107.49, the speed-up of the FDBK method against the RaBK-e-paved method is distributed from 2.99 to 1434.74, and the speed-up of the FDBK method against the RaBK-a-paved method is distributed from 2.40 to 121.86. Therefore, the submatrices, stepsizes and weights chosen in the FDBK method are much effective.

Full-rank sparse matrices selected from [7]

There are five thin (or tall) matrices, five square matrices, and ten fat matrices, which originate in different applications such as linear programming problem, combinatorial problem, least-squares problem, directed weighted graph, weighted bipartite graph and undirected weighted graph [7]. These twenty matrices of Type II are determined uniquely.

Numerical results corresponding to these matrices of Type II are listed in Tables 6 and 7, where “density”, the sparsity of these matrices, is computed as usual via the following format:

$$ \text{density} = \frac{\text{number of nonzeros of an } m\times n \text{ matrix}}{m\times n}, $$

and “cond(A)”, the Euclidean condition number of A, is computed by using the matlab function cond.

Since the matrix WorldCities has zero rows, in the numerical experiments, we removed these zero rows from the matrix. Clearly, this operation does not influence the solution of the corresponding linear system.

From Tables 6 and 7, we can see that the phenomena here are similar to those observed from Tables 2, 3, 4, and 5:

• FDBK versus GBK: The FDBK method performs better than the GBK method especially in terms of the CPU time, although the number of the iteration steps of the GBK method is less than that of the FDBK method. Moreover, the speed-up of the FDBK method against the GBK method is distributed from 1.48 to 15.12.

• FDBK versus RaBK: Compared with the four special cases of the RaBK method, data in tables shows us that the FDBK method has great advantages in terms of the CPU time in all cases and the number of iteration steps except the case when the matrix is model1. In detail, for the matrix of model1, the RaBK-e-paved method owns the least number of iteration steps. For the matrices of Cities and Stranke94, the RaBK-e-paved and RaBK-a-paved methods failed due to the number of the iteration steps exceeding 200000. Specifically, the speed-up of the FDBK method against the RaBK-c method is distributed from 3.25 to 173.83, and the speed-up of the FDBK method against the RaBK-a method is distributed from 1.87 to 75.25. When the numbers of iteration steps do not exceed 200000, the speed-up of the FDBK method against the RaBK-e-paved method is distributed from 3.82 to 20374.32, and the speed-up of the FDBK method against the RaBK-a-paved method is distributed from 2.18 to 57.28.

Rank-deficient sparse matrices selected from [7]

The matrices used here, originated in different applications such as combinatorial problem, undirected weighted graph, directed graph and bipartite graph [7], include a thin (or tall) matrix, two square matrices and three fat matrices. As is in the previous part, these six matrices of Type III are determined uniquely.

Numerical results corresponding to these matrices of Type III are listed in Table 8, where “density” and “cond(A)” are computed via the method in the previous part.

Since the matrices relat6, GD00_a and GL7d26 have zero rows, respectively, we removed these zero rows from the matrices in the numerical experiments in the same reason described in the previous part.

From Table 8, we can also observe the similar phenomena to those observed from Tables 2, 3, 4, 5, 6, and 7:

• FDBK versus GBK: The FDBK method performs better than the GBK method especially in terms of the CPU time, although the number of the iteration steps of the FDBK method is greater than that of the GBK method. Moreover, the speed-up of the FDBK method against the GBK method is distributed from 1.45 to 2.51.

• FDBK versus RaBK: The FDBK method outperforms the four special cases of the RaBK method in terms of both the number of iteration steps and the CPU time. Specifically, in the table, the speed-up of the FDBK method against the RaBK-c method is distributed from 5.92 to 56.55, the speed-up of the FDBK method against the RaBK-a method is distributed from 1.52 to 31.80, the speed-up of the FDBK method against the RaBK-e-paved method is distributed from 5.02 to 44.69, and the speed-up of the FDBK method against the RaBK-a-paved method is distributed from 3.07 to 19.79.

All in all, data in Tables 2, 3, 4, 5, 6, 7, and 8 illustrates that the CPU time of the FDBK method is less than those of other tested methods, i.e., the FDBK method performs more efficiently than other tested methods especially in terms of the CPU time.

5 Conclusions

In this paper, we propose the fast deterministic block Kaczmarz (FDBK) method for solving large-scale consistent linear systems. It is proved that the FDBK method converges to the least-norm solutions of the linear systems whether they are overdetermined or underdetermined. Numerical results illustrate that the FDBK method provides significant computational advantages and is more efficient, which means that the FDBK method is a competitive block Kaczmarz-type method for consistent linear system.