A Projection Hestenes–Stiefel Method with Spectral Parameter for Nonlinear Monotone Equations and Signal Processing

Abstract

A number of practical problems in science and engineering can be converted into a system of nonlinear equations and therefore, it is imperative to develop efficient methods for solving such equations. Due to their nice convergence properties and low storage requirements, conjugate gradient methods are considered among the most efficient for solving large-scale nonlinear equations. In this paper, a modified conjugate gradient method is proposed based on a projection technique and a suitable line search strategy. The proposed method is matrix-free and its sequence of search directions satisfies sufficient descent condition. Under the assumption that the underlying function is monotone and Lipschitzian continuous, the global convergence of the proposed method is established. The method is applied to solve some benchmark monotone nonlinear equations and also extended to solve ${\ell }_1$-norm regularized problems to reconstruct a sparse signal in compressive sensing. Numerical comparison with some existing methods shows that the proposed method is competitive, efficient and promising.

1. Introduction

Let ${\mathbb{R}}^n$ be an $n-$dimensional Euclidean space with inner product $\langle ·,·\rangle$ and norm $\parallel ·\parallel$. Suppose that D is a nonempty closed convex subset of ${\mathbb{R}}^n$. We denote by ${\mathbb{R}}_{+}^n$ the set $\{{(x_1,x_2,\dots ,x_n)}^T\in {\mathbb{R}}^n|x_i\ge 0,i=1,2,\dots ,n\}.$ In this paper, we consider the problem of finding a point $\widehat{x}$ in the set D for which

$$F\left(\widehat{x}\right)=0.$$

(1)

It is interesting to note that nonlinear equations in the form of (1) has various background and applications in science and engineering, such as the first-order necessary condition of the unconstrained convex optimization problems [1], the ${\ell }_1$-norm problem arising from compressing sensing [2], chemical equilibrium systems and optimal power flow equations [3], etc.

The classical methods for solving (1) include Newton’s method, quasi-Newton methods and inexact-Newton methods (see, Chapters 3 and 5 in [4], Chapter 11 in [5]). Unfortunately, these methods are not suitable for solving large-scale problems because they require solving systems of linear equations using the Jacobian matrix or its approximation at each iteration. As a result, several matrix-free methods for solving nonlinear systems of equations are proposed (see, e.g., [6,7,8,9,10] among others). On the other hand, Bellavia et al. [11] proposed an affine scaling trust-region iterative algorithm for bound-constrained systems of nonlinear equations. Their algorithm is based on the classical trust-region Newton method for unconstrained nonlinear equations and it possesses global and local fast convergence properties. They provided preliminary numerical experiments to show the efficiency of the method. Based on the nonmonotonic interior backtracking line search technique, Zhu [12] proposed an affine scaling trust-region method for nonlinear equality systems subject to bounds on variables. Under some standard assumptions, he proved the global convergence as well as the fast rate of local convergence of the method and reported some numerical experiments to demonstrate its effectiveness. In [13], Ahookhosh et al. presented a trust-region algorithm to solve symmetric nonlinear system of equations. Their algorithm combines an effective adaptive trust-region radius and a non-monotone strategy. They established the global convergence of the algorithm without the non-degeneracy assumption of the exact Jacobian and presented some numerical comparison to show its performance. For more detail on trust-region methods for nonlinear equations, the reader may refer to the survey paper by Yuan [14].

Among numerous methods for solving large-scale general unconstrained optimization problems, conjugate gradient methods (CG) are popular because they are simple to implement and require low storage with good convergence properties. Based on this, a quite number of researchers have made effort to extend some of the classical conjugate gradient methods to solve nonlinear monotone equations with convex constraints. For example, Xiao and Zhu [15] combined the conjugate gradient method of Hager and Zhang [16] and the projection technique of Solodov and Svaiter [17] to solve constrained system of monotone nonlinear equations. Their numerical experiments show that the method works well and its convergence analysis was established under some reasonable assumptions. The modified Perry conjugate gradient method [18] for general unconstrained optimization was extended by Dai et al. [19] to solve the unconstrained version of problem (1). The numerical performance of their method was compared with the methods in [20,21] and the results show their method stands out. Based on the popular Broyden–Fletcher–Goldfarb–Shanno (BFGS) updating formula for solving general unconstrained optimization, Gao et al. [22] recently proposed two adaptive projection algorithms to solve the system of monotone nonlinear equations with convex constraints. The sequence of the search directions generated by their algorithms satisfy sufficient descent property and under the assumption that the underlying function is Lipschitzian continuous, the convergence analysis of the method was established. Recently, different interesting results on spectral and conjugate gradient methods for addressing unconstrained minimization problems and nonlinear equations were presented in [23,24,25,26,27,28,29,30,31,32] and the references therein.

Inspired by the contributions discussed above, in this paper, we extend a modified Hestenes–Stiefel-like proposed by Amini et al. [33] to solve system of monotone nonlinear equations with convex constraints. We built the proposed algorithm by modifying the search direction of Amini et al. [33] and combining it with the projection technique of Solodov and Svaiter [17]. We proved the global convergence of the algorithm using a more general line search strategy that is mostly utilized in literature. Additional contribution of this paper is the application of the proposed algorithm to solve signal processing problem arising from compressive sensing. We present numerical experiments to demonstrate the efficiency of the proposed method and also establish the convergence analysis under standard assumptions. We organize the rest of this paper as follows. In Section 2, we present the algorithm and its global convergence. In Section 3, we present the numerical experiments and give the conclusions in Section 4.

2. Proposed Algorithm for Monotone Equations and Its Convergence Analysis

Definition 1.

Let $x,y\in {\mathbb{R}}^n,$ a function $F:{\mathbb{R}}^n\to {\mathbb{R}}^n$ is said to be

(i) 

monotone if

$$0\le \langle F\left(x\right)-F\left(y\right),x-y\rangle .$$

(2)

(ii) 

Lipschitzian continuous if there exists $L>0$ such that

$$\parallel F\left(x\right)-F\left(y\right)\parallel \le L\parallel x-y\parallel .$$

(3)

We begin by recalling the well-known Hestenes–Stiefel (HS) conjugate gradient method for solving unconstrained optimization problem of the form

$$min\{f\left(x\right):x\in {\mathbb{R}}^n\},$$

(4)

where $f:{\mathbb{R}}^n\to \mathbb{R}$ is a continuously differentiable function and bounded from below. HS CG method updates its sequence of iterates using the following recursive formula:

$$x_{k+1}=x_k+{\alpha }_k{d}_k,$$

(5)

where ${\alpha }_k>0$ is a suitable stepsize. The search direction $d_k$ is defined by

$$d_k=\left\{\begin{array}{cc}-F_k,\hfill & \mathrm{if}k=0,\hfill \\ -F_k+{\beta }_k^{HS}{d}_{k-1},\hfill & \mathrm{if}k>0,\hfill \end{array}\right.$$

(6)

where the CG parameter is given by

$${\beta }_k^{HS}=\frac{\langle F_k,y_{k-1}\rangle }{\langle y_{k-1},d_{k-1}\rangle },$$

and $y_{k-1}=F_k-F_{k-1}$ and $F_k$ denotes the gradient of f at $x_k.$

Definition 2.

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be differentiable at $x\in {\mathbb{R}}^n$ and $d\in {\mathbb{R}}^n$ satisfies

$$\langle F,d\rangle <0,$$

(7)

where F denotes the gradient of $f,$ then d is called a descent direction of f at $x.$

It is well known that (7) is a crucial property for iterative methods (5) to be globally convergent. However, the HS CG method does not guarantee (7), and therefore not globally convergent for general nonlinear functions.

The HS-CG method has enjoyed some forms of modifications in order to improve its convergence properties and/or its numerical performance. Recently, Amini et al. [33] studied some modified HS CG for solving (4). Based on the work of Narushima et al. [34] and Dai and Kou [35], Amini et al. proposed a modified HS CG method with the search direction defined as follows

$$d_k=\left\{\begin{array}{cc}-F_k,\hfill & \mathrm{if}k=0,\mathrm{or}{\overline{\beta }}_k^{MHS}\le 0\hfill \\ -F_k+{\overline{\beta }}_k^{MHS}{d}_{k-1},\hfill & \mathrm{if}k>0,\hfill \end{array}\right.$$

(8)

where

$${\overline{\beta }}_k^{MHS}=\frac{\langle F_k,y_{k-1}\rangle }{\langle y_{k-1},d_{k-1}\rangle }{\theta }_k-\eta {\left(\frac{\parallel y_{k-1}\parallel {\theta }_k}{\langle y_{k-1},d_{k-1}\rangle }\right)}^2\langle F_k,d_{k-1}\rangle ,$$

(9)

and ${\theta }_k=1-{\langle F_k,d_{k-1}\rangle }^2/\parallel F_k{\parallel }^2{\parallel d_{k-1}\parallel }^2.$ They showed that if $\langle y_{k-1},d_{k-1}\rangle \ne 0$ and $\eta >1/4,$ then the search direction $d_k$ satisfies the sufficient descent condition (7). The natural question that comes to mind is, can we modified (9) in such a way that these two restrictions are removed and still retain the nice properties associated with (8)?

In this paper we provide answer to the above question. Let $w_{k+1}=x_k+{\alpha }_k{d}_k,$ we define the proposed search direction as follows $d_0=-F\left(x_0\right)$ and

$$d_k=-v_{k}F\left(x_k\right)+max\{{\beta }_k^{PMHS},0\}{d}_{k-1},k=1,2,\dots ,$$

(10)

where

$${\beta }_k^{PMHS}=\frac{\langle F\left(x_k\right),d_{k-1}\rangle }{\parallel d_{k-1}{\parallel }^2}-\frac{\parallel {\gamma }_{k-1}{\parallel }^2}{{\langle {\gamma }_{k-1},d_{k-1}\rangle }^2}\langle F\left(x_k\right),d_{k-1}\rangle ,$$

(11)

$$v_k=\frac{\parallel s_{k-1}{\parallel }^2}{\langle {\gamma }_{k-1},s_{k-1}\rangle },{\gamma }_{k-1}=F\left(w_k\right)-F\left(x_{k-1}\right)+a{s}_{k-1},s_{k-1}=w_k-x_{k-1},a>0.$$

(12)

The incorporation of the spectral parameter $v_k$ in the definition of the search direction is to improve the numerical performance of the proposed algorithm. Next, we describe projection operator which is usually used in iterative algorithms for solving problems such as fixed point problem, variational inequality problem, and so on. Let $x\in {\mathbb{R}}^n$ and define an operator $P_D:{\mathbb{R}}^n\to D$ by $P_D\left(x\right)=\mathrm{argmin}\{\parallel x-y\parallel :y\in D\}.$ The operator $P_D$ is called a projection onto the feasible set D and it enjoys the nonexpansive property, that is, $\parallel P_D\left(x\right)-P_D\left(y\right)\parallel \le \parallel x-y\parallel ,\forall x,y\in {\mathbb{R}}^n.$ If $y\in D,$ then $P_D\left(y\right)=y$ and therefore, we have

$$\parallel P_D\left(x\right)-y\parallel \le \parallel x-y\parallel .$$

(13)

We now state the steps of the proposed algorithm in Algorithm 1.

Algorithm 1: Modified Hestene–Stiefel with spectral parameter (HSS).

Input: Given $x_0\in D$, $0<\kappa \le 1,$ $Tol>0,$ $a>0,$ $\sigma ,\varrho \in (0,1).$ Set $k=0$. Step 1: Compute $F\left(x_k\right).$ If $\parallel F\left(x_k\right)\parallel \le Tol,$ stop, otherwise go to step 2. Step 2: Compute the search direction as follows. If $k=0,$ $d_k=-F\left(x_k\right).$ Else $$d_k=-v_{k}F\left(x_k\right)+max\{{\beta }_k^{PMHS},0\}{d}_{k-1},$$ $${\beta }_k^{PMHS}=\frac{\langle F\left(x_k\right),d_{k-1}\rangle }{\parallel d_{k-1}{\parallel }^2}-\frac{\parallel {\gamma }_{k-1}{\parallel }^2}{{\langle {\gamma }_{k-1},d_{k-1}\rangle }^2}\langle F\left(x_k\right),d_{k-1}\rangle ,$$ $$v_k=\frac{\parallel s_{k-1}{\parallel }^2}{\langle {\gamma }_{k-1},s_{k-1}\rangle },{\gamma }_{k-1}=F\left(w_k\right)-F\left(x_{k-1}\right)+a{s}_{k-1},s_{k-1}=w_k-x_{k-1}.$$ Step 3: Determine the stepsize ${\alpha }_k=\kappa {\varrho }^i$ where i is the smallest nonegative integer such that $$-\langle F(x_k+\kappa {\varrho }^i{d}_k),d_k\rangle \ge \sigma \kappa {\varrho }^i\parallel d_k{\parallel }^2{\parallel F(x_k+\kappa {\varrho }^i{d}_k)\parallel }^{1/r},r\ge 1,$$ (14) Step 4: Set $w_{k+1}=x_k+{\alpha }_k{d}_k.$ If $w_{k+1}\in D$ and $\parallel F\left(w_{k+1}\right)\parallel \le Tol$ then stop. Else compute the next iterate using $$x_{k+1}=P_D\left[x_k-\frac{\langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle }{\parallel F\left(w_{k+1}\right){\parallel }^2}F\left(w_{k+1}\right)\right].$$ (15) Step 5: Set $k:=k+1$ and repeat the process from Step 1.

Remark 1.

The line search defined by (14) is more general than that of [36,37]. When $r=1,$ then the line search (14) reduces to the line search in [36] and when r is sufficiently large enough, it reduces to the line search in [37].

Assumption 1.

Throughout this paper, we assume the following

(i) 

The solution set of problem (1) is nonempty.

(ii) 

The function $F:{\mathbb{R}}^n\to {\mathbb{R}}^n$ satisfies (2) and (3).

The following lemma shows that the proposed search direction is well-defined and satisfies (7) independent of line search strategy.

Lemma 1.

The parameters ${\beta }_k^{PMHS}$ and $v_k$ defined by (11) and (12), respectively, are well-defined. In addition, $\forall k\ge 0,$ the search direction $d_k$ defined by (10) satisfies

$$\langle F\left(x_k\right),d_k\rangle \le -t{\parallel F_k\parallel }^2,t>0.$$

(16)

Proof of Lemma 1. 

From the monotonicity of $F,$ we have $\langle F\left(w_k\right)-F\left(x_{k-1}\right),w_k-x_{k-1}\rangle \ge 0.$ This implies that

$$\langle {\gamma }_{k-1},s_{k-1}\rangle \ge a{\parallel s_{k-1}\parallel }^2>0.$$

(17)

By the definition of $s_{k-1}$ and $w_k$ in Steps 2 and 4 of Algorithm 1, we have $s_{k-1}=w_k-x_{k-1}={\alpha }_{k-1}{d}_{k-1}.$ Therefore, it holds

$$\langle {\gamma }_{k-1},d_{k-1}\rangle \ge a{\alpha }_{k-1}{\parallel d_{k-1}\parallel }^2>0.$$

(18)

By (3) we have

$$\langle {\gamma }_{k-1},s_{k-1}\rangle =\begin{array}{c}\hfill \langle F\left(w_k\right)-F\left(x_{k-1}\right),s_{k-1}\rangle +a{\parallel s_{k-1}\parallel }^2\end{array}\le (L+a){\parallel s_{k-1}\parallel }^2.$$

(19)

So (17) and (19) give

$$\frac{1}{L+a}\le v_k\le \frac{1}{a}.$$

(20)

Hence $v_k$ is well-defined and so is ${\beta }_k^{PMHS}$ by (18).

Now taking the inner product of the search direction defined by (10) with $F_k$, for $k=0,$ it follows that $\langle F\left(x_k\right),d_k\rangle \le -{\parallel F\left(x_k\right)\parallel }^2,$ that is $t=1.$ Suppose $k>0$ and ${\beta }_k^{PMHS}\le 0,$ we get

$$\langle F\left(x_k\right),d_k\rangle =-v_k\parallel F\left(x_k\right){\parallel }^2\le -\frac{1}{L+a}{\parallel F\left(x_k\right)\parallel }^2.$$

Again, suppose $k>0$ and ${\beta }_k^{PMHS}>0,$ we have

$$\begin{array}{cc}\hfill \langle F\left(x_k\right),d_k\rangle & =-v_k{\parallel F\left(x_k\right)\parallel }^2+{\beta }_k^{PMHS}\langle F\left(x_k\right),d_{k-1}\rangle \hfill \\ \hfill & =-v_k{\parallel F\left(x_k\right)\parallel }^2+\left[\frac{\langle F\left(x_k\right),d_{k-1}\rangle }{\parallel d_{k-1}{\parallel }^2}-\frac{\parallel {\gamma }_{k-1}{\parallel }^2}{{\langle {\gamma }_{k-1},d_{k-1}\rangle }^2}\langle F\left(x_k\right),d_{k-1}\rangle \right]\langle F\left(x_k\right),d_{k-1}\rangle \hfill \\ \hfill & \le -v_k{\parallel F\left(x_k\right)\parallel }^2+\frac{{\langle F\left(x_k\right),d_{k-1}\rangle }^2}{\parallel d_{k-1}{\parallel }^2}-\frac{\parallel {\gamma }_{k-1}{\parallel }^2}{\parallel {\gamma }_{k-1}{\parallel }^2{\parallel d_{k-1}\parallel }^2}{\langle F\left(x_k\right),d_{k-1}\rangle }^2\hfill \\ \hfill & \le -\frac{1}{L+a}{\parallel F\left(x_k\right)\parallel }^2+\frac{{\langle F\left(x_k\right),d_{k-1}\rangle }^2}{\parallel d_{k-1}{\parallel }^2}-\frac{{\langle F\left(x_k\right),d_{k-1}\rangle }^2}{\parallel d_{k-1}{\parallel }^2}\hfill \\ \hfill & =-\frac{1}{L+a}{\parallel F\left(x_k\right)\parallel }^2.\hfill \end{array}$$

The two inequalities follow from Cauchy–Schwarz inequality and (20) respectively. Hence, the desired result holds. □

Lemma 2.

Let the sequence of iterates $\{x_k\}$ and the search direction $\{d_k\}$ be generated by Algorithm 1, then there always exists a step-size ${\alpha }_k$ satisfying the line search defined by (14) for any $k\ge 0.$

Proof of Lemma 2. 

Suppose on the contrary that there exists some $k_0$ such that for any $i=0,1,2,\dots ,$ the line search (14) does not hold, that is

$$-\langle F(x_{k_0}+\kappa {\varrho }^i{d}_{k_0}),d_{k_0}\rangle <\sigma \kappa {\varrho }^i\parallel d_{k_0}{\parallel }^2{\parallel F(x_{k_0}+\kappa {\varrho }^i{d}_{k_0})\parallel }^{1/r}.$$

(21)

By the fact that F is continuous, $\varrho \in (0,1)$ and $\{\parallel d_k\parallel \}$ is bounded for all k (see Lemma 3 below), letting $i\to \infty$ yields

$$\langle F\left(x_{k_0}\right),d_{k_0}\rangle \ge 0.$$

(22)

It is clear that the inequality (22) contradicts (16). Hence the line search (14) is well-defined. □

Lemma 3.

Let Assumption 1 hold and $\widehat{x}$ be a solution of problem (1). Suppose the sequences $\{w_k\},$ $\{x_k\}$ and $\{d_k\}$ are generated by Algorithm 1. Then the following hold

(i) 

$\{x_k\}$ and $\{\parallel F\left(x_k\right)\parallel \}$ are bounded and $\underset{k\to \infty }{lim}\parallel x_k-\widehat{x}\parallel$ exists.

(ii) 

The sequence of the search direction $\{\parallel d_k\parallel \}$ is bounded.

(iii) 

$\{w_k\}$ and $\{\parallel F\left(w_k\right)\parallel \}$ are bounded.

(iv) 

$\underset{k\to \infty }{lim}{\alpha }_k\parallel d_k\parallel =0.$

(v) 

$\underset{k\to \infty }{lim}\parallel x_{k+1}-x_k\parallel =0.$

Proof of Lemma 3. 

To show (i), let $k\ge 0$ and $\widehat{x}$ be a solution of problem (1), then $\langle F\left(\widehat{x}\right),w_{k+1}-\widehat{x}\rangle =0.$ Since F is monotone, we have $\langle F\left(w_{k+1}\right),w_{k+1}-\widehat{x}\rangle \ge \langle F\left(\widehat{x}\right),w_{k+1}-\widehat{x}\rangle =0.$ Therefore, it holds that

$$\langle F\left(w_{k+1}\right),x_k-\widehat{x}\rangle =\langle F\left(w_{k+1}\right),x_k-w_{k+1}+w_{k+1}-\widehat{x}\rangle \ge \langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle .$$

(23)

From the property (13) we have

$$∥P_D\left(x_k-\frac{\langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle }{\parallel F\left(w_{k+1}\right){\parallel }^2}F\left(w_{k+1}\right)\right)-\widehat{x}∥\le ∥x_k-\frac{\langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle }{\parallel F\left(w_{k+1}\right){\parallel }^2}F\left(w_{k+1}\right)-\widehat{x}∥.$$

(24)

From the definition of $x_{k+1},$ we have

$$\begin{array}{cc}\parallel x_{k+1}-\widehat{x}{\parallel }^2\hfill & \le {∥x_k-\widehat{x}-\frac{\langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle }{\parallel F\left(w_{k+1}\right){\parallel }^2}F\left(w_{k+1}\right)∥}^2\hfill \\ \hfill & =\parallel x_k-\widehat{x}{\parallel }^2-2\frac{\langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle }{\parallel F\left(w_{k+1}\right){\parallel }^2}\langle F\left(w_{k+1}\right),x_k-\widehat{x}\rangle +\frac{{\langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle }^2}{\parallel F\left(w_{k+1}\right){\parallel }^2}\hfill \\ \hfill & \le \parallel x_k-\widehat{x}{\parallel }^2-2\frac{\langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle }{\parallel F\left(w_{k+1}\right){\parallel }^2}\langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle +\frac{{\langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle }^2}{\parallel F\left(w_{k+1}\right){\parallel }^2}\hfill \\ \hfill & =\parallel x_k-\widehat{x}{\parallel }^2-\frac{{\langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle }^2}{\parallel F\left(w_{k+1}\right){\parallel }^2}\hfill \\ \hfill & \le \parallel x_k-\widehat{x}{\parallel }^2.\hfill \end{array}$$

(25)

The first and second inequalities respectively follow from (24) and (23). The last inequality holds by dropping the second negative term on the right hand side. This implies that $\parallel x_k-\widehat{x}\parallel \le \parallel x_0-\widehat{x}\parallel$ for all $k,$ and therefore the sequence $\{x_k\}$ is bounded and $\underset{k\to \infty }{lim}\parallel x_k-\widehat{x}\parallel$ exists. Let $c_1=L\parallel x_0-\widehat{x}\parallel ,$ since F is Lipschitzian continuous and $\{\parallel x_k-\widehat{x}\parallel \}$ is decreasing then

$$\parallel F\left(x_k\right)\parallel =\parallel F\left(x_k\right)-F\left(\widehat{x}\right)\parallel \le L\parallel x_k-\widehat{x}\parallel \le \cdots \le L\parallel x_0-\widehat{x}\parallel =c_1.$$

(26)

To show (ii), let $k=0,$ by the definition of the search direction (10) we have

$$\parallel d_0\parallel =\parallel F\left(x_0\right)\parallel \le c_1.$$

(27)

Suppose $k>0$ and ${\beta }_k^{PMHS}\le 0,$ then $max\{{\beta }_k^{PMHS},0\}=0$ and (10) reduces

$$d_k=-v_{k}F\left(x_k\right),k=1,2,\dots ,$$

Therefore, combining with (20) and (26) yields

$$\parallel d_k\parallel =v_k\parallel F\left(x_k\right)\parallel \le \frac{c_1}{a}.$$

(28)

By the Lipschitzian continuity, we have

$$\begin{array}{cc}\hfill \parallel {\gamma }_{k-1}\parallel & =\parallel F\left(w_k\right)-F\left(x_{k-1}\right)+a(w_k-x_{k-1})\parallel \hfill \\ \hfill & \le L\parallel w_k-x_{k-1}\parallel +a\parallel w_k-x_{k-1}\parallel \hfill \\ \hfill & \le (L+a){\alpha }_{k-1}\parallel d_{k-1}\parallel .\hfill \end{array}$$

(29)

Again, suppose $k>0$ and ${\beta }_k^{PMHS}>0,$ we have

$$\begin{array}{cc}\hfill \parallel d_k\parallel & =\parallel -v_{k}F\left(x_k\right)+{\beta }_k^{PMHS}{d}_{k-1}\parallel \hfill \\ \hfill & \le v_k\parallel F\left(x_k\right)\parallel +|{\beta }_k^{PMHS}|\parallel d_{k-1}\parallel \hfill \\ \hfill & =v_k\parallel F\left(x_k\right)\parallel +\left|\frac{\langle F\left(x_k\right),d_{k-1}\rangle }{\parallel d_{k-1}{\parallel }^2}-\frac{\parallel {\gamma }_{k-1}{\parallel }^2}{{\langle {\gamma }_{k-1},d_{k-1}\rangle }^2}\langle F\left(x_k\right),d_{k-1}\rangle \right|\parallel d_{k-1}\parallel \hfill \\ \hfill & \le v_k\parallel F\left(x_k\right)\parallel +\left[\frac{\parallel F\left(x_k\right)\parallel \parallel d_{k-1}\parallel }{\parallel d_{k-1}{\parallel }^2}+\frac{\parallel {\gamma }_{k-1}{\parallel }^2}{{\langle {\gamma }_{k-1},d_{k-1}\rangle }^2}\parallel F\left(x_k\right)\parallel \parallel d_{k-1}\parallel \right]\parallel d_{k-1}\parallel \hfill \\ \hfill & =v_k\parallel F\left(x_k\right)\parallel +\parallel F\left(x_k\right)\parallel +\frac{\parallel {\gamma }_{k-1}{\parallel }^2}{{\langle {\gamma }_{k-1},d_{k-1}\rangle }^2}\parallel F\left(x_k\right)\parallel \parallel d_{k-1}{\parallel }^2\hfill \\ \hfill & \le \frac{1}{a}\parallel F\left(x_k\right)\parallel +\parallel F\left(x_k\right)\parallel +\frac{{(L+a)}^2{\alpha }_{k-1}^2\parallel F\left(x_k\right)\parallel \parallel d_{k-1}{\parallel }^4}{a^2{\alpha }_{k-1}^2{\parallel d_{k-1}\parallel }^4}\hfill \\ \hfill & =\frac{1}{a}\parallel F\left(x_k\right)\parallel +\parallel F\left(x_k\right)\parallel +\frac{{(L+a)}^2}{a^2}\parallel F\left(x_k\right)\parallel \hfill \\ \hfill & =\left[\frac{1}{a}+1+\frac{{(L+a)}^2}{a^2}\right]\parallel F\left(x_k\right)\parallel \hfill \\ \hfill & \le \left[\frac{1}{a}+1+\frac{{(L+a)}^2}{a^2}\right]c_1.\hfill \end{array}$$

The first and second inequalities follow from triangle inequality and Cauchy–Schwartz inequality, respectively. The third inequality follows from (18) and (29), while the fourth inequality follows from (26). If we let $c:=\left[\frac{1}{a}+1+\frac{{(L+a)}^2}{a^2}\right]c_1,$ then it holds that

$$\parallel d_k\parallel \le c,\forall k.$$

(30)

Next, we show (iii). By the boundedness $\{x_k\}$ and (30), it follows from the definition $w_k$ that $\{w_k\}$ is also bounded. By Lipschitzian continuity of $F,$ there exists some constant $c_2$ for which

$$\parallel F\left(w_k\right)\parallel \le c_2,\forall k\ge 0.$$

(31)

To show (iv), from (25), we deduce

$${\langle F\left(w_{k+1}\right),{\alpha }_k{d}_k\rangle }^2\le \parallel F\left(w_{k+1}\right){\parallel }^2(\parallel x_k-\widehat{x}{\parallel }^2-\parallel x_{k+1}-\widehat{x}{\parallel }^2).$$

(32)

Since the stepsize ${\alpha }_k$ in Step 3 of Algorithm 1 satisfies ${\alpha }_k\le 1,$ $\forall k,$ then from (14), we have

$${\sigma }^2{\alpha }_k^4\parallel d_k{\parallel }^4\parallel F\left(w_{k+1}\right){\parallel }^{2/r}\le {\sigma }^2{\alpha }_k^2\parallel d_k{\parallel }^4{\parallel F\left(w_{k+1}\right)\parallel }^{2/r}\le {\langle F\left(w_{k+1}\right),{\alpha }_k{d}_k\rangle }^2.$$

(33)

Combining (32) and (33) gives

$${\sigma }^2{\alpha }_k^4\parallel d_k{\parallel }^4\parallel F\left(w_{k+1}\right){\parallel }^{2/r}\le \parallel F\left(w_{k+1}\right){\parallel }^2(\parallel x_k-\widehat{x}{\parallel }^2-\parallel x_{k+1}-\widehat{x}{\parallel }^2).$$

(34)

Multiplying both sides of (34) by $\parallel F\left(w_{k+1}\right){\parallel }^{-2/r}$ and using (31) gives

$${\sigma }^2{\alpha }_k^4\parallel d_k{\parallel }^4\le \parallel F\left(w_{k+1}\right){\parallel }^{2-2/r}(\parallel x_k-\widehat{x}{\parallel }^2-\parallel x_{k+1}-\widehat{x}{\parallel }^2)\le c_2^{2-2/r}(\parallel x_k-\widehat{x}{\parallel }^2-\parallel x_{k+1}-\widehat{x}{\parallel }^2).$$

(35)

Taking limits of both sides give

$${\sigma }^2\underset{k\to \infty }{lim}{\alpha }_k^4{\parallel d_k\parallel }^4=0.$$

(36)

Thus,

$$\underset{k\to \infty }{lim}{\alpha }_k\parallel d_k\parallel =0.$$

(37)

Finally, we show (v). Equation (37), together with the definition of $w_{k+1}$ in Step 4 of Algorithm 1 yields

$$\underset{k\to \infty }{lim}\parallel w_{k+1}-x_k\parallel =0.$$

(38)

By the property of projection (13), we have

$$\begin{array}{cc}\hfill \underset{k\to \infty }{lim}\parallel x_{k+1}-x_k\parallel & =\underset{k\to \infty }{lim}∥P_D\left[x_k-\frac{\langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle }{\parallel F\left(w_{k+1}\right){\parallel }^2}F\left(w_{k+1}\right)\right]-x_k∥\hfill \\ \hfill & \le \underset{k\to \infty }{lim}∥x_k-\frac{\langle F\left(w_{k+1}\right),x_k-w_{k+1}\rangle }{\parallel F\left(w_{k+1}\right){\parallel }^2}F\left(w_{k+1}\right)-x_k∥\hfill \\ \hfill & \le \underset{k\to \infty }{lim}\parallel x_k-w_{k+1}\parallel \hfill \\ \hfill & =0.\hfill \end{array}$$

(39)

 □

Theorem 1.

Let $\{x_k\}$ be the sequence generated by Algorithm 1. Suppose Assumption 1 holds then

(i) 

$\underset{k\to \infty }{lim\; inf}\parallel F\left(x_k\right)\parallel =0.$

(ii) 

the sequence $\{x_k\}$ converges to a point $\widehat{x}$ which satisfies $F\left(\widehat{x}\right)=0.$

Proof of Theorem 1. 

We prove (i) by contradiction. Now suppose that

$$\underset{k\to \infty }{lim\; inf}\parallel F\left(x_k\right)\parallel >0,\forall k,$$

then we can find some positive constant, say $\vartheta$ such that

$$\parallel F\left(x_k\right)\parallel \ge \vartheta ,\forall k.$$

(40)

Applying the Cauchy–Schwarz inequality to (16) yields $t\parallel F\left(x_k\right)\parallel \le \parallel d_k\parallel .$ This, together with (40) gives $\parallel d_k\parallel \ge t\vartheta .$ Combining with (37), we obtain

$$\underset{k\to \infty }{lim}{\alpha }_k=0.$$

(41)

Since F satisfies Lipschitzian continuity, then it holds

$$\begin{array}{cc}\hfill \parallel F(x_k+{\varrho }^{-1}{\alpha }_k{d}_k)\parallel & =\parallel F(x_k+{\varrho }^{-1}{\alpha }_k{d}_k)-F\left(\widehat{x}\right)\parallel \hfill \\ \hfill & \le L\parallel x_k+{\varrho }^{-1}{\alpha }_k{d}_k-\widehat{x}\parallel \hfill \\ \hfill & \le L\parallel x_k-\widehat{x}\parallel +{\varrho }^{-1}{\alpha }_k\parallel d_k\parallel \hfill \\ \hfill & \le m,\hfill \end{array}$$

(42)

where m is a positive constant. The last inequality follows from the boundedness of $\{x_k\}$ and $\{d_k\}$ together with the definition of ${\alpha }_k.$ If ${\alpha }_k\ne \kappa ,$ since Algorithm 1 uses a backtracking process to compute ${\alpha }_k$ starting from $\kappa ,$ then ${\varrho }^{-1}{\alpha }_k$ does not satisfy (14), that is,

$$\begin{array}{cc}\hfill -\langle F(x_k+{\varrho }^{-1}{\alpha }_k{d}_k),d_k\rangle & <\sigma {\varrho }^{-1}{\alpha }_k\parallel d_k{\parallel }^2{\parallel F(x_k+{\varrho }^{-1}{\alpha }_k{d}_k)\parallel }^{1/r}\hfill \\ \hfill & \le \sigma {\varrho }^{-1}{\alpha }_k{c}^2{m}^{1/r}\hfill \\ \hfill & =M{\alpha }_k,\hfill \end{array}$$

(43)

where $M:=\sigma {\varrho }^{-1}{c}^2{m}^{1/r}$ and the second inequality follows from (30) and (42). Since $\{x_k\}$ and $\{\parallel d_k\parallel \}$ are bounded, there exist some accumulation points $\widehat{x}$ and $\widehat{d}$ of $\{x_k\}$ and $\{\parallel d_k\parallel \}$ respectively and some infinite index sets K and $K_{\ast }$ for which $\underset{k\in K}{lim}{x}_k=\widehat{x}$ and $\underset{k\in K_{\ast }}{lim}{d}_k=\widehat{d}$ where $K_{\ast }\subset K.$ Therefore by the continuity of F and taking limit on both sides of inequality (43) for $k\in K_{\ast }$ we obtain

$$-\langle F\left(\widehat{x}\right),\widehat{d}\rangle \le 0.$$

(44)

On the other hand, (16) and (40) gives $-\langle F_k,d_k\rangle \ge t{\vartheta }^2.$ Taking limit for $k\in K_{\ast }$ we obtain

$$-\langle F\left(\widehat{x}\right),\widehat{d}\rangle >0.$$

(45)

The inequalities (44) and (45) yield contradiction and therefore (i) must hold.

Finally, we show (ii) holds. Now, since F is continuous and the sequence $\{x_k\}$ is bounded, then there is some accumulation point of $\{x_k\}$ say $\widehat{x}$ for which $\parallel F\left(\widehat{x}\right)\parallel =0$. By boundedness of $\{x_k\},$ we can find subsequence $\{x_{k_j}\}$ of $\{x_k\}$ for which $\underset{j\to \infty }{lim}\parallel x_{k_j}-\widehat{x}\parallel =0.$ Since $\underset{k\to \infty }{lim}\parallel x_k-\widehat{x}\parallel$ exists, from (i) of Lemma 3, we can conclude that $\underset{k\to \infty }{lim}\parallel x_k-\widehat{x}\parallel =0$ and the proof is complete. □

3. Experiment on Monotone Equations and Application in Signal Processing

In this section, we demonstrate the numerical performance of Algorithm 1 (HSS) and its computational advantage by comparing with some existing methods. We divide the experiment into two subsections where the first subsection is devoted to solving some test problems while the second subsection discussed the application of HSS algorithm in signal recovery. For the monotone nonlinear equations experiment, all solvers were coded in MATLAB R2019b and run on a PC with intel Core(TM) i5-8250u processor with 4GB of RAM and CPU 1.60GHZ.

3.1. First Experiment on Monotone Equations

In this experiment, we apply HSS algorithm to solve eleven test problems and compared the numerical results with some state of the art existing methods namely: modified Harger and Zhang CG method denoted as CGD (also known as CG_Descent) by Xiao and Zhu [15], modified Dai–Yuan CG method denoted as PDY by Liu and Feng [32] and modified Fletcher–Reeves CG method denoted as MFRM by Abubakar et al. [25]. We considered eleven problems where Problems 1–10 are solved with dimension $n=1000,5000,10,000,50,000,100,000$ and Problem 11 with dimension $n=4$ (see Appendix A). We used six different starting points, that is, $x_1={(0.1,0.1,0.1,\cdots ,0.1)}^T,$ $x_2={(\frac{1}{2},\frac{1}{2^2},\frac{1}{2^3},\cdots ,\frac{1}{2^n})}^T,$ $x_3={(2,2,\dots ,2)}^T,$ $x_4={(1,\frac{1}{2},\frac{1}{3},\cdots ,\frac{1}{n})}^T,$ $x_5={(1-\frac{1}{n},1-\frac{2}{n},1-\frac{3}{n},\cdots ,0)}^T$ and $x_6=\mathrm{rand}(0,1)$. This brings the total number of problem runs in this experiment to 306.

We implemented HSS method using the following parameters $\kappa =1,$ $\sigma =0.01,$ $\varrho =0.5,$ $r=5$ and $a=0.01$ while the parameters used for CGD, PDY and MFRM methods come from [15,25,32], respectively. We set the terminating criterion for the iteration process as $\parallel F\left(x_k\right)\parallel \le {10}^{-6}$ or $\parallel F\left(w_k\right)\parallel \le {10}^{-6}$ and declare failure (denoted by "-") whenever the number of iterations exceeds 1000 and the terminating criterion has not been satisfied.

We carried out the comparison based on ITER (number of iterations), FVAL (number of function evaluations) and TIME (CPU time(s)) and the numerical results obtained by each solver are reported in

Table 1. Test results obtained by the four solvers for Problem 1.

Problem 1		HSS				CGD				PDY				MFRM
DIM	SP	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM
1000	x1	5	12	0.4454	1.2 × ${10}^{-8}$	41	84	0.029665	9.97 × ${10}^{-7}$	36	74	0.0291	3.49 × ${10}^{-7}$	47	96	0.049823	4.58 × ${10}^{-7}$
	x2	25	51	0.030772	9.12 × ${10}^{-7}$	57	116	0.020445	8.17 × ${10}^{-7}$	42	85	0.015079	8.84 × ${10}^{-7}$	65	131	0.054894	9.19 × ${10}^{-7}$
	x3	8	17	0.005867	9.42 × ${10}^{-9}$	50	102	0.011775	8.56 × ${10}^{-7}$	46	94	0.017204	2.21 × ${10}^{-8}$	40	82	0.032647	5.07 × ${10}^{-7}$
	x4	24	50	0.010883	7.2 × ${10}^{-7}$	58	118	0.015481	9.51 × ${10}^{-7}$	40	82	0.018437	3.16 × ${10}^{-7}$	44	90	0.037726	5.45 × ${10}^{-7}$
	x5	7	15	0.00825	1.49 × ${10}^{-8}$	51	104	0.012897	8.46 × ${10}^{-7}$	51	104	0.019256	9.89 × ${10}^{-7}$	64	130	0.072206	7.35 × ${10}^{-7}$
	x6	7	15	0.021386	2.37 × ${10}^{-8}$	41	84	0.011211	8.86 × ${10}^{-7}$	46	94	0.018799	7.01 × ${10}^{-7}$	80	162	0.072448	6.36 × ${10}^{-8}$
5000	x1	5	11	0.024934	1.79 × ${10}^{-7}$	40	82	0.040348	8.34 × ${10}^{-7}$	27	56	0.034997	1.3 × ${10}^{-8}$	35	72	0.19811	6.59 × ${10}^{-7}$
	x2	25	51	0.043535	9.12 × ${10}^{-7}$	57	116	0.04253	8.17 × ${10}^{-7}$	42	85	0.08315	8.84 × ${10}^{-7}$	65	131	0.2973	9.19 × ${10}^{-7}$
	x3	7	16	0.063339	2.09 × ${10}^{-8}$	48	98	0.05612	8.76 × ${10}^{-7}$	28	58	0.067063	4.05 × ${10}^{-7}$	51	104	0.19957	5.68 × ${10}^{-7}$
	x4	24	50	0.045037	7.2 × ${10}^{-7}$	58	118	0.083654	9.51 × ${10}^{-7}$	36	74	0.066975	3.44 × ${10}^{-7}$	57	116	0.2415	6.8 × ${10}^{-7}$
	x5	7	15	0.016824	3.17 × ${10}^{-8}$	49	100	0.069098	8.61 × ${10}^{-7}$	51	104	0.093807	7.98 × ${10}^{-7}$	51	104	0.42878	6.81 × ${10}^{-7}$
	x6	7	15	0.013023	3.37 × ${10}^{-8}$	38	78	0.061728	8.02 × ${10}^{-7}$	49	99	0.083743	8.02 × ${10}^{-7}$	88	178	0.79169	6.7 × ${10}^{-7}$
10000	x1	5	11	0.025322	1.82 × ${10}^{-7}$	39	80	0.087834	8.97 × ${10}^{-7}$	29	60	0.10988	2.14 × ${10}^{-8}$	37	76	0.3135	3.44 × ${10}^{-7}$
	x2	25	51	0.092561	9.12 × ${10}^{-7}$	57	116	0.13838	8.17 × ${10}^{-7}$	42	85	0.13059	8.84 × ${10}^{-7}$	65	131	0.58046	9.19 × ${10}^{-7}$
	x3	7	16	0.021996	2.96 × ${10}^{-8}$	47	96	0.10667	9.17 × ${10}^{-7}$	31	64	0.11367	1.18 × ${10}^{-7}$	93	188	1.4396	2.81 × ${10}^{-7}$
	x4	24	50	0.077032	7.2 × ${10}^{-7}$	58	118	0.14476	9.51 × ${10}^{-7}$	41	84	0.15532	1.1 × ${10}^{-7}$	48	98	0.38582	8.67 × ${10}^{-7}$
	x5	7	15	0.020935	4.45 × ${10}^{-8}$	48	98	0.10544	8.97 × ${10}^{-7}$	47	95	0.16012	5.62 × ${10}^{-7}$	97	196	2.8134	9.86 × ${10}^{-7}$
	x6	7	15	0.02372	4.53 × ${10}^{-8}$	42	86	0.090851	8.97 × ${10}^{-7}$	54	109	0.27744	5.59 × ${10}^{-7}$	114	230	3.2143	2.62 × ${10}^{-7}$
50000	x1	5	11	0.12861	3.17 × ${10}^{-7}$	38	78	0.33746	8.43 × ${10}^{-7}$	28	58	0.44472	8.48 × ${10}^{-8}$	47	96	1.8109	3.45 × ${10}^{-7}$
	x2	25	51	0.40895	9.12 × ${10}^{-7}$	57	116	0.4312	8.17 × ${10}^{-7}$	42	85	0.58467	8.84 × ${10}^{-7}$	65	131	2.2362	9.19 × ${10}^{-7}$
	x3	7	16	0.089772	6.61 × ${10}^{-8}$	45	92	0.38008	9.78 × ${10}^{-7}$	44	90	0.76263	2.61 × ${10}^{-7}$	49	100	3.709	6.73 × ${10}^{-7}$
	x4	24	50	0.49831	7.2 × ${10}^{-7}$	58	118	0.49767	9.51 × ${10}^{-7}$	45	92	0.64548	2.84 × ${10}^{-7}$	51	104	1.6105	8.18 × ${10}^{-7}$
	x5	7	15	0.08695	9.9 × ${10}^{-8}$	46	94	0.40103	9.31 × ${10}^{-7}$	51	104	0.72555	6.27 × ${10}^{-7}$	203	408	27.1911	9.8 × ${10}^{-7}$
	x6	7	15	0.081075	9.63 × ${10}^{-8}$	41	84	0.37714	9.08 × ${10}^{-7}$	44	90	0.63276	6.26 × ${10}^{-7}$	173	348	17.3745	6.02 × ${10}^{-7}$
100000	x1	5	11	0.1897	4.34 × ${10}^{-7}$	38	78	0.68124	7.72 × ${10}^{-7}$	21	44	0.78409	7.7 × ${10}^{-7}$	40	82	2.3871	7.69 × ${10}^{-7}$
	x2	25	51	1.1264	9.12 × ${10}^{-7}$	57	116	1.092	8.17 × ${10}^{-7}$	42	85	1.2409	8.84 × ${10}^{-7}$	65	131	3.7292	9.19 × ${10}^{-7}$
	x3	7	16	0.19532	9.34 × ${10}^{-8}$	45	92	0.76874	8.38 × ${10}^{-7}$	37	76	1.5389	4.43 × ${10}^{-8}$	107	216	16.1536	9.91 × ${10}^{-7}$
	x4	24	50	0.69604	7.2 × ${10}^{-7}$	58	118	1.1008	9.51 × ${10}^{-7}$	32	66	1.0387	7.38 × ${10}^{-7}$	54	110	3.0635	7.87 × ${10}^{-7}$
	x5	7	15	0.13571	1.4 × ${10}^{-7}$	45	92	0.81993	9.9 × ${10}^{-7}$	51	104	3.0136	7.08 × ${10}^{-7}$	451	904	155.5752	8.9 × ${10}^{-7}$
	x6	7	15	0.15849	1.38 × ${10}^{-7}$	41	84	0.83232	9.94 × ${10}^{-7}$	49	100	2.741	7.08 × ${10}^{-7}$	182	366	53.9013	5.58 × ${10}^{-7}$

,

Table 2. Test results obtained by the four solvers for Problem 2.

Problem 2		HSS				CGD				PDY				MFRM
DIM	SP	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM
1000	x1	4	10	0.065511	4.79 × ${10}^{-8}$	54	110	0.051537	8.99 × ${10}^{-7}$	2	6	0.004049	5.17 × ${10}^{-7}$	2	6	0.00428	5.17 × ${10}^{-7}$
	x2	7	16	0.004944	3.08 × ${10}^{-7}$	55	112	0.020758	8.77 × ${10}^{-7}$	18	38	0.014524	4.14 × ${10}^{-7}$	60	122	0.030779	8.53 × ${10}^{-8}$
	x3	8	18	0.007408	5.76 × ${10}^{-8}$	80	162	0.024411	8.64 × ${10}^{-7}$	5	12	0.005914	1.74 × ${10}^{-8}$	5	12	0.002481	1.74 × ${10}^{-8}$
	x4	8	18	0.004786	5.33 × ${10}^{-8}$	60	122	0.030894	9.09 × ${10}^{-7}$	20	42	0.014378	8.06 × ${10}^{-7}$	86	174	0.041737	6.46 × ${10}^{-7}$
	x5	8	18	0.006147	2.74 × ${10}^{-7}$	71	144	0.032592	8.41 × ${10}^{-7}$	27	56	0.025985	1.81 × ${10}^{-7}$	96	194	0.044708	2.04 × ${10}^{-7}$
	x6	8	18	0.007174	2.78 × ${10}^{-7}$	71	144	0.033933	8.54 × ${10}^{-7}$	25	52	0.048252	2.21 × ${10}^{-7}$	89	180	0.051754	8.75 × ${10}^{-8}$
5000	x1	4	10	0.013144	1.06 × ${10}^{-7}$	58	118	0.08423	8.02 × ${10}^{-7}$	2	6	0.011378	1.75 × ${10}^{-7}$	2	6	0.00446	1.75 × ${10}^{-7}$
	x2	7	16	0.018096	3.13 × ${10}^{-7}$	55	112	0.10769	8.7 × ${10}^{-7}$	30	62	0.19022	1.54 × ${10}^{-7}$	73	148	0.15676	6.86 × ${10}^{-7}$
	x3	8	18	0.018438	1.28 × ${10}^{-7}$	83	168	0.12004	9.71 × ${10}^{-7}$	5	12	0.011973	2.36 × ${10}^{-9}$	5	12	0.009605	2.36 × ${10}^{-9}$
	x4	8	18	0.022149	5.4 × ${10}^{-8}$	60	122	0.12048	9 × ${10}^{-7}$	18	38	0.094073	5.88 × ${10}^{-8}$	61	124	0.13065	8.76 × ${10}^{-7}$
	x5	8	18	0.034873	9.51 × ${10}^{-7}$	74	150	0.12629	9.49 × ${10}^{-7}$	22	46	0.046554	8.16 × ${10}^{-7}$	77	156	0.20059	1.08 × ${10}^{-7}$
	x6	8	18	0.035623	9.55 × ${10}^{-7}$	74	150	0.13564	9.58 × ${10}^{-7}$	22	46	0.079387	7.45 × ${10}^{-7}$	87	176	0.2346	4.59 × ${10}^{-7}$
10000	x1	4	10	0.015467	1.5 × ${10}^{-7}$	59	120	0.15681	9.04 × ${10}^{-7}$	2	6	0.012605	1.21 × ${10}^{-7}$	2	6	0.015088	1.21 × ${10}^{-7}$
	x2	7	16	0.030136	3.13 × ${10}^{-7}$	55	112	0.15155	8.69 × ${10}^{-7}$	28	58	0.52817	1.05 × ${10}^{-7}$	72	146	0.33387	9.65 × ${10}^{-7}$
	x3	8	18	0.030859	1.82 × ${10}^{-7}$	85	172	0.52762	8.77 × ${10}^{-7}$	5	12	0.10838	3.62 × ${10}^{-9}$	5	12	0.018115	1.24 × ${10}^{-9}$
	x4	8	18	0.062129	5.41 × ${10}^{-8}$	60	122	0.36479	8.99 × ${10}^{-7}$	15	32	0.052187	5.56 × ${10}^{-7}$	78	158	0.3405	1.51 × ${10}^{-7}$
	x5	9	20	0.064209	1.33 × ${10}^{-8}$	76	154	0.20614	8.58 × ${10}^{-7}$	25	52	0.089306	9 × ${10}^{-7}$	101	204	0.53394	5.47 × ${10}^{-7}$
	x6	9	20	0.067411	1.33 × ${10}^{-8}$	76	154	0.3443	8.58 × ${10}^{-7}$	31	64	0.12864	8.79 × ${10}^{-7}$	73	148	0.44865	6.23 × ${10}^{-7}$
50000	x1	4	10	0.068733	3.34 × ${10}^{-7}$	63	128	0.7666	8.26 × ${10}^{-7}$	2	6	0.03321	6.32 × ${10}^{-8}$	2	6	0.031681	6.32 × ${10}^{-8}$
	x2	7	16	0.20861	3.14 × ${10}^{-7}$	55	112	1.2994	8.68 × ${10}^{-7}$	21	44	0.30953	6.18 × ${10}^{-10}$	49	100	0.99731	2.56 × ${10}^{-7}$
	x3	8	18	0.24123	4.06 × ${10}^{-7}$	89	180	1.1196	8.02 × ${10}^{-7}$	6	14	0.25741	9.31 × ${10}^{-9}$	5	12	0.061125	4.01 × ${10}^{-10}$
	x4	8	18	0.40721	5.42 × ${10}^{-8}$	60	122	1.6253	8.98 × ${10}^{-7}$	15	32	0.42982	2.59 × ${10}^{-7}$	61	124	1.2389	7.49 × ${10}^{-7}$
	x5	9	20	0.25666	2.98 × ${10}^{-8}$	79	160	1.2268	9.81 × ${10}^{-7}$	23	48	0.34981	1.82 × ${10}^{-7}$	108	218	1.9382	7.03 × ${10}^{-7}$
	x6	9	20	0.1428	2.98 × ${10}^{-8}$	79	160	1.9121	9.81 × ${10}^{-7}$	24	50	0.40973	7.86 × ${10}^{-7}$	111	224	2.3737	7.48 × ${10}^{-7}$
100000	x1	4	10	0.14432	4.73 × ${10}^{-7}$	64	130	2.8646	9.34 × ${10}^{-7}$	2	6	0.061232	5.4 × ${10}^{-8}$	2	6	0.058923	5.4 × ${10}^{-8}$
	x2	7	16	0.18563	3.14 × ${10}^{-7}$	55	112	1.6057	8.68 × ${10}^{-7}$	29	60	0.86796	6.52 × ${10}^{-8}$	71	144	2.482	9.83 × ${10}^{-7}$
	x3	8	18	0.26077	5.74 × ${10}^{-7}$	90	182	2.6208	9.07 × ${10}^{-7}$	7	16	0.29491	1.1 × ${10}^{-9}$	5	12	0.11839	2.71 × ${10}^{-10}$
	x4	8	18	0.30728	5.42 × ${10}^{-8}$	60	122	1.8968	8.98 × ${10}^{-7}$	15	32	0.64725	2.34 × ${10}^{-7}$	61	124	2.7544	4.46 × ${10}^{-7}$
	x5	9	20	0.29364	4.22 × ${10}^{-8}$	81	164	2.4882	8.87 × ${10}^{-7}$	20	42	0.95254	3.99 × ${10}^{-7}$	86	174	3.8181	8.38 × ${10}^{-7}$
	x6	9	20	0.30376	4.21 × ${10}^{-8}$	81	164	2.1676	8.87 × ${10}^{-7}$	21	44	0.67373	7.01 × ${10}^{-8}$	130	262	4.741	5.23 × ${10}^{-7}$

,

Table 3. Test results obtained by the four solvers for Problem 3.

Problem 3		HSS				CGD				PDY				MFRM
DIM	SP	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM
1000	x1	4	10	0.02031	1.97 × ${10}^{-8}$	67	136	0.033374	9.14 × ${10}^{-7}$	21	44	0.016594	7.52 × ${10}^{-7}$	6	14	0.003308	2.51 × ${10}^{-20}$
	x2	4	10	0.004364	3.86 × ${10}^{-8}$	59	120	0.014332	9.74 × ${10}^{-7}$	19	40	0.020992	5.27 × ${10}^{-7}$	56	114	0.028785	1.95 × ${10}^{-7}$
	x3	5	12	0.009166	4.62 × ${10}^{-7}$	79	160	0.020838	9.14 × ${10}^{-7}$	24	50	0.028946	8.19 × ${10}^{-7}$	7	16	0.003857	5.28 × ${10}^{-7}$
	x4	4	10	0.003387	4.2 × ${10}^{-7}$	63	128	0.015309	8.43 × ${10}^{-7}$	20	42	0.023507	5.35 × ${10}^{-7}$	59	119	0.034386	9.47 × ${10}^{-7}$
	x5	5	12	0.007451	4.72 × ${10}^{-8}$	75	152	0.018522	8.3 × ${10}^{-7}$	23	48	0.028748	9.58 × ${10}^{-7}$	62	126	0.036143	2.58 × ${10}^{-7}$
	x6	5	12	0.003156	4.83 × ${10}^{-8}$	75	152	0.018401	8.24 × ${10}^{-7}$	23	48	0.01997	9.53 × ${10}^{-7}$	85	172	0.041196	2.93 × ${10}^{-7}$
5000	x1	4	10	0.00634	4.4 × ${10}^{-8}$	71	144	0.056879	8.37 × ${10}^{-7}$	22	46	0.032142	2.34 × ${10}^{-22}$	6	14	0.013685	6.96 × ${10}^{-7}$
	x2	4	10	0.007762	3.86 × ${10}^{-8}$	59	120	0.064447	9.74 × ${10}^{-7}$	19	40	0.045592	5.27 × ${10}^{-7}$	56	114	0.1389	1.95 × ${10}^{-7}$
	x3	6	14	0.036929	1.02 × ${10}^{-8}$	83	168	0.097078	8.37 × ${10}^{-7}$	26	54	0.043952	9.45 × ${10}^{-7}$	8	18	0.017421	0
	x4	4	10	0.013407	4.21 × ${10}^{-7}$	63	128	0.066394	8.43 × ${10}^{-7}$	20	42	0.051169	5.35 × ${10}^{-7}$	47	96	0.14942	4.76 × ${10}^{-7}$
	x5	5	12	0.010295	1.06 × ${10}^{-7}$	78	158	0.11486	9.51 × ${10}^{-7}$	25	52	0.050411	5.36 × ${10}^{-7}$	84	170	0.23801	5.46 × ${10}^{-7}$
	x6	5	12	0.016684	1.07 × ${10}^{-7}$	78	158	0.15325	9.49 × ${10}^{-7}$	25	52	0.037297	5.39 × ${10}^{-7}$	58	117	0.22868	5.38 × ${10}^{-7}$
10000	x1	4	10	0.022699	6.23 × ${10}^{-8}$	72	146	0.16795	9.47 × ${10}^{-7}$	22	46	0.060396	3.31 × ${10}^{-22}$	6	14	0.020364	7.28 × ${10}^{-20}$
	x2	4	10	0.014139	3.86 × ${10}^{-8}$	59	120	0.14901	9.74 × ${10}^{-7}$	19	40	0.18271	5.27 × ${10}^{-7}$	56	114	0.3439	1.95 × ${10}^{-7}$
	x3	6	14	0.019224	1.45 × ${10}^{-8}$	84	170	0.69638	9.47 × ${10}^{-7}$	27	56	0.65826	6.68 × ${10}^{-7}$	8	18	0.030973	3.47 × ${10}^{-20}$
	x4	4	10	0.011995	4.21 × ${10}^{-7}$	63	128	0.33074	8.43 × ${10}^{-7}$	20	42	0.076416	5.35 × ${10}^{-7}$	36	74	0.25376	3.81 × ${10}^{-7}$
	x5	5	12	0.015141	1.49 × ${10}^{-7}$	80	162	0.4328	8.61 × ${10}^{-7}$	25	52	0.10034	7.58 × ${10}^{-7}$	72	146	0.50642	2.51 × ${10}^{-7}$
	x6	5	12	0.022858	1.49 × ${10}^{-7}$	80	162	0.22692	8.63 × ${10}^{-7}$	25	52	0.16107	7.59 × ${10}^{-7}$	77	156	0.49567	1.88 × ${10}^{-7}$
50000	x1	4	10	0.052651	1.39 × ${10}^{-7}$	76	154	1.2123	8.67 × ${10}^{-7}$	24	50	1.1795	6.65 × ${10}^{-7}$	7	16	0.17603	8.43 × ${10}^{-20}$
	x2	4	10	0.057156	3.86 × ${10}^{-8}$	59	120	1.0414	9.74 × ${10}^{-7}$	19	40	0.35856	5.27 × ${10}^{-7}$	56	114	1.395	1.95 × ${10}^{-7}$
	x3	6	14	0.063795	3.24 × ${10}^{-8}$	88	178	1.5448	8.67 × ${10}^{-7}$	27	56	0.41163	2.37 × ${10}^{-20}$	7	16	0.10883	4.33 × ${10}^{-18}$
	x4	4	10	0.04699	4.21 × ${10}^{-7}$	63	128	0.80096	8.43 × ${10}^{-7}$	20	42	0.2929	5.35 × ${10}^{-7}$	42	86	1.0935	9.35 × ${10}^{-7}$
	x5	5	12	0.17235	3.34 × ${10}^{-7}$	83	168	1.0549	9.86 × ${10}^{-7}$	26	54	0.46606	8.48 × ${10}^{-7}$	83	168	2.0317	3.14 × ${10}^{-7}$
	x6	5	12	0.061083	3.34 × ${10}^{-7}$	83	168	1.3178	9.87 × ${10}^{-7}$	26	54	0.88305	1.54 × ${10}^{-22}$	86	174	2.0782	4.3 × ${10}^{-7}$
100000	x1	4	10	0.13629	1.97 × ${10}^{-7}$	77	156	1.507	9.81 × ${10}^{-7}$	19	40	0.84867	3.35 × ${10}^{-20}$	7	16	0.18	3.11 × ${10}^{-7}$
	x2	4	10	0.11002	3.86 × ${10}^{-8}$	59	120	1.1762	9.74 × ${10}^{-7}$	19	40	0.49061	5.27 × ${10}^{-7}$	56	114	2.3847	1.95 × ${10}^{-7}$
	x3	6	14	0.17107	4.58 × ${10}^{-8}$	89	180	2.3631	9.81 × ${10}^{-7}$	34	70	1.5875	5.62 × ${10}^{-7}$	7	16	0.20417	5.04 × ${10}^{-18}$
	x4	4	10	0.17033	4.21 × ${10}^{-7}$	63	128	2.0171	8.43 × ${10}^{-7}$	20	42	0.45278	5.35 × ${10}^{-7}$	53	108	2.3837	2.24 × ${10}^{-7}$
	x5	5	12	0.27433	4.73 × ${10}^{-7}$	85	172	2.4078	8.92 × ${10}^{-7}$	27	56	0.78559	9.24 × ${10}^{-7}$	80	162	3.2927	3.65 × ${10}^{-7}$
	x6	5	12	0.42743	4.72 × ${10}^{-7}$	85	172	2.1616	8.94 × ${10}^{-7}$	29	60	0.69763	5.07 × ${10}^{-7}$	86	174	3.0691	2.38 × ${10}^{-7}$

,

Table 4. Test results obtained by the four solvers for Problem 4.

Problem 4		HSS				CGD				PDY				MFRM
DIM	SP	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM
1000	x1	1	3	0.022489	0	1	3	0.047719	0	1	3	0.007245	0	1	3	0.000932	0
	x2	1	3	0.002172	0	1	3	0.002429	0	1	3	0.003757	0	109	219	0.029483	9.28 × ${10}^{-7}$
	x3	1	3	0.001634	0	1	3	0.00262	0	1	3	0.002875	0	1	3	0.002245	0
	x4	3	8	0.005628	4.47 × ${10}^{-8}$	1	3	0.00244	0	5	12	0.007667	7.88 × ${10}^{-9}$	1	3	0.00235	0
	x5	5	12	0.004021	6.49 × ${10}^{-7}$	1	3	0.003671	0	29	59	0.019814	9.22 × ${10}^{-7}$	1	3	0.001477	0
	x6	5	12	0.012438	7.19 × ${10}^{-7}$	1	3	0.001087	0	24	49	0.012885	7.25 × ${10}^{-7}$	1	3	0.00134	0
5000	x1	1	3	0.005965	0	1	3	0.003018	0	1	3	0.002284	0	1	3	0.002272	0
	x2	1	3	0.004459	0	1	3	0.002205	0	1	3	0.003033	0	109	219	0.13851	9.28 × ${10}^{-7}$
	x3	1	3	0.002232	0	1	3	0.006697	0	1	3	0.003255	0	1	3	0.007835	0
	x4	3	8	0.007485	4.15 × ${10}^{-8}$	1	3	0.002504	0	5	12	0.008525	6.9 × ${10}^{-9}$	1	3	0.003338	0
	x5	6	14	0.015053	1.46 × ${10}^{-8}$	1	3	0.002627	0	25	52	0.02548	6.94 × ${10}^{-7}$	1	3	0.003799	0
	x6	6	14	0.010208	1.48 × ${10}^{-8}$	1	3	0.002331	0	26	53	0.032945	6.87 × ${10}^{-7}$	1	3	0.004136	0
10000	x1	1	3	0.004832	0	1	3	0.013794	0	1	3	0.003671	0	1	3	0.00363	0
	x2	1	3	0.003793	0	1	3	0.00365	0	1	3	0.004001	0	109	219	0.36648	9.28 × ${10}^{-7}$
	x3	1	3	0.004974	0	1	3	0.004041	0	1	3	0.005493	0	1	3	0.01389	0
	x4	3	8	0.010592	4.11 × ${10}^{-8}$	1	3	0.009375	0	5	12	0.026602	6.79 × ${10}^{-9}$	1	3	0.008508	0
	x5	6	14	0.021774	2.07 × ${10}^{-8}$	1	3	0.009331	0	27	55	0.05058	6.22 × ${10}^{-7}$	1	3	0.006177	0
	x6	6	14	0.013876	2.05 × ${10}^{-8}$	1	3	0.006686	0	23	48	0.048102	8.31 × ${10}^{-7}$	1	3	0.00721	0
50000	x1	1	3	0.021524	0	1	3	0.017893	0	1	3	0.021182	0	1	3	0.013617	0
	x2	1	3	0.05473	0	1	3	0.021253	0	1	3	0.010713	0	109	219	1.148	9.28 × ${10}^{-7}$
	x3	1	3	0.021119	0	1	3	0.013569	0	1	3	0.018747	0	1	3	0.04227	0
	x4	3	8	0.073359	4.07 × ${10}^{-8}$	1	3	0.009532	0	5	12	0.06247	6.69 × ${10}^{-9}$	1	3	0.017147	0
	x5	6	14	0.063864	4.64 × ${10}^{-8}$	1	3	0.011356	0	1	3	0.026335	0	1	3	0.020316	0
	x6	6	14	0.10304	4.7 × ${10}^{-8}$	1	3	0.008921	0	1	3	0.02759	0	1	3	0.022485	0
100000	x1	1	3	0.035424	0	1	3	0.016441	0	1	3	0.034987	0	1	3	0.024402	0
	x2	1	3	0.027929	0	1	3	0.03353	0	1	3	0.036914	0	109	219	2.2239	9.28 × ${10}^{-7}$
	x3	1	3	0.039706	0	1	3	0.017034	0	1	3	0.11907	0	1	3	0.082234	0
	x4	3	8	0.083596	4.07 × ${10}^{-8}$	1	3	0.017529	0	5	12	0.083531	6.68 × ${10}^{-9}$	1	3	0.04628	0
	x5	6	14	0.25359	6.57 × ${10}^{-8}$	1	3	0.016306	0	1	3	0.033998	0	1	3	0.039002	0
	x6	6	14	0.1416	6.95 × ${10}^{-8}$	1	3	0.031449	0	1	3	0.024931	0	1	3	0.041211	0

,

Table 5. Test results obtained by the four solvers for Problem 5.

Problem 5		HSS				CGD				PDY				MFRM
DIM	SP	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM
1000	x1	4	10	0.059751	3.96 × ${10}^{-7}$	82	166	0.049837	8.42 × ${10}^{-7}$	26	54	0.023436	6.16 × ${10}^{-7}$	68	138	0.077811	3.54 × ${10}^{-7}$
	x2	4	10	0.004665	4.11 × ${10}^{-7}$	82	166	0.036694	8.73 × ${10}^{-7}$	26	54	0.018791	6.39 × ${10}^{-7}$	74	150	0.062604	4.38 × ${10}^{-7}$
	x3	4	10	0.003302	1.09 × ${10}^{-7}$	76	154	0.058903	8.81 × ${10}^{-7}$	24	50	0.014953	6.76 × ${10}^{-7}$	64	130	0.05319	5.6 × ${10}^{-7}$
	x4	4	10	0.004825	4.1 × ${10}^{-7}$	82	166	0.036868	8.71 × ${10}^{-7}$	26	54	0.013522	6.38 × ${10}^{-7}$	78	158	0.060024	5.4 × ${10}^{-7}$
	x5	4	10	0.003849	3.39 × ${10}^{-7}$	81	164	0.031956	8.99 × ${10}^{-7}$	26	54	0.018961	5.26 × ${10}^{-7}$	75	152	0.067381	9.61 × ${10}^{-7}$
	x6	4	10	0.00315	3.39 × ${10}^{-7}$	81	164	0.077436	9.01 × ${10}^{-7}$	26	54	0.014281	5.27 × ${10}^{-7}$	54	110	0.060038	7.5 × ${10}^{-7}$
5000	x1	4	10	0.012654	8.89 × ${10}^{-7}$	85	172	0.15576	9.65 × ${10}^{-7}$	27	56	0.081796	6.9 × ${10}^{-7}$	54	110	0.24452	8.65 × ${10}^{-7}$
	x2	4	10	0.011453	9.23 × ${10}^{-7}$	86	174	0.4407	8.01 × ${10}^{-7}$	27	56	0.068774	7.16 × ${10}^{-7}$	58	118	0.35362	8.98 × ${10}^{-7}$
	x3	4	10	0.011682	2.44 × ${10}^{-7}$	80	162	0.33484	8.08 × ${10}^{-7}$	25	52	0.067068	7.57 × ${10}^{-7}$	43	88	0.25534	7.14 × ${10}^{-7}$
	x4	4	10	0.013908	9.23 × ${10}^{-7}$	86	174	0.24378	8.01 × ${10}^{-7}$	27	56	0.088127	7.16 × ${10}^{-7}$	63	128	0.30915	7.22 × ${10}^{-7}$
	x5	4	10	0.011849	7.6 × ${10}^{-7}$	85	172	0.15641	8.24 × ${10}^{-7}$	27	56	0.083818	5.89 × ${10}^{-7}$	55	112	0.28214	7.38 × ${10}^{-7}$
	x6	4	10	0.013519	7.61 × ${10}^{-7}$	85	172	0.21864	8.24 × ${10}^{-7}$	27	56	0.17961	5.9 × ${10}^{-7}$	87	176	0.33912	9.84 × ${10}^{-7}$
10000	x1	5	12	0.049344	6.35 × ${10}^{-7}$	87	176	0.32399	8.73 × ${10}^{-7}$	28	58	0.33859	7.32 × ${10}^{-7}$	51	104	0.62071	7.26 × ${10}^{-7}$
	x2	5	12	0.054254	6.59 × ${10}^{-7}$	87	176	0.56731	9.06 × ${10}^{-7}$	29	60	0.28634	5.7 × ${10}^{-7}$	49	100	0.49179	8.68 × ${10}^{-7}$
	x3	4	10	0.025027	3.45 × ${10}^{-7}$	81	164	0.81926	9.14 × ${10}^{-7}$	26	54	0.13539	5.35 × ${10}^{-7}$	58	118	0.53457	9.29 × ${10}^{-7}$
	x4	5	12	0.037107	6.59 × ${10}^{-7}$	87	176	0.33429	9.06 × ${10}^{-7}$	29	60	0.18407	5.69 × ${10}^{-7}$	48	98	0.58512	8.06 × ${10}^{-7}$
	x5	5	12	0.029731	5.43 × ${10}^{-7}$	86	174	0.31597	9.33 × ${10}^{-7}$	28	58	0.18179	6.25 × ${10}^{-7}$	78	158	0.7064	6.91 × ${10}^{-7}$
	x6	5	12	0.030679	5.41 × ${10}^{-7}$	86	174	0.34123	9.33 × ${10}^{-7}$	28	58	0.13266	6.26 × ${10}^{-7}$	59	120	0.60942	5.85 × ${10}^{-7}$
50000	x1	6	14	0.13438	7.17 × ${10}^{-7}$	90	182	1.9581	1 × ${10}^{-6}$	32	66	1.3355	0	62	126	2.0853	6.8 × ${10}^{-7}$
	x2	6	14	0.14676	7.45 × ${10}^{-7}$	91	184	1.4814	8.3 × ${10}^{-7}$	33	68	0.71451	0	59	120	1.9564	9.73 × ${10}^{-7}$
	x3	4	10	0.083175	7.72 × ${10}^{-7}$	85	172	1.5701	8.37 × ${10}^{-7}$	26	54	0.69494	0	43	88	1.5166	4.88 × ${10}^{-7}$
	x4	6	14	0.14168	7.45 × ${10}^{-7}$	91	184	1.8901	8.3 × ${10}^{-7}$	33	68	1.1252	0	46	94	1.7868	4.16 × ${10}^{-7}$
	x5	6	14	0.20631	6.13 × ${10}^{-7}$	90	182	1.2432	8.54 × ${10}^{-7}$	31	64	0.60108	0	67	136	1.7509	6.22 × ${10}^{-7}$
	x6	6	14	0.15371	6.13 × ${10}^{-7}$	90	182	2.031	8.54 × ${10}^{-7}$	31	64	0.96708	0	48	98	1.4123	7.24 × ${10}^{-7}$
100000	x1	7	16	0.36536	5.12 × ${10}^{-7}$	92	186	3.4223	9.05 × ${10}^{-7}$	34	70	2.0212	0	37	76	2.2322	8.4 × ${10}^{-7}$
	x2	7	16	0.41608	5.32 × ${10}^{-7}$	92	186	3.4177	9.39 × ${10}^{-7}$	35	72	2.3869	0	66	134	4.3938	9.15 × ${10}^{-7}$
	x3	5	12	0.26751	5.51 × ${10}^{-7}$	86	174	3.1756	9.47 × ${10}^{-7}$	26	54	1.3934	0	34	70	2.8543	7.66 × ${10}^{-7}$
	x4	7	16	0.36165	5.32 × ${10}^{-7}$	92	186	2.9337	9.39 × ${10}^{-7}$	35	72	1.998	0	57	116	2.9496	9.55 × ${10}^{-7}$
	x5	6	14	0.41128	8.67 × ${10}^{-7}$	91	184	2.3545	9.66 × ${10}^{-7}$	33	68	2.1747	0	71	144	3.5477	6.17 × ${10}^{-7}$
	x6	6	14	0.27328	8.67 × ${10}^{-7}$	91	184	2.3414	9.66 × ${10}^{-7}$	33	68	2.2056	0	59	120	3.2639	6.57 × ${10}^{-7}$

,

Table 6. Test results obtained by the four solvers for Problem 6.

Problem 6		HSS				CGD				PDY				MFRM
DIM	SP	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM
1000	x1	5	12	0.030248	3.21 × ${10}^{-8}$	36	74	0.032352	9.48 × ${10}^{-7}$	6	14	0.006658	2.09 × ${10}^{-7}$	3	8	0.00372	3.24 × ${10}^{-7}$
	x2	6	14	0.004253	4.69 × ${10}^{-7}$	37	76	0.010311	7.65 × ${10}^{-7}$	34	70	0.018938	6.1 × ${10}^{-7}$	86	174	0.068292	7.13 × ${10}^{-7}$
	x3	5	12	0.004081	2.21 × ${10}^{-7}$	36	74	0.010483	9.07 × ${10}^{-7}$	6	14	0.005091	6.55 × ${10}^{-7}$	4	10	0.004645	6.55 × ${10}^{-8}$
	x4	10	22	0.014077	1.03 × ${10}^{-8}$	37	76	0.010188	7.56 × ${10}^{-7}$	33	68	0.013095	5.47 × ${10}^{-7}$	63	128	0.0778	8.47 × ${10}^{-7}$
	x5	6	14	0.006538	2.76 × ${10}^{-7}$	36	74	0.010269	6.45 × ${10}^{-7}$	48	98	0.018494	8.73 × ${10}^{-7}$	80	162	0.10296	3.08 × ${10}^{-7}$
	x6	6	14	0.005977	2.91 × ${10}^{-7}$	36	74	0.012178	6.54 × ${10}^{-7}$	52	106	0.02832	3.6 × ${10}^{-7}$	88	178	0.12078	8.96 × ${10}^{-7}$
5000	x1	5	12	0.024024	7.18 × ${10}^{-8}$	38	78	0.044492	8.3 × ${10}^{-7}$	6	14	0.014241	4.68 × ${10}^{-7}$	3	8	0.018603	7.25 × ${10}^{-7}$
	x2	6	14	0.018634	6.56 × ${10}^{-7}$	39	80	0.059781	6.7 × ${10}^{-7}$	35	72	0.084409	5.59 × ${10}^{-7}$	69	140	0.39768	6.38 × ${10}^{-7}$
	x3	5	12	0.017453	4.95 × ${10}^{-7}$	38	78	0.06979	7.94 × ${10}^{-7}$	7	16	0.02862	9.35 × ${10}^{-8}$	4	10	0.017763	1.46 × ${10}^{-7}$
	x4	8	18	0.026507	5.07 × ${10}^{-7}$	39	80	0.053907	6.68 × ${10}^{-7}$	36	74	0.15347	6.96 × ${10}^{-7}$	71	144	0.47127	9.1 × ${10}^{-7}$
	x5	6	14	0.019105	6.22 × ${10}^{-7}$	37	76	0.063182	9.02 × ${10}^{-7}$	34	70	0.13452	7.37 × ${10}^{-7}$	85	172	0.66379	3.47 × ${10}^{-7}$
	x6	6	14	0.014968	6.44 × ${10}^{-7}$	37	76	0.051971	9.06 × ${10}^{-7}$	48	98	0.22496	9.43 × ${10}^{-7}$	83	168	0.55329	9.71 × ${10}^{-7}$
10000	x1	5	12	0.023248	1.02 × ${10}^{-7}$	39	80	0.098655	7.34 × ${10}^{-7}$	6	14	0.0289	6.62 × ${10}^{-7}$	4	10	0.044346	5.12 × ${10}^{-9}$
	x2	6	14	0.027323	7.49 × ${10}^{-7}$	39	80	0.10691	9.48 × ${10}^{-7}$	16	34	0.058902	8.16 × ${10}^{-7}$	48	98	0.55498	7.33 × ${10}^{-7}$
	x3	5	12	0.02135	7 × ${10}^{-7}$	39	80	0.10212	7.02 × ${10}^{-7}$	7	16	0.029555	1.36 × ${10}^{-7}$	4	10	0.035127	2.07 × ${10}^{-7}$
	x4	8	18	0.030169	4.59 × ${10}^{-7}$	39	80	0.22112	9.46 × ${10}^{-7}$	35	72	0.1597	5.62 × ${10}^{-7}$	83	168	0.87343	6.35 × ${10}^{-7}$
	x5	6	14	0.028248	8.8 × ${10}^{-7}$	38	78	0.32903	7.98 × ${10}^{-7}$	40	82	0.13693	6.2 × ${10}^{-7}$	83	168	0.80412	7.74 × ${10}^{-7}$
	x6	6	14	0.026041	7.92 × ${10}^{-7}$	38	78	0.2385	8.04 × ${10}^{-7}$	42	86	0.2604	7.67 × ${10}^{-7}$	79	160	0.89436	7.84 × ${10}^{-7}$
50000	x1	5	12	0.15962	2.27 × ${10}^{-7}$	41	84	0.41018	6.42 × ${10}^{-7}$	7	16	0.16754	9.46 × ${10}^{-8}$	4	10	0.14045	1.15 × ${10}^{-8}$
	x2	6	14	0.12	9.08 × ${10}^{-7}$	41	84	0.48069	8.3 × ${10}^{-7}$	28	58	0.67966	7.57 × ${10}^{-7}$	84	170	2.9466	2.31 × ${10}^{-7}$
	x3	6	14	0.25283	8.32 × ${10}^{-9}$	40	82	0.55524	9.82 × ${10}^{-7}$	8	18	0.1135	2.69 × ${10}^{-7}$	4	10	0.13051	4.63 × ${10}^{-7}$
	x4	8	18	0.11363	4.12 × ${10}^{-7}$	41	84	0.73687	8.29 × ${10}^{-7}$	26	54	0.34848	1.44 × ${10}^{-7}$	105	212	3.7842	6.72 × ${10}^{-7}$
	x5	7	16	0.1164	1.05 × ${10}^{-8}$	40	82	0.41344	6.98 × ${10}^{-7}$	37	76	0.53249	7.23 × ${10}^{-7}$	86	174	3.0183	5.09 × ${10}^{-7}$
	x6	7	16	0.11197	1.04 × ${10}^{-8}$	40	82	0.47039	6.99 × ${10}^{-7}$	50	102	1.4389	7.13 × ${10}^{-7}$	88	178	2.9197	3.2 × ${10}^{-7}$
100000	x1	5	12	0.3068	3.21 × ${10}^{-7}$	41	84	1.417	9.08 × ${10}^{-7}$	7	16	0.18772	8.58 × ${10}^{-7}$	4	10	0.21746	1.62 × ${10}^{-8}$
	x2	6	14	0.56886	9.63 × ${10}^{-7}$	42	86	0.81291	7.34 × ${10}^{-7}$	35	72	1.0428	7.61 × ${10}^{-7}$	-	-	-	-
	x3	6	14	0.1754	1.18 × ${10}^{-8}$	41	84	0.88265	8.69 × ${10}^{-7}$	8	18	0.36603	3.81 × ${10}^{-7}$	4	10	0.18537	6.55 × ${10}^{-7}$
	x4	8	18	0.2628	4.34 × ${10}^{-7}$	42	86	1.285	7.34 × ${10}^{-7}$	29	60	1.0324	5.25 × ${10}^{-7}$	92	186	5.9597	7.9 × ${10}^{-7}$
	x5	7	16	0.21732	1.48 × ${10}^{-8}$	40	82	0.69398	9.87 × ${10}^{-7}$	35	72	1.1286	4.43 × ${10}^{-7}$	116	234	6.096	9.91 × ${10}^{-8}$
	x6	7	16	0.28834	1.52 × ${10}^{-8}$	40	82	1.4087	9.87 × ${10}^{-7}$	50	102	1.9037	6.08 × ${10}^{-7}$	87	176	4.7662	9.35 × ${10}^{-7}$

,

Table 7. Test results obtained by the four solvers for Problem 7.

Problem 7		HSS				CGD				PDY				MFRM
DIM	SP	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM
1000	x1	4	10	0.012183	1.68 × ${10}^{-8}$	151	304	0.18691	9.17 × ${10}^{-7}$	16	34	0.014957	8.17 × ${10}^{-7}$	6	14	0.012322	9.16 × ${10}^{-8}$
	x2	5	11	0.004785	1.65 × ${10}^{-7}$	133	268	0.056032	9.21 × ${10}^{-7}$	15	31	0.011109	7.97 × ${10}^{-7}$	39	79	0.065169	8.34 × ${10}^{-7}$
	x3	1	3	0.001547	0	2	5	0.004122	0	18	38	0.013079	8.51 × ${10}^{-7}$	1	3	0.002491	0
	x4	7	15	0.004476	7.97 × ${10}^{-8}$	140	282	0.046527	9.19 × ${10}^{-7}$	17	36	0.011909	4.98 × ${10}^{-7}$	273	547	6.0835	2.24 × ${10}^{-10}$
	x5	10	21	0.012394	2.24 × ${10}^{-9}$	164	330	0.056094	9.22 × ${10}^{-7}$	19	40	0.018864	4.77 × ${10}^{-7}$	-	-	-	-
	x6	10	21	0.010066	6.38 × ${10}^{-7}$	164	330	0.067306	9.42 × ${10}^{-7}$	19	40	0.014743	4.64 × ${10}^{-7}$	358	717	4.6658	7.11 × ${10}^{-7}$
5000	x1	4	10	0.11789	3.76 × ${10}^{-8}$	158	318	0.21518	9.8 × ${10}^{-7}$	17	36	0.073395	6.85 × ${10}^{-7}$	6	14	0.042878	2.05 × ${10}^{-7}$
	x2	5	11	0.015099	1.65 × ${10}^{-7}$	133	268	0.17588	9.21 × ${10}^{-7}$	15	31	0.039081	7.97 × ${10}^{-7}$	39	79	0.25795	8.34 × ${10}^{-7}$
	x3	6	14	0.037396	1.09 × ${10}^{-7}$	2	5	0.00964	0	20	42	0.060058	8.59 × ${10}^{-7}$	1	3	0.006658	0
	x4	7	15	0.032192	7.96 × ${10}^{-8}$	140	282	0.59813	9.19 × ${10}^{-7}$	17	36	0.068599	4.99 × ${10}^{-7}$	229	459	82.1077	0
	x5	10	21	0.020827	7.11 × ${10}^{-7}$	171	344	0.46259	9.87 × ${10}^{-7}$	20	42	0.068094	4.02 × ${10}^{-7}$	172	345	21.112	0
	x6	12	25	0.028397	8.18 × ${10}^{-9}$	171	344	0.24954	9.82 × ${10}^{-7}$	20	42	0.11606	4.01 × ${10}^{-7}$	211	423	92.8425	0
10000	x1	4	10	0.017055	5.32 × ${10}^{-8}$	162	326	0.45674	9.1 × ${10}^{-7}$	17	36	0.19021	9.69 × ${10}^{-7}$	6	14	0.11361	2.9 × ${10}^{-7}$
	x2	5	11	0.01981	1.65 × ${10}^{-7}$	133	268	0.56473	9.21 × ${10}^{-7}$	15	31	0.16351	7.97 × ${10}^{-7}$	39	79	0.54726	8.34 × ${10}^{-7}$
	x3	6	14	0.064627	1.55 × ${10}^{-7}$	2	5	0.016405	0	21	44	0.22851	4.56 × ${10}^{-7}$	1	3	0.016089	0
	x4	7	15	0.025851	7.96 × ${10}^{-8}$	140	282	0.8344	9.19 × ${10}^{-7}$	17	36	0.085903	4.99 × ${10}^{-7}$	850	1701	193.6507	0
	x5	11	23	0.32958	6.94 × ${10}^{-9}$	175	352	0.49858	9.16 × ${10}^{-7}$	20	42	0.10045	5.69 × ${10}^{-7}$	-	-	-	-
	x6	10	21	0.076488	3.74 × ${10}^{-7}$	175	352	0.5223	9.16 × ${10}^{-7}$	20	42	0.10389	5.68 × ${10}^{-7}$	82	165	6.8805	0
50000	x1	4	10	0.078496	1.19 × ${10}^{-7}$	169	340	2.5024	9.73 × ${10}^{-7}$	18	38	0.6056	8.13 × ${10}^{-7}$	6	14	0.37763	6.48 × ${10}^{-7}$
	x2	5	11	0.099397	1.65 × ${10}^{-7}$	133	268	2.1159	9.21 × ${10}^{-7}$	15	31	0.68363	7.97 × ${10}^{-7}$	39	79	2.5718	8.34 × ${10}^{-7}$
	x3	6	14	0.15118	3.46 × ${10}^{-7}$	2	5	0.026231	0	23	48	0.61079	9.93 × ${10}^{-7}$	1	3	0.058223	0
	x4	7	15	0.10366	7.96 × ${10}^{-8}$	140	282	2.1722	9.19 × ${10}^{-7}$	17	36	0.39142	4.99 × ${10}^{-7}$	47	95	17.9721	5.55 × ${10}^{-9}$
	x5	11	23	0.35229	3.92 × ${10}^{-7}$	182	366	2.3322	9.79 × ${10}^{-7}$	20	42	0.62861	7.76 × ${10}^{-7}$	-	-	-	-
	x6	12	25	0.18608	1.01 × ${10}^{-8}$	182	366	2.4855	9.81 × ${10}^{-7}$	20	42	0.92	7.75 × ${10}^{-7}$	-	-	-	-
100000	x1	4	10	0.20729	1.68 × ${10}^{-7}$	173	348	4.6402	9.03 × ${10}^{-7}$	19	40	0.75335	4.31 × ${10}^{-7}$	-	-	-	-
	x2	5	11	0.14682	1.65 × ${10}^{-7}$	133	268	2.9435	9.21 × ${10}^{-7}$	15	31	0.8933	7.97 × ${10}^{-7}$	-	-	-	-
	x3	6	14	0.19741	4.89 × ${10}^{-7}$	2	5	0.045153	0	27	56	1.7879	4.72 × ${10}^{-7}$	-	-	-	-
	x4	7	15	0.20939	7.96 × ${10}^{-8}$	140	282	3.452	9.19 × ${10}^{-7}$	17	36	0.92705	4.99 × ${10}^{-7}$	-	-	-	-
	x5	12	25	0.60932	6.89 × ${10}^{-9}$	186	374	5.0285	9.09 × ${10}^{-7}$	21	44	1.23	4.11 × ${10}^{-7}$	-	-	-	-
	x6	13	27	0.3519	1.84 × ${10}^{-8}$	186	374	4.6665	9.08 × ${10}^{-7}$	21	44	0.93468	4.11 × ${10}^{-7}$	-	-	-	-

,

Table 8. Test results obtained by the four solvers for Problem 8.

Problem 8		HSS				CGD				PDY				MFRM
DIM	SP	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM
1000	x1	66	134	0.24751	9.78 × ${10}^{-7}$	-	-	-	-	-	-	-	-	-	-	-	-
	x2	27	56	0.034158	9.5 × ${10}^{-7}$	808	1618	0.31885	9.99 × ${10}^{-7}$	-	-	-	-	-	-	-	-
	x3	1	2	0.003785	0	2	5	0.001531	0	1	2	0.001223	0	1	2	0.006734	0
	x4	67	136	0.049339	9.88 × ${10}^{-7}$	-	-	-	-	-	-	-	-	67	135	0.035797	5.66 × ${10}^{-7}$
	x5	73	148	0.0461	9.68 × ${10}^{-7}$	-	-	-	-	-	-	-	-	64	129	0.065585	9.67 × ${10}^{-7}$
	x6	72	146	0.04761	9.93 × ${10}^{-7}$	-	-	-	-	-	-	-	-	63	127	0.035655	9.71 × ${10}^{-7}$
5000	x1	94	190	0.54224	9.91 × ${10}^{-7}$	-	-	-	-	-	-	-	-	-	-	-	-
	x2	27	56	0.062239	9.5 × ${10}^{-7}$	808	1618	1.2269	9.99 × ${10}^{-7}$	-	-	-	-	-	-	-	-
	x3	1	2	0.002594	0	2	5	0.012859	0	1	2	0.005997	0	1	2	0.00257	0
	x4	80	162	0.38038	9.91 × ${10}^{-7}$	-	-	-	-	-	-	-	-	73	147	0.18682	9.29 × ${10}^{-7}$
	x5	101	204	0.43745	9.83 × ${10}^{-7}$	-	-	-	-	-	-	-	-	108	217	0.30825	9.98 × ${10}^{-7}$
	x6	101	204	0.31897	9.88 × ${10}^{-7}$	-	-	-	-	-	-	-	-	108	217	0.28176	9.91 × ${10}^{-7}$
10000	x1	110	222	0.75291	9.94 × ${10}^{-7}$	-	-	-	-	-	-	-	-	-	-	-	-
	x2	27	56	0.1057	9.5 × ${10}^{-7}$	808	1618	3.0397	9.99 × ${10}^{-7}$	-	-	-	-	-	-	-	-
	x3	1	2	0.003731	0	2	5	0.009001	0	1	2	0.007766	0	1	2	0.003949	0
	x4	83	168	0.4733	9.88 × ${10}^{-7}$	-	-	-	-	-	-	-	-	74	149	0.4244	9.69 × ${10}^{-7}$
	x5	117	236	0.76712	9.86 × ${10}^{-7}$	-	-	-	-	-	-	-	-	152	305	0.70872	9.97 × ${10}^{-7}$
	x6	117	236	0.82138	9.85 × ${10}^{-7}$	-	-	-	-	-	-	-	-	153	307	0.702	9.95 × ${10}^{-7}$
50000	x1	160	322	4.4256	9.95 × ${10}^{-7}$	-	-	-	-	-	-	-	-	-	-	-	-
	x2	27	56	0.52296	9.5 × ${10}^{-7}$	808	1618	9.7793	9.99 × ${10}^{-7}$	-	-	-	-	-	-	-	-
	x3	1	2	0.016082	0	2	5	0.069327	0	1	2	0.019848	0	1	2	0.010272	0
	x4	84	170	2.3099	9.99 × ${10}^{-7}$	-	-	-	-	-	-	-	-	75	151	1.7006	9.31 × ${10}^{-7}$
	x5	166	334	4.1716	9.99 × ${10}^{-7}$	-	-	-	-	-	-	-	-	396	793	8.1566	9.99 × ${10}^{-7}$
	x6	166	334	4.2682	9.99 × ${10}^{-7}$	-	-	-	-	-	-	-	-	396	793	6.9611	9.99 × ${10}^{-7}$
100000	x1	189	380	8.5193	9.9 × ${10}^{-7}$	-	-	-	-	-	-	-	-	-	-	-	-
	x2	27	56	0.84001	9.5 × ${10}^{-7}$	808	1618	17.381	9.99 × ${10}^{-7}$	-	-	-	-	-	-	-	-
	x3	1	2	0.033166	0	2	5	0.12617	0	1	2	0.01928	0	1	2	0.029227	0
	x4	85	172	6.6857	9.79 × ${10}^{-7}$	-	-	-	-	-	-	-	-	75	151	3.7352	9.32 × ${10}^{-7}$
	x5	195	392	11.7601	9.93 × ${10}^{-7}$	-	-	-	-	-	-	-	-	623	1247	21.2654	1 × ${10}^{-6}$
	x6	195	392	7.9429	9.93 × ${10}^{-7}$	-	-	-	-	-	-	-	-	624	1249	21.5608	9.99 × ${10}^{-7}$

,

Table 9. Test results obtained by the four solvers for Problem 9.

Problem 9		HSS				CGD				PDY				MFRM
DIM	SP	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM
1000	x1	61	124	0.066702	9.54 × ${10}^{-7}$	67	136	0.099921	7.96 × ${10}^{-7}$	139	280	0.076923	9.73 × ${10}^{-7}$	317	636	0.71829	9.8 × ${10}^{-7}$
	x2	31	64	0.018303	8.25 × ${10}^{-7}$	35	72	0.043891	8.99 × ${10}^{-7}$	187	376	0.09677	8.84 × ${10}^{-7}$	245	492	0.52225	9.87 × ${10}^{-7}$
	x3	52	106	0.029299	7.74 × ${10}^{-7}$	92	186	0.10058	9.64 × ${10}^{-7}$	227	456	0.12142	9.23 × ${10}^{-7}$	291	584	0.6824	9.91 × ${10}^{-7}$
	x4	36	74	0.017934	9.87 × ${10}^{-7}$	51	104	0.018526	8.96 × ${10}^{-7}$	218	438	0.11408	9.53 × ${10}^{-7}$	282	566	0.94291	9.88 × ${10}^{-7}$
	x5	49	100	0.023288	9.36 × ${10}^{-7}$	98	198	0.038489	9.43 × ${10}^{-7}$	233	468	0.22177	9.99 × ${10}^{-7}$	320	642	1.3394	9.96 × ${10}^{-7}$
	x6	52	106	0.029525	8.02 × ${10}^{-7}$	139	280	0.080835	9.97 × ${10}^{-7}$	188	378	0.11787	9.81 × ${10}^{-7}$	-	-	-	-
5000	x1	63	128	0.32998	8.55 × ${10}^{-7}$	69	140	0.089325	9.55 × ${10}^{-7}$	188	378	0.57537	8.86 × ${10}^{-7}$	295	592	3.8478	9.96 × ${10}^{-7}$
	x2	31	64	0.18052	8.25 × ${10}^{-7}$	35	72	0.059832	8.99 × ${10}^{-7}$	187	376	1.2573	8.84 × ${10}^{-7}$	245	492	2.4301	9.87 × ${10}^{-7}$
	x3	66	134	0.26308	8.96 × ${10}^{-7}$	84	170	0.13572	9.76 × ${10}^{-7}$	277	556	0.8517	9.68 × ${10}^{-7}$	306	614	3.3586	9.83 × ${10}^{-7}$
	x4	36	74	0.1387	9.89 × ${10}^{-7}$	51	104	0.09048	8.94 × ${10}^{-7}$	218	438	1.1212	9.56 × ${10}^{-7}$	282	566	2.8587	9.88 × ${10}^{-7}$
	x5	60	122	0.35995	7.44 × ${10}^{-7}$	87	176	0.5147	8.48 × ${10}^{-7}$	181	364	0.76997	9.64 × ${10}^{-7}$	385	771	4.8374	9.86 × ${10}^{-7}$
	x6	54	110	0.22668	8.29 × ${10}^{-7}$	115	232	0.48916	8.87 × ${10}^{-7}$	199	400	0.66965	9.62 × ${10}^{-7}$	-	-	-	-
10000	x1	65	132	0.57593	9.3 × ${10}^{-7}$	71	144	0.2565	9.49 × ${10}^{-7}$	193	388	2.0299	9.37 × ${10}^{-7}$	291	584	6.5063	9.97 × ${10}^{-7}$
	x2	31	64	0.19486	8.25 × ${10}^{-7}$	35	72	0.11428	8.99 × ${10}^{-7}$	187	376	1.1546	8.84 × ${10}^{-7}$	245	492	5.7929	9.87 × ${10}^{-7}$
	x3	71	144	0.58288	7.63 × ${10}^{-7}$	83	168	0.30524	9.96 × ${10}^{-7}$	220	442	2.048	9.39 × ${10}^{-7}$	313	628	9.0926	9.72 × ${10}^{-7}$
	x4	36	74	0.25617	9.89 × ${10}^{-7}$	51	104	0.18279	8.94 × ${10}^{-7}$	218	438	2.1529	9.56 × ${10}^{-7}$	282	566	7.5672	9.88 × ${10}^{-7}$
	x5	64	130	0.44209	8.52 × ${10}^{-7}$	88	178	0.6975	8.93 × ${10}^{-7}$	232	466	1.4547	9.66 × ${10}^{-7}$	385	771	13.336	9.98 × ${10}^{-7}$
	x6	55	112	0.31903	8.87 × ${10}^{-7}$	121	244	0.69565	9.14 × ${10}^{-7}$	202	406	1.9326	9.15 × ${10}^{-7}$	-	-	-	-
50000	x1	56	114	1.443	9.12 × ${10}^{-7}$	75	152	1.0305	9.7 × ${10}^{-7}$	190	382	4.94	9.44 × ${10}^{-7}$	292	586	22.2723	9.85 × ${10}^{-7}$
	x2	31	64	0.6458	8.25 × ${10}^{-7}$	35	72	0.77561	8.99 × ${10}^{-7}$	187	376	4.2758	8.84 × ${10}^{-7}$	245	492	18.3378	9.87 × ${10}^{-7}$
	x3	77	156	2.3404	9.2 × ${10}^{-7}$	83	168	1.4405	9.09 × ${10}^{-7}$	233	468	6.0204	9.9 × ${10}^{-7}$	313	628	31.4896	9.86 × ${10}^{-7}$
	x4	36	74	0.76958	9.89 × ${10}^{-7}$	51	104	0.9568	8.94 × ${10}^{-7}$	218	438	5.508	9.56 × ${10}^{-7}$	282	566	21.0092	9.88 × ${10}^{-7}$
	x5	77	156	1.839	7.95 × ${10}^{-7}$	81	164	1.4263	8.13 × ${10}^{-7}$	238	478	6.0323	9.93 × ${10}^{-7}$	477	956	66.1866	3.76 × ${10}^{-7}$
	x6	59	120	1.4313	6.21 × ${10}^{-7}$	130	262	2.69	9.73 × ${10}^{-7}$	207	416	5.3511	9.34 × ${10}^{-7}$	-	-	-	-
100000	x1	56	114	2.7481	9.28 × ${10}^{-7}$	77	156	2.7769	8.94 × ${10}^{-7}$	197	396	9.2178	9.98 × ${10}^{-7}$	290	582	44.5019	9.93 × ${10}^{-7}$
	x2	31	64	1.4145	8.25 × ${10}^{-7}$	35	72	0.97134	8.99 × ${10}^{-7}$	187	376	8.4259	8.84 × ${10}^{-7}$	245	492	36.7053	9.87 × ${10}^{-7}$
	x3	92	186	5.4545	8.29 × ${10}^{-7}$	85	172	3.0767	9.13 × ${10}^{-7}$	184	370	8.5041	9.73 × ${10}^{-7}$	357	716	118.6675	9.98 × ${10}^{-7}$
	x4	36	74	1.654	9.89 × ${10}^{-7}$	51	104	2.0814	8.94 × ${10}^{-7}$	218	438	10.4207	9.56 × ${10}^{-7}$	282	566	43.7452	9.88 × ${10}^{-7}$
	x5	69	140	4.4259	8.51 × ${10}^{-7}$	83	168	2.9639	8.07 × ${10}^{-7}$	257	516	12.9142	9.96 × ${10}^{-7}$	331	664	111.4667	9.84 × ${10}^{-7}$
	x6	59	120	2.7119	8.79 × ${10}^{-7}$	141	284	5.8394	8.87 × ${10}^{-7}$	206	414	10.0669	9.33 × ${10}^{-7}$	-	-	-	-

,

Table 10. Test results obtained by the four solvers for Problem 10.

Problem 11		HSS				CGD				PDY				MFRM
DIM	SP	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM
1000	x1	72	146	0.046063	9.69 × ${10}^{-7}$	38	78	0.13552	5.47 × ${10}^{-7}$	225	452	0.09038	9.68 × ${10}^{-7}$	41	84	0.063262	8.97 × ${10}^{-7}$
	x2	69	140	0.026	9.32 × ${10}^{-7}$	37	76	0.024512	6.72 × ${10}^{-7}$	205	412	0.080801	9.84 × ${10}^{-7}$	46	94	0.064366	8.96 × ${10}^{-7}$
	x3	77	156	0.027549	9.89 × ${10}^{-7}$	40	82	0.012066	8.38 × ${10}^{-7}$	152	306	0.060964	9.82 × ${10}^{-7}$	47	96	0.065376	7.43 × ${10}^{-7}$
	x4	63	128	0.02025	9.03 × ${10}^{-7}$	42	86	0.013116	6.97 × ${10}^{-7}$	226	454	0.089011	9.59 × ${10}^{-7}$	39	80	0.05465	8.98 × ${10}^{-7}$
	x5	73	148	0.024453	9.01 × ${10}^{-7}$	37	76	0.016001	9.83 × ${10}^{-7}$	204	410	0.082852	9.77 × ${10}^{-7}$	38	78	0.054682	6.94 × ${10}^{-7}$
	x6	93	188	0.029533	9.47 × ${10}^{-7}$	45	92	0.037255	9.99 × ${10}^{-7}$	328	658	0.14417	9.93 × ${10}^{-7}$	47	96	0.1194	8.09 × ${10}^{-7}$
5000	x1	69	140	0.18051	8.25 × ${10}^{-7}$	37	76	0.072643	7.15 × ${10}^{-7}$	208	418	0.38838	9.98 × ${10}^{-7}$	37	76	0.2563	7.23 × ${10}^{-7}$
	x2	75	152	0.13023	8.3 × ${10}^{-7}$	37	76	0.044212	4.24 × ${10}^{-7}$	208	418	0.65663	9.66 × ${10}^{-7}$	38	78	0.2476	9 × ${10}^{-7}$
	x3	83	168	0.12786	9.58 × ${10}^{-7}$	46	94	0.079937	8.06 × ${10}^{-7}$	157	316	0.84669	9.77 × ${10}^{-7}$	44	90	0.29073	9.45 × ${10}^{-7}$
	x4	66	134	0.14343	8.4 × ${10}^{-7}$	31	64	0.027742	5.17 × ${10}^{-7}$	202	406	0.41872	9.74 × ${10}^{-7}$	43	88	0.30094	4.26 × ${10}^{-7}$
	x5	76	154	0.11437	9.54 × ${10}^{-7}$	41	84	0.058961	4.94 × ${10}^{-7}$	205	412	0.39337	9.48 × ${10}^{-7}$	47	96	0.50356	8.33 × ${10}^{-7}$
	x6	98	198	0.16855	8.42 × ${10}^{-7}$	50	102	0.070835	7.33 × ${10}^{-7}$	351	704	1.3398	9.62 × ${10}^{-7}$	50	102	0.43595	3.95 × ${10}^{-7}$
10000	x1	74	150	0.31335	8.07 × ${10}^{-7}$	41	84	0.11908	3.11 × ${10}^{-7}$	219	440	1.3276	9.71 × ${10}^{-7}$	41	84	0.85407	4.69 × ${10}^{-7}$
	x2	77	156	0.33062	9.84 × ${10}^{-7}$	42	86	0.14335	7.17 × ${10}^{-7}$	200	402	1.8449	9.98 × ${10}^{-7}$	47	96	0.98298	6.67 × ${10}^{-7}$
	x3	73	148	0.2738	9.79 × ${10}^{-7}$	39	80	0.12366	6.46 × ${10}^{-7}$	148	298	0.71134	9.58 × ${10}^{-7}$	45	92	0.89528	8.1 × ${10}^{-7}$
	x4	77	156	0.28779	9.88 × ${10}^{-7}$	39	80	0.12037	4.26 × ${10}^{-7}$	222	446	1.9026	9.6 × ${10}^{-7}$	41	84	1.0111	9.98 × ${10}^{-7}$
	x5	79	160	0.30745	9.61 × ${10}^{-7}$	35	72	0.10851	9.48 × ${10}^{-7}$	197	396	0.93803	9.86 × ${10}^{-7}$	36	74	0.78185	9.23 × ${10}^{-7}$
	x6	101	204	0.44826	9.82 × ${10}^{-7}$	51	104	0.14368	6.93 × ${10}^{-7}$	348	698	2.515	9.97 × ${10}^{-7}$	42	86	0.88774	5.76 × ${10}^{-7}$
50000	x1	80	162	1.7087	7.83 × ${10}^{-7}$	41	84	0.49621	4.59 × ${10}^{-7}$	204	410	5.1793	9.76 × ${10}^{-7}$	40	82	3.1302	4.85 × ${10}^{-7}$
	x2	81	164	2.2268	9.19 × ${10}^{-7}$	41	84	0.46078	2.73 × ${10}^{-7}$	201	404	4.2643	9.87 × ${10}^{-7}$	46	94	3.4281	6.69 × ${10}^{-7}$
	x3	76	154	1.742	9.9 × ${10}^{-7}$	42	86	0.56419	9.12 × ${10}^{-7}$	152	306	2.9933	9.9 × ${10}^{-7}$	49	100	3.3687	7.99 × ${10}^{-7}$
	x4	83	168	1.3065	7.66 × ${10}^{-7}$	37	76	0.57785	6.02 × ${10}^{-7}$	198	398	4.3892	9.96 × ${10}^{-7}$	40	82	2.4788	4.09 × ${10}^{-7}$
	x5	81	164	1.4513	8.87 × ${10}^{-7}$	40	82	0.54615	9.17 × ${10}^{-7}$	196	394	3.7983	9.62 × ${10}^{-7}$	50	102	3.0168	8.14 × ${10}^{-7}$
	x6	106	214	2.0765	9.35 × ${10}^{-7}$	50	102	0.6377	7.26 × ${10}^{-7}$	364	730	7.3788	9.52 × ${10}^{-7}$	49	100	2.9609	6.42 × ${10}^{-7}$
100000	x1	80	162	3.7128	9.06 × ${10}^{-7}$	36	74	1.2562	6.72 × ${10}^{-7}$	210	422	8.4059	9.9 × ${10}^{-7}$	47	96	6.3303	4.09 × ${10}^{-7}$
	x2	81	164	2.8053	9.51 × ${10}^{-7}$	42	86	1.3892	5.03 × ${10}^{-7}$	215	432	7.851	1 × ${10}^{-6}$	40	82	5.602	6.53 × ${10}^{-7}$
	x3	85	172	3.2804	9.1 × ${10}^{-7}$	46	94	1.406	3.58 × ${10}^{-7}$	155	312	6.2393	9.74 × ${10}^{-7}$	48	98	6.8649	7.43 × ${10}^{-7}$
	x4	83	168	3.2079	9.94 × ${10}^{-7}$	43	88	1.207	9.09 × ${10}^{-7}$	211	424	8.7274	9.6 × ${10}^{-7}$	58	118	7.2979	6.17 × ${10}^{-7}$
	x5	81	164	3.1215	8.28 × ${10}^{-7}$	42	86	1.1724	4.39 × ${10}^{-7}$	212	426	8.7216	9.92 × ${10}^{-7}$	49	100	6.5793	9.17 × ${10}^{-7}$
	x6	109	220	3.7274	9.75 × ${10}^{-7}$	54	110	1.4392	7 × ${10}^{-7}$	373	748	13.9937	9.54 × ${10}^{-7}$	50	102	6.8552	4.66 × ${10}^{-7}$

and

Table 11. Test results obtained by the four solvers for Problem 11.

Problem 11	HSS				CGD				PDY				MFRM
SP	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM	ITER	FVAL	TIME	NORM
x1	69	139	0.071482	9.81 × ${10}^{-7}$	243	487	0.060688	9.56 × ${10}^{-7}$	57	115	0.033502	8.4 × ${10}^{-7}$	48	97	0.059039	8.64 × ${10}^{-7}$
x2	63	127	0.009891	9.41 × ${10}^{-7}$	228	457	0.025727	9.77 × ${10}^{-7}$	52	105	0.018045	8.24 × ${10}^{-7}$	57	115	0.054443	8.39 × ${10}^{-7}$
x3	70	141	0.011627	9.32 × ${10}^{-7}$	246	493	0.028826	9.75 × ${10}^{-7}$	59	119	0.014909	8.08 × ${10}^{-7}$	51	103	0.04544	7.37 × ${10}^{-7}$
x4	68	137	0.010198	9.27 × ${10}^{-7}$	235	471	0.02545	9.49 × ${10}^{-7}$	57	115	0.015413	8.21 × ${10}^{-7}$	61	123	0.052551	9.35 × ${10}^{-7}$
x5	42	85	0.007375	7.69 × ${10}^{-7}$	193	387	0.021762	9.83 × ${10}^{-7}$	39	79	0.013396	9.28 × ${10}^{-7}$	50	101	0.047834	9.42 × ${10}^{-7}$
x6	68	137	0.008927	8.96 × ${10}^{-7}$	250	501	0.026878	9.68 × ${10}^{-7}$	56	113	0.014667	8.47 × ${10}^{-7}$	61	123	0.050977	7.61 × ${10}^{-7}$

. We see from the NORM (norm of the objective function) reported in Table 1, Table 2, Table 3, Table 4, Table 5, Table 6, Table 7, Table 8, Table 9, Table 10 and Table 11 that the proposed HSS algorithm obtained the solutions of all the test problems in each instance while the other three methods (CGD, PDY and MFRM) failed to obtain the solutions of some problems in some instances. This means our proposed algorithm can serve as an alternative to some existing methods. The numerical results reported show that the proposed HSS algorithm recorded least ITER, FVAL and TIME in most instances. We summarized all the information from Table 1, Table 2, Table 3, Table 4, Table 5, Table 6, Table 7, Table 8, Table 9, Table 10 and Table 11 in Figure 1, Figure 2 and Figure 3 based on the performance profile by Dolan and Mor$\acute{e}$ [38] which tells the percentage win by each solver. In terms of ITER and FVAL, we see from Figure 1 and Figure 2 that the HSS algorithm performs well and won about $70\%$ of the whole experiments compared to the existing methods. In addition, Figure 3 shows that the HSS algorithm is faster than all the three methods compared with. Therefore, we can regard the proposed HSS algorithm as more efficient than CGD, PDY and MFRM methods with respect to the numerical experiments performed.

3.2. Second Experiment on Signal Processing

The major advantage of the proposed HSS algorithm is that it does not require the knowledge of the derivative of an objective function and therefore suitable for solving nonsmooth functions. As mentioned in the introduction section, many applications can be converted into monotone nonlinear equation. In particular, we consider the reconstruction of an original signal, say $\widehat{x}\in {\mathbb{R}}^n$ by minimizing an objective function that contains a linear least square error term and a sparseness-including ${\ell }_1$ regularization term

$$\underset{x}{min}\frac{1}{2}{\parallel y-Ex\parallel }_2^2+\mu {\parallel x\parallel }_1,$$

(46)

where $x\in {\mathbb{R}}^n$ $y\in {\mathbb{R}}^k$ is an observation, $E\in R^{k\times n}$ $(k<<n)$ is a linear operator and $\mu \ge 0$ a parameter. Problem (46) has received much attention and different iterative methods for solving it have been proposed by many researchers (see, [39,40,41,42,43,44,45]). One of the popular methods for solving (46) is the gradient projection method for sparse reconstruction (also known as GPSR) proposed by Figueiredo et al. [46]. Other gradient-based iterative algorithms include the coordinate gradient descent [47] and the accelerating gradient projection methods [48] among others. These methods enjoyed good performance, even though they required the knowledge of the gradient.

The derivative-free nature of our proposed algorithm makes suitable to deal with the nonsmooth problem (46). However, Algorithm 1 is designed to handle problems in the form of (1) and therefore we need to rewrite problem (46) into the form of problem (1). Fortunately, the work of Figueiredo et al. [46] shows that if we let $q={\left[uv\right]}^T,$ then (46) can be translated into the following bound-constrained quadratic programming problem

$$\begin{array}{cc}\hfill & \underset{q}{min}\frac{1}{2}{q}^{T}Gq+c^{T}q,\hfill \\ \hfill & \mathrm{s}.\mathrm{t}q\ge 0,\hfill \end{array}$$

(47)

where $c=\mu e_{2n}+\left(\begin{array}{c}-b\\ b\end{array}\right)$, $b=E^{T}y$, $G=\left(\begin{array}{cc}{E}^{T}E& -E^{T}E\\ -E^{T}E& E^{T}E\end{array}\right)$.

It is not difficult to see that the matrix G is a positive semi-definite. On the other hand, Xiao et al. [2] solve problem (47) in a different way by writing it as the following linear variable inequality problem

$$\left\{\begin{array}{c}\mathrm{Find}q\in {\mathbb{R}}^n\mathrm{such}\mathrm{that}\hfill \\ \langle Gq+c,q^{\prime }-q\rangle \ge 0,\forall q^{\prime }\ge 0.\hfill \end{array}\right.$$

(48)

By taking the special structure of the feasible region of q into consideration, they further showed that problem (48) is equivalent to the following linear complementary problem

$$\left\{\begin{array}{c}\mathrm{Find}q\in {\mathbb{R}}^n\mathrm{such}\mathrm{that}\hfill \\ q\ge 0,Gq+c\ge 0\mathrm{and}\langle Gq+c,q\rangle =0.\hfill \end{array}\right.$$

(49)

We can see that $q\in {\mathbb{R}}^n$ is a solution of problem (49) if and only if it satisfies the following

$$F\left(q\right):=min\{q,Gq+c\}=0.$$

(50)

In (50), the function F is a vector-valued and the “min” operator denotes the componentwise minimum of two vectors. Problem (50) is in the form of problem (1) and interestingly, Lemma 3 of [49] and Lemma 2.2 of [2] show that the function F satisfies Assumption 1 (ii) that is, Lipschitzian continuity and monotonicity. Hence, the proposed derivative-free HSS algorithm can be applied to solve it. At each iteration, our proposed algorithm is applied to the resulting problem (50) without requiring the Jacobian matrix information.

We compared HSS algorithm and the modified self-adaptive CG method (MSCG) [50] based on their performance in restoring a length-n sparse signal from k observations. We used three metrics; namely ITER (number of iterations), CPU (CPU time) and mean of squared error (MSE) to evaluate the performance of each method. The MSE is usually used to assess the quality of reconstruction and is calculated using the following formula

$$\mathrm{MSE}=\frac{1}{n}{\parallel x-\widehat{x}\parallel }^2,$$

where x and $\widehat{x}$ denote the original and restored signal respectively. The measurement y contains noise, $y=Gx+\omega ,$ where $\omega$ is the Gaussian noise disturbed as $N(0,{10}^{-4})$ and G is the Gaussian matrix generated by command $\mathrm{randn}(m,n),$ in MATLAB. The size of the signal is selected with $n=2^{15}$ and $m=2^{13}.$ The original signal contains $2^7$ random nonzero elements. For the signal recovery experiment, the algorithms were coded in MATLAB R2019b and run on a PC with intel(R) Core(TM) i7-10510U processor with 8.00 GB (7.80 GB usable) of RAM and CPU 1.80GHZ–2.30GHz.

We started the iteration process by the measurement signal, i.e., $x_0=G^{T}y,$ and used $f\left(x\right)=\frac{1}{2}{\parallel y-Ax\parallel }_2^2+\mu {\parallel x\parallel }_1$ as the merit function. We used the same parameters as in the first experiment for HSS method except for $a=0.2$ while the parameters for MSCG come from [50]. We terminated the iteration process when the relative change of the objective function satisfies $\left|\frac{f\left(x_k\right)-f\left(x_{k-1}\right)}{f\left(x_{k-1}\right)}\right|<{10}^{-5}.$ In order to have relatively fair assessment for both methods, we run each code with the same initial point, using the same continuation technique on parameter $\mu$ and observed the convergence behaviour of each method to obtain a solution with similar accuracy. We presented numerical results of the experiment for fifteen different noise samples in

Table 12. Numerical results of HSS and modified self-adaptive conjugate gradient (MSCG) methods with the initial points randomly generated.

	HSS			MSCG
S/No.	MSE	ITER	CPU	MSE	ITER	CPU
1	2.23 $\times {10}^{-6}$	79	178.11	4.61 $\times {10}^{-6}$	143	309.23
2	3.44 $\times {10}^{-6}$	82	198.38	6.46 $\times {10}^{-6}$	150	359.03
3	2.84 $\times {10}^{-6}$	71	175.06	7.43 $\times {10}^{-6}$	163	386.78
4	4.71 $\times {10}^{-6}$	72	160.22	1.49 $\times {10}^{-5}$	139	305.39
5	1.99 $\times {10}^{-6}$	76	184.17	4.07 $\times {10}^{-6}$	144	341.41
6	1.68 $\times {10}^{-6}$	83	197.36	3.12 $\times {10}^{-6}$	148	342.94
7	3.92 $\times {10}^{-6}$	65	158.09	6.43 $\times {10}^{-6}$	162	396.00
8	2.23 $\times {10}^{-6}$	79	173.63	4.43 $\times {10}^{-6}$	145	314.28
9	1.59 $\times {10}^{-6}$	71	170.02	3.94 $\times {10}^{-6}$	152	365.58
10	5.72 $\times {10}^{-6}$	65	124.77	9.63 $\times {10}^{-6}$	160	311.38
11	3.71 $\times {10}^{-6}$	67	152.91	4.44 $\times {10}^{-6}$	141	306.33
12	2.09 $\times {10}^{-6}$	70	148.05	3.58 $\times {10}^{-6}$	145	307.59
13	2.39 $\times {10}^{-6}$	72	155.38	4.93 $\times {10}^{-6}$	146	287.72
14	1.96 $\times {10}^{-6}$	72	148.69	5.41 $\times {10}^{-6}$	151	308.14
15	2.36 $\times {10}^{-6}$	79	177.47	4.61 $\times {10}^{-6}$	143	318.89
Average	2.86 $\times {10}^{-6}$	73.53	166.82	5.87$\times {10}^{-6}$	148.80	330.71

and the average of each column is also computed. In addition, we presented the graphical view of the original, disturbed and recovered signals in Figure 4 and Figure 5. From Table 12, we see that HSS algorithm restored the disturbed signal with least ITER values and also converged faster than MSCG based on the CPU time(s). Moreover, the quality of reconstruction by HSS algorithm is slightly better than that of MSCG method since the MSE with respect to the former is a little less than that of the later.

4. Conclusions

A Hestenes–Stiefel-like derivative-free method with spectral parameter for nonlinear monotone equations has been proposed based on a suitable line search strategy and projection technique. The method is a modification of the conjugate gradient algorithm proposed by Amini et al. [33]. Two types of experiments were presented to show the efficiency of the proposed method. Numerical results reported show that the proposed outperformed three existing methods [15,25,32] and was able to recover some disturbing signals in compressive sensing with better quality than the method in [50]. The convergence analysis of the proposed method was established under standard assumptions.