Preconditioned conjugate gradient methods for absolute value equations

Nassima Anane$^\ast $ Mohamed Achache$^\bullet $

October 11, 2019; accepted: February 27, 2020; published online: August 11, 2020.

In this paper, we investigate the NP-hard absolute value equations (AVE), $Ax-B\left\vert x\right\vert =b$, where $A,B$ are given symmetric matrices in $\mathbb {R}^{n\times n}$, $b\in \mathbb {R}^{n}$. By reformulating the AVE as an equivalent unconstrained convex quadratic optimization, we prove that the unique solution of the AVE is the unique minimum of the corresponding quadratic optimization. Then across the latter, we adopt the preconditioned conjugate gradient methods to determining an approximate solution of the AVE. The computational results show the efficiency of these approaches in dealing with the AVE.

MSC. 65F08, 90C33, 93C05, 90C20

Keywords. Absolute value equations, linear system, unconstrained convex quadratic optimization, linear complementarity problems

$^\ast $ Département de génés des procédures. Faculté de Technologie. Université ferhat Abbas, Sétif 1. Sétif 19000, Algérie, e-mail: nasimaannan@gmail.com.

$^\bullet $ Laboratoire de Mathématiques Fondamentales et Numériques. Université ferhat Abbas, Sétif 1. Sétif 19000, Algérie, e-mail: achache_m@univ-setif.dz. This work has been supported by: La Direction Générale de la Recherche Scientifique et du Développement Technologique (DGRSDT-MESRS), under project PRFU number C00L03UN190120190004. Algérie.

1 Introduction

The absolute value equations (AVE) of the type:

\begin{equation} Ax-B|x|=b,\label{f1} \end{equation}

where $A$ and $B$ are given matrices in $\mathbb {R}^{n\times n},\, b\in \mathbb {R}^{n}$ and $\left\vert x\right\vert $ denotes the vector with absolute values of each components of the vector $x$, was investigated by [ 1 ] , [ 11 ] , [ 12 ] , [ 15 ] . A special case of 1 when $B=I$ ($I$ denotes the identity matrix) is the AVE of the type:

\[ Ax-|x|=b. \]

The AVEs arise in many scientific areas and mathematical problems such as linear complementarity problems (LCP), boundary value problems, equilibrium problems and interval linear equations. As is known in [ 11 ] , the general NP-hard linear complementarity can be formulated as the AVE 1, then it is an NP-hard in its general form. Furthermore, much research has been devoted to achieve their numerical solutions efficiently (see, e.g., [ 1 ] , [ 2 ] , [ 7 ] , [ 8 ] , [ 9 ] , [ 12 ] , [ 15 ] ).

In this paper, by reformulating the AVE 1 into an equivalent unconstrained quadratic optimization problem, we prove first under the condition that the smallest singular value of $A$ is greater than the largest singular value of $B$, the AVE 1 is uniquely solvable for any $b$. Secondly, we show that the unique minimum of the corresponding unconstrained quadratic problem is the unique solution of the AVE 1. Then across the latter, we apply the conjugate gradient algorithms to approximate numerically the solution of the AVE 1. In the presence of the ill-conditioned, preconditioned conjugate gradient methods can be used to ensure and to accelerate the convergence of the basic CG algorithms. We show across some examples of the AVE, the efficiency of these approaches.

Now we describe our notation. The scalar product of two vectors $x$ and $y$ in $\mathbb {R}^{n}$ is denoted by $x^{T}y$. For $x\in \mathbb {R}^{n}$, the norm $\Vert x\Vert $ will denote the Euclidean norm $(x^{T}x)^{1/2}$, and $\operatorname {sign}(x)$ will denote a vector with components equal to $+1, 0$ or $- 1$, depending on whether the corresponding component of $x$ is positive, zero or negative, respectively. In addition, $D(x)$:= $\partial \vert x\vert =\operatorname {sign}(x))$ will denote the diagonal matrix corresponding to $\operatorname {sign} (x)$ where $\partial \vert x\vert $ denotes the generalized Jacobian for the absolute value $\vert x\vert $ based on a sub-gradient. The vector of ones and the inverse of a nonsingular matrix $A$ are denoted, respectively, by $e$ and $A^{-1}$. $\lambda _{\min }(M)$ and $\lambda _{\max }(M)$ stand for the minimal and the maximal eigenvalues of a matrix $M$.

As it is known, for a symmetric matrix $M$, the minimal and the maximal singular values of $M$, are defined by $\sigma _{\min }(M)=\min _{\Vert y\Vert =1}\Vert My\Vert $ and $\sigma _{\max }(M)=\Vert M\Vert = \max _{\Vert y\Vert =1}\Vert My\Vert $, respectively. Here, $\Vert M\Vert $ is called the spectral induced norm. Finally, the spectral condition number of a non-singular symmetric matrix $M$ is denoted by $\kappa ({M})=\frac{\vert \lambda _{\max }(M)\vert }{\vert \lambda _{\min }(M)\vert }$.

The paper is built as follows. In section 2, the unique solvability of the AVE 1 as well as its equivalence reformulation to unconstrained quadratic optimization and the basic conjugate gradient methods for solving the AVE 1 are stated. In section 3, the preconditioned conjugate gradient algorithms are proposed. Numerical results are reported in section 4. The paper is ended with a conclusion and future work in section 5.

2 Basic conjugate gradient methods

Before describing the conjugate gradient algorithm, the following results are useful. For given symmetric matrices $A$ and $B$, we define, for any diagonal matrix $D$ whose elements are equal to $1, 0$ or $-1$, the matrix $Q=A-BD$. To prove the unique solvability of the AVE 1, the following result is required.

Lemma 1

If symmetric matrices $A$ and $B$ satisfy:

\[ \sigma _{\min }(A){\gt}\sigma _{\max }(B), \]

then the matrix $A-BD$ is nonsingular for any diagonal matrix $D$ whose elements are equal to $+1$, $0$ or $-1$.

Proof â–¼

Assume the contrary, that $A-BD$ is singular, then for some nonzero vector $x$ with $\Vert x\Vert =1$, we then have that $(A-BD)x=0,$ which derives a contradiction. This implies that $Ax=BDx$. Hence

\begin{eqnarray*} \sigma _{\min }(A) & =& \min _{\left\Vert y\right\Vert =1}\Vert Ay\Vert \leq \Vert Ax\Vert =\Vert BDx \Vert \\ & \leq & \Vert B\Vert \Vert D\Vert \Vert x\Vert \leq \Vert B\Vert =\sigma _{\max }(B). \end{eqnarray*}

This contradicts our condition. Hence $A-BD$ is non-singular.â–¡

Now according to the equality $D(x)x=\vert x\vert $, with $D(x)=\operatorname {diag}(\operatorname {sign} (x)$) the AVE 1 can be transformed into the following linear system of equations:

\begin{equation} Qx=b,\label{f2} \end{equation}

where $Q=A-BD$.

Lemma 2

If symmetric matrices $A$ and $B$ satisfy

\[ \sigma _{\min }(A){\gt}\sigma _{\max }(B), \]

then the AVE 1 is uniquely solvable for any $b$.

Proof â–¼

Based on the result of lemma 1, the matrix $Q$ is non-singular for any arbitrary diagonal matrix $D$ whose elements are equal to $1, 0$ or $- 1$ and therefore the AVE 1 has a unique solution for any $b$.â–¡

One of the important numerical tools to solve the system 2 is to transform it into an equivalent quadratic optimization problem:

\begin{equation} \min _{x\in \mathbb {R}^{n}}f(x)=\tfrac {1}{2}(Qx-b)^{T}(Qx-b) \label{f3}. \end{equation}

The gradient and the Hessian matrix of $f(x)$ are given by:

\[ g(x):=\partial f(x)=Q^{T}(Qx-b) \]

and

\[ H(x):=\partial ^{2}f(x)=Q^{T}Q. \]

Since $H(x)$ is positive definite for any diagonal matrix $D$ whose elements are equal to $+1$, $0$ or $- 1$, the problem 3 has a unique minimum that satisfies

\[ g(x)=0 \]

\begin{equation} Q^{T}Qx=Q^{T}b.\label{f4} \end{equation}

Since $Q$ is non-singular therefore 4 is equivalent to 2 and so is equivalent to AVE 1. Hence solving the AVE 1 is equivalent to find the unique minimum of 3.

The conjugate gradient methods are known to be effective in solving quadratic problems in finite termination [ 4 ] , [ 5 ] , [ 16 ] , [ 17 ] , [ 18 ] . These methods start with an initial point $x_{0}$ and generate a sequence $\left\{ x_{k}\right\} $ according to the following recurrence formula:

\begin{equation} x_{k+1}=x_{k}+\alpha _{k}d_{k},\qquad k=0,\, 1,\, 2,\dots \label{f5} \end{equation}

where $\alpha _{k}{\gt}0$ is the step-size obtained by a line search and the directions $d_{k}$ are computed by the rule:

\begin{equation} d_{k}=-g_{k}+\beta _{k}d_{k-1},\quad k\geq 1,\, d_{0}=-g_{0}, \label{f6} \end{equation}

where $\beta _{k}$ is a suitable positive scalar known as the conjugate updating parameter and $g_{k}$ refers to $g(x_{k})$.

2.1 Exact line search

Determining the step-size $\alpha _{k}$ in 5 along the direction $d_{k}$, for an objective function $f(x)$, which is to be minimized, can be simplified to finding the value of $\alpha _{k}=\alpha $ which consequently minimizes the function:

\[ f(x_{k+1})=f(x_{k}+\alpha d_{k})=m(\alpha ). \]

The function $m(\alpha )$ is of a single variable, that is $\alpha $. Therefore, the $\alpha _{k}$ is calculated by an exact line search as follows. Using Taylor’s expansion, we have,

\[ m(\alpha )=f(x_{k}+\alpha d_{k})=f(x_{k})+\alpha g_{k}^{T}d_{k}+\tfrac {\alpha ^{2}}{2}d_{k}^{T}H_{k}d_{k}, \]

\[ \tfrac {\partial m}{\partial \alpha }=0\Leftrightarrow \alpha =-\tfrac {g_{k}^{T}d_{k}}{d_{k}^{T}H_{k}d_{k}}. \]

Therefore the exact line search is taken as:

\begin{equation} \alpha _{k}=-\tfrac {g_{k}^{T}d_{k}}{d_{k}^{T}H_{k}d_{k}},\label{f7} \end{equation}

where $H_{k}$ refers to $H(x_{k})$.

2.2 Computation of $\protect \beta _{k}$

The coefficients $\beta _{k}$ being chosen in such a way that $d_{k}$ is conjugated with all the preceding directions, in other words

\[ d_{k}^{T}Qd_{k-1}=0, \]

then it implies that:

\[ d_{k}^{T}Qd_{k-1}=-g_{k}^{T}Qd_{k-1}+(\beta _{k}d_{k-1})^{T}Qd_{k-1}=0, \]

and so:

\begin{equation} \label{f.8} \beta _{k}=\tfrac {g_{k}^{T}Qd_{k-1}}{d_{k-1}^{T}Qd_{k-1}}. \end{equation}

2.3 Basic conjugate gradient algorithms.

We are now ready to state the basic CG algorithms for solving the AVE 1.

Step 1. Choose an arbitrary initial point $x_{0}\in \mathbb {R}^{n}$, $\epsilon {\gt}0$ and $d_{0}=-g_{0}$, $k=0$;
Step 2. Compute $\alpha _{k}$ from 7 and set $x_{k+1}=x_{k}+\alpha _{k}d_{k}$;
Step 3. If $\Vert Ax_{k}-B\vert x_{k}\vert -b\Vert {\lt}\epsilon $ then STOP, otherwise compute $d_{k}$ according to $d_{k}=-g_{k}+\beta _{k}d_{k-1}$ with $\beta _{k}$ is computed from 8;
Step 4. Set $k=k+1,$ and go to Step 2.

In [ 4 ] , and [ 17 ] , it is shown that the convergence of the $CG$ methods is linearly global to the unique minimum $x^{\ast }$. It is known that the convergence of $CG$ methods depends heavily on the condition number $\kappa (Q).$ If $\kappa (Q)$ is close to $1$, i.e., if the matrix $Q$ is well-conditioned then $CG$ methods converge fast to the solution. Otherwise, in the presence of ill-conditioned of the matrix $Q$, these methods have a very slow convergence.

3 Preconditioned conjugate gradient algorithms

Preconditioning is mainly used in $CG$ methods in order to accelerate their convergence when $\kappa (Q)$ is very far from $1$, i.e., when $Q$ is ill-conditioned. Based on this fact, we can consider the preconditioned AVE 1:

\begin{equation} PAx-PB\left\vert x\right\vert =Pb,\label{f9} \end{equation}

where $P$ is a non-singular matrix, called the preconditioner. Obviously, the form 9 is a general form of the AVE 1. For $P=I$, the form 9 reduced to the AVE 1. Again using $D(x)x=\left\vert x\right\vert $, then 9 becomes the following preconditioned linear system:

\begin{equation} PQx=Pb.\label{f10} \end{equation}

Hence the system 10 has a unique solution if the matrix $PQ$ is invertible. Since $P$ is assumed to be non-singular, then we only prove that $Q$ is non-singular. By lemma 1, the matrix $Q$ is non-singular for any diagonal matrix $D$ whose elements are $1, 0$, or $-1$, and consequently, the system 10 has a unique solution and so the preconditioned AVE in 9 is uniquely solvable for each $b$. Based on this observation, therefore, the equivalent preconditioned quadratic optimization problem is:

\begin{equation} \min _{x\in \mathbb {R}^{n}}f_{P}(x)=\tfrac {1}{2}(PQx-Pb)^{T}(PQx-Pb).\label{f11} \end{equation}

The gradient and the Hessian matrix of $f$ are:

\[ g^{P}(x):=\partial f_{P}(x)=(PQ)^{T}(PQx-Pb) \]

and

\[ H^{P}(x):=\partial ^{2}f_{P}(x)=(PQ)^{T}(PQ). \]

It is clear that if $P=I$, the problem 11 reduces to the original problem 3. Also since $(PQ)^{T}(PQ)$ is positive definite matrix, the problem 11 has a unique minimum that satisfies:

\[ g^{P}(x)=0, \]

\[ (PQ)^{T}(PQx-Pb)=0, \]

which means that the unique minimum is the unique solution of the preconditioned system and which is in turn the unique solution of the AVE 1. For the preconditioned problem 10, with same manner as the basic CG algorithms, we compute the exact line search $\alpha _{k}$ and the conjugate parameter $\beta _{k}$ along the new preconditioned modified search direction by the formulas:

\begin{equation} \alpha _{k}=-\frac{(g_{k}^{P})^{T}d_{k}}{d_{k}^{T}H_{k}^{P}d_{k}}, \label{f12} \end{equation}

and

\begin{equation} \beta _{k}=\frac{(g_{k}^{P})^{T}Qd_{k-1}}{d_{k-1}^{T}Qd_{k-1}}. \label{f13} \end{equation}

Now the preconditioned conjugate gradient $(PCG)$ algorithm for solving the AVE 1 is described as follows.

3.1 Preconditioned conjugate gradient algorithm

Step 1. Choose an arbitrary $x_{0}\in \mathbb {R}^{n}$, a preconditioner matrix $P$, $\epsilon {\gt}0$ and $d_{0}=-g_{0}^{P}$, $k=0$;
Step 2. Compute $\alpha _{k}$ from 12 and set $x_{k+1}=x_{k}+\alpha _{k}d_{k}$;
Step 3. If $\Vert Ax_{k}-B\vert x_{k}\vert -b\Vert {\lt}\epsilon $ then STOP, otherwise compute $d_{k}$ according to $d_{k}=-g_{k}^{P}+\beta _{k}d_{k-1}$ with $\beta _{k}$ is computed from 13;
Step 4. Set $k=k+1,$ and go to Step 2.

Note that there is no unique strategy for choosing the preconditioning matrix $P$ for the conjugate $CG$ methods. In fact, the strategy of choosing $P$ is based on a such way that the $\kappa (PQ)\ll \kappa (Q).$ For more details see [ 4 ] .

4 Numerical experiments

In this section, we present some numerical experiments on some examples of solvable AVE 1 to confirm the viability of the $PCG$ algorithms. The experiments are performed with MATLAB 7.9 and carried out on a PC where our tolerance is set to $\epsilon = 10^{-6}$. The initial point and the true solution of AVE 1 are denoted by $x_{0}$ and $x^{\ast }$, respectively. Meanwhile, the number of iterations, the elapsed times and the residue are denoted by Iter, CPU and RSD=$\Vert Ax_{k}-B\vert x_{k}\vert -b\Vert $, respectively. In our numerical implementation, the appropriate choice of the preconditioners are $P=\frac{1}{n}I,n\geq 1,$ and $P=A^{-1}$.

Example 3

Let the symmetric matrices $A$, $B$ and the vector $b$ be given as:

\begin{align*} A =& (a_{ij})=\begin{cases} 4n, & \mbox{if } i=j, \\ n, & \mbox{if } \left\vert i-j\right\vert =1 \\ 0.5, & \mbox{otherwise} \end{cases}\\ B =& (b_{ij})= \begin{cases} n, & \mbox{if } i=j, \\ \frac{1}{n}, & \mbox{if } \left\vert i-j\right\vert =1, \\ 0.125, & \mbox{otherwise} \end{cases}\end{align*}

\begin{align*} b=& (548,647.5,\ldots ,647.5,548)^{T}. \end{align*}

With the initial points $x_{1}^{0}=(0.001,\ldots ,0.001)^{T}$ and $x_{2}^{0}=(0.9,\ldots ,0.9)^{T},$ the computational results with different size of $n$, are summarized in table 1.

Size $n$	$x_{0}$		$P=I$ (basic CGA)	$P=\frac{1}{n}I,n{\gt}1$	$P=A^{-1}$
	$x_{1}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 29 \\ 0.0186 \\ {6.0870e-6}\end{array}$	$\begin{array}{c} 21 \\ 0.0161 \\ {8.4089e-6}\end{array}$	$\begin{array}{c} 2 \\ 0.0057 \\ {4.5068e-07}\end{array}$
$100$	$x_{2}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 27 \\ 0.0178 \\ {6.7790e-6}\end{array}$	$\begin{array}{c} 19 \\ 0.0158 \\ {9.1783e-6}\end{array}$	$\begin{array}{c} 3 \\ 0.0074 \\ {6.9333e-06}\end{array}$
	$x_{1}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 33 \\ 3.5787 \\ {5.4336e-6}\end{array}$	$\begin{array}{c} 21 \\ 2.4979 \\ {8.5594e-6}\end{array}$	$\begin{array}{c} 2 \\ 0.2273 \\ {4.5352e-08}\end{array}$
$1000$	$x_{2}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 31 \\ 3.3429 \\ {6.0443e-6}\end{array}$	$\begin{array}{c} 19 \\ 2.0959 \\ {9.3010e-6}\end{array}$	$\begin{array}{c} 3 \\ 0.3293 \\ {8.8665e-15}\end{array}$
	$x_{1}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 34 \\ 26.6083 \\ {5.7908e-6}\end{array}$	$\begin{array}{c} 21 \\ 16.2365 \\ {8.4035e-6}\end{array}$	$\begin{array}{c} 2 \\ 1.5644 \\ {2.2684e-08}\end{array}$
$2000$	$x_{2}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 32 \\ 24.4110 \\ {6.4720e-6}\end{array}$	$\begin{array}{c} 19 \\ 14.6529 \\ {9.2160e-6}\end{array}$	$\begin{array}{c} 3 \\ 2.2716 \\ {1.5029e-14}\end{array}$
	$x_{1}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 34 \\ 90.5026 \\ {8.4709e-6}\end{array}$	$\begin{array}{c} 21 \\ 53.2645 \\ {8.3032e-6}\end{array}$	$\begin{array}{c} 2 \\ 4.9661 \\ {1.5124e-08}\end{array}$
$3000$	$x_{2}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 32 \\ 83.9471 \\ {9.5473e-6}\end{array}$	$\begin{array}{c} 19 \\ 48.7091 \\ {9.1581e-6}\end{array}$	$\begin{array}{c} 3 \\ 5.7692 \\ {2.7556e-14}\end{array}$

Table 1 Numerical results for example 3.

The true solution is $x^{\ast }=(\frac{4}{3},\frac{4}{3},\ldots ,\frac{4}{3},\frac{4}{3})^{T}$.

Example 4

The hydrodynamic equations (equilibrium problem [ 13 ] , is modeled as the following non-differentiable algebraic equations:

\[ Bx+\max (0,x)=c, \]

where $B\in \mathbb {R}^{n\times n}$,$c\in \mathbb {R}^{n}$ are given. Using the identity

\[ \max \left( a,b\right) =\tfrac {1}{2}\left( a+b+\left\vert a-b\right\vert \right) , \]

equality, the hydrodynamic equation can be reformulated as an AVE 1. We have, $Bx+\frac{1}{2}\left( x+\left\vert x\right\vert \right) =c\Leftrightarrow Ax-\left\vert x\right\vert -b=0 $ where $A=-(2B+I)$ and $b=-2c$.

Consider now, a randomly hydrodynamic equation where $B\in \mathbb {R}^{n\times n}$ and $c$ are given by:

\[ B=(b_{ij})=\left\{ \begin{array}{l} b_{ii}=-25.5, \\ b_{i,i+1}=a_{i+1,i}=-2.5, \\ b_{ij}=0,\end{array}\right. \]

and

\[ c=\left( -27,-29.5,\ldots ,-29.5,-27\right) ^{T}. \]

The initial points are $x_{1}^{0}=(0.5,\ldots ,0.5)^{T}$ and $x_{2}^{0}=(0.9,\ldots ,0.9)^{T}.$ The computational results with different size of $n$, are summarized in table 2.

Size $n$	$x_{0}$		$P=I$ (basic CGA)	$P=\frac{1}{n}I,n{\gt}1$	$P=A^{-1}$
	$x_{1}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 11 \\ 0.0143 \\ {6.1357e-6}\end{array}$	$\begin{array}{c} 8 \\ 0.0133 \\ {5.7939e-6}\end{array}$	$\begin{array}{c} 4 \\ 0.0081 \\ {4.8013e-8}\end{array}$
$100$	$x_{2}^{0}$	$\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 10 \\ 0.0170 \\ {5.6321e-6}\end{array}$	$\begin{array}{c} 7 \\ 0.0113 \\ {5.1941e-6}\end{array}$	$\begin{array}{c} 3 \\ 0.0068 \\ {2.0096e-6}\end{array}$
	$x_{1}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 11 \\ 1.1760 \\ {5.8906e-6}\end{array}$	$\begin{array}{c} 7 \\ 0.7838 \\ {2.5537e-6}\end{array}$	$\begin{array}{c} 4 \\ 1.5308 \\ {4.8112e-8}\end{array}$
$1000$	$x_{2}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 10 \\ 1.1115 \\ {5.4239e-6}\end{array}$	$\begin{array}{c} 6 \\ 0.6666 \\ {2.2815e-6}\end{array}$	$\begin{array}{c} 3 \\ 1.1335 \\ {2.0219e-6}\end{array}$
	$x_{1}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 11 \\ 8.9451 \\ {5.8609e-6}\end{array}$	$\begin{array}{c} 6 \\ 4.7227 \\ {5.7002e-6}\end{array}$	$\begin{array}{c} 4 \\ 5.5383 \\ {4.8116e-8}\end{array}$
$2000$	$x_{2}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 10 \\ 8.1684 \\ {5.4023e-6}\end{array}$	$\begin{array}{c} 5 \\ 4.0932 \\ {5.0782e-6}\end{array}$	$\begin{array}{c} 3 \\ 5.3227 \\ {2.0226e-6}\end{array}$
	$x_{1}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 11 \\ 28.4459 \\ {5.8503e-6}\end{array}$	$\begin{array}{c} 6 \\ 15.5639 \\ {3.7993e-6}\end{array}$	$\begin{array}{c} 4 \\ 13.9749 \\ {4.8117e-8}\end{array}$
$3000$	$x_{2}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 10 \\ 25.7548 \\ {5.3948e-6}\end{array}$	$\begin{array}{c} 5 \\ 12.8931 \\ {3.3853e-6}\end{array}$	$\begin{array}{c} 3 \\ 10.7083 \\ {2.0228e-6}\end{array}$

Table 2 Numerical results for example 4.

The true solution of this example is $x^{\ast }=e.$

Example 5

Given a matrix $M$ and a vector $q$, the LCP [ 3 ] , consists in finding $w,$ $z\in \mathbb {R}^{n}$ such that

\[ w\geq 0,\; z\geq 0,\, w-Mz=q,\, z^{T}w=0. \]

Letting $w=\left\vert x\right\vert -x,\, \, z=\left\vert x\right\vert +x,$ then, $w\geq 0,\, z\geq 0,$ and $z^{T}w=0$. By substituting $w$ and $z$ in LCP, then an equivalent AVE 1 with $A=(I-M)^{-1}(I+M)$, and $b=-(I-M)^{-1}q$, provided that $(I-M)$ is invertible, is obtained. Note that if $x$ solves the AVE 1, then $z=\left\vert x\right\vert +x\geq 0$ solves the LCP. Let $M\in \mathbb {R}^{n\times n}$ and $q$ be given as:

\begin{align*} M=& (a_{ij})= \begin{cases} 0.6, & \mbox{if } i=j, \\ -0.01, & \mbox{if } \left\vert i-j\right\vert =1, \\ 0, & \mbox{otherwise} ,\end{cases}\\ q=& -e. \end{align*}

The initial points are $x_{1}^{0}=(0.001,\cdots ,0.001)^{T}$ and $x_{2}^{0}=(0.9,\cdots ,0.9)^{T}$ and the obtained computational results with different size of $n$, are stated in table 3.

Size $n$	$x_{0}$		$P=I$ (basic CGA)	$P=\frac{1}{n}I,n{\gt}1$	$P=A^{-1}$
	$x_{1}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 7 \\ 0.0152 \\ {2.0378e-6}\end{array}$	$\begin{array}{c} 5 \\ 0.0090 \\ {2.3141e-6}\end{array}$	$\begin{array}{c} 4 \\ 0.0083 \\ {9.3375e-6}\end{array}$
$100$	$x_{2}^{0}$	$\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 6 \\ 0.0106 \\ {3.3940e-6}\end{array}$	$\begin{array}{c} 4 \\ 0.0081 \\ {3.8226e-6}\end{array}$	$\begin{array}{c} 4 \\ 0.0104 \\ {7.3068e-6}\end{array}$
	$x_{1}^{0}$	$\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 7 \\ 1.6359 \\ {1.9182e-6}\end{array}$	$\begin{array}{c} 4 \\ 1.0504 \\ {2.4378e-6}\end{array}$	$\begin{array}{c} 4 \\ 0.9420 \\ {9.34412e-6}\end{array}$
$1000$	$x_{2}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 6 \\ 1.4547 \\ {3.2870e-6}\end{array}$	$\begin{array}{c} 3 \\ 0.6995 \\ {4.1163e-6}\end{array}$	$\begin{array}{c} 4 \\ 0.9617 \\ {7.3117e-6}\end{array}$
	$x_{1}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 7 \\ 7.2802 \\ {1.9091e-6}\end{array}$	$\begin{array}{c} 4 \\ 4.1854 \\ {1.2187e-6}\end{array}$	$\begin{array}{c} 4 \\ 4.1506 \\ {9.3440e-6}\end{array}$
$2000$	$x_{2}^{0}$	$\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 6 \\ 6.1432 \\ {3.2795e-6}\end{array}$	$\begin{array}{c} 3 \\ 3.0415 \\ {2.0590e-6}\end{array}$	$\begin{array}{c} 4 \\ 4.8948 \\ {7.3116e-6}\end{array}$
	$x_{1}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 7 \\ 20.3593 \\ {1.9059e-6}\end{array}$	$\begin{array}{c} 3 \\ 8.6417 \\ {6.7655e-6}\end{array}$	$\begin{array}{c} 4 \\ 11.5123 \\ {9.3440e-6}\end{array}$
$3000$	$x_{2}^{0}$	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 6 \\ 18.1800 \\ {3.2770e-6}\end{array}$	$\begin{array}{c} 3 \\ 8.6375 \\ {1.3729e-6}\end{array}$	$\begin{array}{c} 4 \\ 11.6423 \\ {7.3116e-6}\end{array}$

Table 3 Numerical results for example 5.

The true solution is

\[ x^{\ast }=(0.8477,\, 0.8618,\, 0.8621,\ldots ,\, 0.8621,\, 0.8618,\, 0.8477)^{T}, \]

and then

\[ z^{\ast }=(1.6954,1.7237,1.7241,\ldots ,1.7241,1.7237,1.6954)^{T} \]

is the solution of LCP.

Example 6

The matrices $A$ and $B$ are given by:

\begin{align*} A=& (a_{ij})= \begin{cases} a_{ii}=10001, & \mbox{if } i=1, \\ a_{ij}=\frac{1}{i+j-1}, & \mbox{if } i\neq j, \\ a_{ii}=\frac{1}{i+j-1}+1, & i=j,i\neq 1,\end{cases}\\ B=& I. \end{align*}

For example, if $n=4$, then:

\[ A=\left( \begin{smallmatrix} 10001 & \frac{1}{2} & \frac{1}{3} & \frac{1}{4} \\ \frac{1}{2} & \frac{4}{3} & \frac{1}{4} & \frac{1}{5} \\ \frac{1}{3} & \frac{1}{4} & \frac{6}{5} & \frac{1}{6} \\ \frac{1}{4} & \frac{1}{5} & \frac{1}{6} & \frac{8}{7}\end{smallmatrix}\right). \]

The spectrum of $A$ is given by $\left\{ 10001,1.657,1.0189,1.0002\right\} $. Since $\lambda _{\min }(A)=1.0002{\gt} \lambda _{\max }(I)=1,$ then the AVE is uniquely solvable for any $b$. The matrix $A$ is ill-conditioned since $\kappa (A)=\frac{10001}{1.0002}=9999 \gg 1$. Based on $\kappa (A)$, we have deduced that $\kappa (Q)\gg 1$ for some matrices $D$ whose diagonal elements are $1$, $0$, or $-1$, which confirms for $n=4$ that $Q$ is ill conditioned. For $n \geq 4$, a careful investigation is needed to confirm the ill-conditioning of $Q$. In fact, the matrix $A$ is constructed from the Hilbert matrix, which is known to be ill-conditioned.

Next, for $b=(A-I)e\in \mathbb {R}^{n},$ and with the initial point $x_{0}=(0,0,\cdots ,0)^{T},$ the computational results for this example with different size of $n$, are illustrated in table 4.

Size $n$		$P=I$ (basic CGA)	$P=\frac{1}{n}I, n{\gt}1$	$P=A^{-1}$
4	$\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \text{RSD}\end{array}$	$\begin{array}{c} 3530 \\ 0.1300 \\ {9.9959e-6}\end{array}$	$\begin{array}{c} 2701 \\ 0.0983 \\ {9.9952e-6}\end{array}$	$\begin{array}{c} 2 \\ 0.0050 \\ {4.1168e-16}\end{array}$
10	$\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}$	$\begin{array}{c} 16483 \\ 0.6712 \\ {9.9991e-6}\end{array}$	$\begin{array}{c} 12079 \\ 0.4594 \\ {9.9983e-6}\end{array}$	$\begin{array}{c} 2 \\ 0.0051 \\ {6.753e-16}\end{array}$
1000	$\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \text{RSD}\end{array}$	$*$	$*$	$\begin{array}{c} 2 \\ 0.2494 \\ {3.9550e-14}\end{array}$
2000	$\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \text{RSD}\end{array}$	$\begin{array}{c} * \\*\end{array}$	$\begin{array}{c} * \\*\end{array}$	$\begin{array}{c} 2 \\ 1.5669 \\ {7.2000e-14}\end{array}$

Table 4 Numerical results for example 6.

The "*" means that the basic CG and the preconditioned CG with $P=\frac{1}{n} I,n{\gt}1$ algorithms failed.

The true solution of this example is $x^{\ast }=e$.

5 Conclusion and future work

In this paper, we have presented preconditioned conjugate gradient methods for solving the NP-hard absolute value equations. The obtained numerical results with the preconditioned matrix $P=A^{-1}$ are the best since the number of iterations and the elapsed times are minimum compared with those obtained by the basic conjugate gradient algorithms $(P=I).$ We hope that the preconditioned absolute value equations serves as a basis for future research on other more choice for the preconditioned matrix $P$ to intend an efficient study of the absolute value equations.

Bibliography

1: M. Achache, N. Hazzam, Solving absolute value equations via linear complementarity and interior-point methods, J. Nonl. Funct. Anal., 2018, pp. 1–10. $\includegraphics[scale=0.1]{ext-link.png}$
2: M.A. Noor, J. Iqbal, E. Al-Said, Residual iterative method for solving absolute value equations, Abstract Appl. Anal., Article ID 406232, (2012), pp. 1–9. $\includegraphics[scale=0.1]{ext-link.png}$
3: R.W. Cottle, J.S. Pang, R.E. Stone, The Linear Complementarity Problem, Academic Press, New-York, 1992.
4: R. Fletcher, Practical Methods of Optimization, John Wiley and Sons, New-York, 1987.
5: R. Fletcher, C.M. Reeves, Functions minimization by conjugate gradients, Computational Journal, 7 (1964), pp. 149–154. $\includegraphics[scale=0.1]{ext-link.png}$
6: M. Hladick, Bounds for the solution of absolute value equations, Comput. Optimiz. Appl., 69 (2018), pp. 243–266. $\includegraphics[scale=0.1]{ext-link.png}$
7: J. Iqbal, M.A. Noor, K.I. Noor, On iterative method for solving absolute value equations, Optimiz. Lett., 6 (2012), pp. 1027–1033. $\includegraphics[scale=0.1]{ext-link.png}$
8: S. Ketabchi, H. Moosaei, An efficient method for optimal correcting of absolute value equations by minimal changes in the right hand side, Comput. Math. Appl., 64 (2012), pp. 1882–1885. $\includegraphics[scale=0.1]{ext-link.png}$
9: O.L. Mangasarian.A generalized Newton method for absolute value equations. Optimiz. Lett. 3, (2009), pp. 101–108. $\includegraphics[scale=0.1]{ext-link.png}$
10: O.L. Mangasarian, A Newton method for linear programming, J. Optim. Theory Appl., 121 (2004), pp. 1–18. $\includegraphics[scale=0.1]{ext-link.png}$
11: O.L. Mangasarian, R.R. Meyer, Absolute value equations, Linear Algebra Appl., 419 (2006), pp. 359–367. $\includegraphics[scale=0.1]{ext-link.png}$
12: T. Migot, L. Abdellah, M. Haddou, Solving absolute value equation using complementarity and smoothing functions, Comput. Appl. Math., 327 (2018),
pp. 196–207. $\includegraphics[scale=0.1]{ext-link.png}$
13: L. Lehmann, M. Radons, M. Rump, CH. Strom, Sign controlled solvers for the absolute value equation with an application to support vector machines, 2010.
14: J. Rohn, On unique solvability of the absolute value equations, Optimiz. Lett., 3 (2009), pp. 603–606. $\includegraphics[scale=0.1]{ext-link.png}$
15: J. Rohn, An algorithm for computing all solutions of an absolute value equation, Optimiz. Lett., 6 (2012), pp. 851–856. $\includegraphics[scale=0.1]{ext-link.png}$
16: Y. Shi, Modified quasi-Newton methods for solving systems of linear equations, Int. J. Contemp. Math. Sci., 15 (2007), pp. 737–744. $\includegraphics[scale=0.1]{ext-link.png}$
17: G. Zoutendijk, Nonlinear Programming, Computational Methods, in: Integer and Nonlinear Programming, J. Abadie, ed., North- Holland, Amsterdam, 1970, pp. 37–86.
18: N. Ujevic, A new iterative method for solving linear systems, Appl. Math. Comput., 179 (2006), pp. 725–730. $\includegraphics[scale=0.1]{ext-link.png}$

Size \(n\)	\(x_{0}\)		\(P=I\) (basic CGA)	\(P=\frac{1}{n}I,n{\gt}1\)	\(P=A^{-1}\)
	\(x_{1}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 29 \\ 0.0186 \\ {6.0870e-6}\end{array}\)	\(\begin{array}{c} 21 \\ 0.0161 \\ {8.4089e-6}\end{array}\)	\(\begin{array}{c} 2 \\ 0.0057 \\ {4.5068e-07}\end{array}\)
\(100\)	\(x_{2}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 27 \\ 0.0178 \\ {6.7790e-6}\end{array}\)	\(\begin{array}{c} 19 \\ 0.0158 \\ {9.1783e-6}\end{array}\)	\(\begin{array}{c} 3 \\ 0.0074 \\ {6.9333e-06}\end{array}\)
	\(x_{1}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 33 \\ 3.5787 \\ {5.4336e-6}\end{array}\)	\(\begin{array}{c} 21 \\ 2.4979 \\ {8.5594e-6}\end{array}\)	\(\begin{array}{c} 2 \\ 0.2273 \\ {4.5352e-08}\end{array}\)
\(1000\)	\(x_{2}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 31 \\ 3.3429 \\ {6.0443e-6}\end{array}\)	\(\begin{array}{c} 19 \\ 2.0959 \\ {9.3010e-6}\end{array}\)	\(\begin{array}{c} 3 \\ 0.3293 \\ {8.8665e-15}\end{array}\)
	\(x_{1}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 34 \\ 26.6083 \\ {5.7908e-6}\end{array}\)	\(\begin{array}{c} 21 \\ 16.2365 \\ {8.4035e-6}\end{array}\)	\(\begin{array}{c} 2 \\ 1.5644 \\ {2.2684e-08}\end{array}\)
\(2000\)	\(x_{2}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 32 \\ 24.4110 \\ {6.4720e-6}\end{array}\)	\(\begin{array}{c} 19 \\ 14.6529 \\ {9.2160e-6}\end{array}\)	\(\begin{array}{c} 3 \\ 2.2716 \\ {1.5029e-14}\end{array}\)
	\(x_{1}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 34 \\ 90.5026 \\ {8.4709e-6}\end{array}\)	\(\begin{array}{c} 21 \\ 53.2645 \\ {8.3032e-6}\end{array}\)	\(\begin{array}{c} 2 \\ 4.9661 \\ {1.5124e-08}\end{array}\)
\(3000\)	\(x_{2}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 32 \\ 83.9471 \\ {9.5473e-6}\end{array}\)	\(\begin{array}{c} 19 \\ 48.7091 \\ {9.1581e-6}\end{array}\)	\(\begin{array}{c} 3 \\ 5.7692 \\ {2.7556e-14}\end{array}\)

Size \(n\)	\(x_{0}\)		\(P=I\) (basic CGA)	\(P=\frac{1}{n}I,n{\gt}1\)	\(P=A^{-1}\)
	\(x_{1}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 11 \\ 0.0143 \\ {6.1357e-6}\end{array}\)	\(\begin{array}{c} 8 \\ 0.0133 \\ {5.7939e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 0.0081 \\ {4.8013e-8}\end{array}\)
\(100\)	\(x_{2}^{0}\)	\(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 10 \\ 0.0170 \\ {5.6321e-6}\end{array}\)	\(\begin{array}{c} 7 \\ 0.0113 \\ {5.1941e-6}\end{array}\)	\(\begin{array}{c} 3 \\ 0.0068 \\ {2.0096e-6}\end{array}\)
	\(x_{1}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 11 \\ 1.1760 \\ {5.8906e-6}\end{array}\)	\(\begin{array}{c} 7 \\ 0.7838 \\ {2.5537e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 1.5308 \\ {4.8112e-8}\end{array}\)
\(1000\)	\(x_{2}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 10 \\ 1.1115 \\ {5.4239e-6}\end{array}\)	\(\begin{array}{c} 6 \\ 0.6666 \\ {2.2815e-6}\end{array}\)	\(\begin{array}{c} 3 \\ 1.1335 \\ {2.0219e-6}\end{array}\)
	\(x_{1}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 11 \\ 8.9451 \\ {5.8609e-6}\end{array}\)	\(\begin{array}{c} 6 \\ 4.7227 \\ {5.7002e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 5.5383 \\ {4.8116e-8}\end{array}\)
\(2000\)	\(x_{2}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 10 \\ 8.1684 \\ {5.4023e-6}\end{array}\)	\(\begin{array}{c} 5 \\ 4.0932 \\ {5.0782e-6}\end{array}\)	\(\begin{array}{c} 3 \\ 5.3227 \\ {2.0226e-6}\end{array}\)
	\(x_{1}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 11 \\ 28.4459 \\ {5.8503e-6}\end{array}\)	\(\begin{array}{c} 6 \\ 15.5639 \\ {3.7993e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 13.9749 \\ {4.8117e-8}\end{array}\)
\(3000\)	\(x_{2}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 10 \\ 25.7548 \\ {5.3948e-6}\end{array}\)	\(\begin{array}{c} 5 \\ 12.8931 \\ {3.3853e-6}\end{array}\)	\(\begin{array}{c} 3 \\ 10.7083 \\ {2.0228e-6}\end{array}\)

Size \(n\)	\(x_{0}\)		\(P=I\) (basic CGA)	\(P=\frac{1}{n}I,n{\gt}1\)	\(P=A^{-1}\)
	\(x_{1}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 7 \\ 0.0152 \\ {2.0378e-6}\end{array}\)	\(\begin{array}{c} 5 \\ 0.0090 \\ {2.3141e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 0.0083 \\ {9.3375e-6}\end{array}\)
\(100\)	\(x_{2}^{0}\)	\(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 6 \\ 0.0106 \\ {3.3940e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 0.0081 \\ {3.8226e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 0.0104 \\ {7.3068e-6}\end{array}\)
	\(x_{1}^{0}\)	\(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 7 \\ 1.6359 \\ {1.9182e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 1.0504 \\ {2.4378e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 0.9420 \\ {9.34412e-6}\end{array}\)
\(1000\)	\(x_{2}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 6 \\ 1.4547 \\ {3.2870e-6}\end{array}\)	\(\begin{array}{c} 3 \\ 0.6995 \\ {4.1163e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 0.9617 \\ {7.3117e-6}\end{array}\)
	\(x_{1}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 7 \\ 7.2802 \\ {1.9091e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 4.1854 \\ {1.2187e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 4.1506 \\ {9.3440e-6}\end{array}\)
\(2000\)	\(x_{2}^{0}\)	\(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 6 \\ 6.1432 \\ {3.2795e-6}\end{array}\)	\(\begin{array}{c} 3 \\ 3.0415 \\ {2.0590e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 4.8948 \\ {7.3116e-6}\end{array}\)
	\(x_{1}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 7 \\ 20.3593 \\ {1.9059e-6}\end{array}\)	\(\begin{array}{c} 3 \\ 8.6417 \\ {6.7655e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 11.5123 \\ {9.3440e-6}\end{array}\)
\(3000\)	\(x_{2}^{0}\)	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 6 \\ 18.1800 \\ {3.2770e-6}\end{array}\)	\(\begin{array}{c} 3 \\ 8.6375 \\ {1.3729e-6}\end{array}\)	\(\begin{array}{c} 4 \\ 11.6423 \\ {7.3116e-6}\end{array}\)

Size \(n\)		\(P=I\) (basic CGA)	\(P=\frac{1}{n}I, n{\gt}1\)	\(P=A^{-1}\)
4	\(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \text{RSD}\end{array}\)	\(\begin{array}{c} 3530 \\ 0.1300 \\ {9.9959e-6}\end{array}\)	\(\begin{array}{c} 2701 \\ 0.0983 \\ {9.9952e-6}\end{array}\)	\(\begin{array}{c} 2 \\ 0.0050 \\ {4.1168e-16}\end{array}\)
10	\(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\)	\(\begin{array}{c} 16483 \\ 0.6712 \\ {9.9991e-6}\end{array}\)	\(\begin{array}{c} 12079 \\ 0.4594 \\ {9.9983e-6}\end{array}\)	\(\begin{array}{c} 2 \\ 0.0051 \\ {6.753e-16}\end{array}\)
1000	\(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \text{RSD}\end{array}\)	\(*\)	\(*\)	\(\begin{array}{c} 2 \\ 0.2494 \\ {3.9550e-14}\end{array}\)
2000	\(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \text{RSD}\end{array}\)	\(\begin{array}{c} * \\*\end{array}\)	\(\begin{array}{c} * \\*\end{array}\)	\(\begin{array}{c} 2 \\ 1.5669 \\ {7.2000e-14}\end{array}\)