ABSTRACT

We present a flexible version of GPBi-CG algorithm which allows for the use of a different preconditioner at each step of the algorithm. In particular, a result of the flexibility of the variable preconditioner is to use any iterative method. For example, the standard GPBi-CG algorithm itself can be used as a preconditioner, as can other Krylov subspace methods or splitting methods. Numerical experiments are conducted for flexible GPBi-CG for a few matrices including some nonsymmetric matrices. These experiments illustrate the convergence and robustness of the flexible iterative method.

1. Introduction

Krylov subspace methods are the iterative choice for solving linear system of the form

. (1)

where the matrix A is assumed to be nonsingular. The strength of Krylov subspace methods are most apparent when combined with a preconditioner. We only consider right preconditioning in the paper. Thus one solves the equivalent linear system

. (2)

The preconditioner M is selected to be close to the matrix A. And the matrix is never formed explicitly. Instead, when is needed, one solves the corresponding system

. (3)

In this paper, we present a flexible version of GPBiCG, which allows the preconditioner M vary from one iteration to another. Let us denote the matrix the preconditioner used in the nth iteration. The need to allow for a variable preconditioner arises when the solution of (2) is not obtained exactly (say, by a direct method), but is approximated by a second (inner) iterative method.

In recent years, several flexible variants of Krylov subspace methods have been established successfully. They include flexible CG, which is applied on a symmetric positive definite matrix [1], flexible GMRES [2], flexible QMR [3], variable preconditioned GCR [4], flexible BiCG and flexible Bi-CGSTAB [5]. Preconditioning as this form is called flexible preconditioning, also known as variable or inexact preconditioning.

The paper is organized as follows. In the next section, we design the FGPBi-CG algorithm, which is a flexible version of GPBi-CG [6]. In Section 3, some numerical experiments will be conducted to illustrate the convergence of the algorithm. Furthermore, in some cases, it is shown that FGPBi-CG can achieve convergence to a tolerance when GPBi-CG is not convergent or even FBi-CGSTAB suffers stagnation. Finally we make some concluding remarks in Section 4.

Throughout the paper, is the initial approximation, is the initial residual, and the norm used is 2-norm.

2. Flexible GPBi-CG Method

We describe the basic idea of variable preconditioning and how it is incorporated with the algorithm GPBi-CG in this section.

The expression is calculated at each iteration of the conventional preconditioned Krylov subspace methods. The object of preconditioning is to change the original coefficient matrix A into another matrix close to identity, i.e.. Consequently, the following property that approximates can be verified easily.

.

Thus, we consider obtaining an approximation of instead of computing. That is, the following system (4) is roughly solved by an iterative method to a certain degree of accuracy that is not sufficient.

. (4)

Here, an approximation for the system (4) does not need to be solved at the same precision at each iteration. A stopping criteria has been established to make the preconditioner to be changed at each iteration. Different inner-loop can be applied to the system (4) including Krylov subspace methods and stationery iterative methods.

The GPBi-CG algorithm proposed by Zhang [6], uses an unified way to derive a class generalizations of Bi-CG. By choosing different coefficients, namely, the following and, the GPBi-CG algorithm will be reduced to other methods based on Bi-CG includes the well known CGS, Bi-CGSTAB, Bi-CGSTAB2.

Next we present a flexible version of GPBi-CG, which needs only some small modification of the GPBi-CG code.

ALGORITHM (FGP-BiCG with right preconditioner) is an initial guess,; is an arbitrary vector, such that, e.g.,; and set,;

For until do

solve

solve

(if, then)

solve

End do

Noted that if we replace with M, a fixed preconditioner, the above algorithm will be reduced to the standard GPBi-CG method with right preconditioner.

3. Numerical Experiments

In this section, we report some numerical experiments to show the convergence behaviors of FGPBi-CG. In all cases the iteration was started with, and the outer-loop is stopped when the relative residual norm. In the following examples, we use stopping criterion for inner-loop as:

1);

2) The maximum number of iterations of inner loop.

Here, denotes the l-th approximation when computing at k-th steps of the outer-loop.

3.1. Examples for Toeplitz Matrix

In the first example, we consider a Toeplitz matrix of order 200 with a parameter.

In this experiment, we choose to be 3.79 and the inner iteration stopping criteria to be the maximum iteration is and relative residuals range from to. We can see from the Figure 1 that GPBi-CG converges faster than that of Bi-CGSTAB. When the standard GPBi-CG algorithm performs well, the flexible version of GPBi-CG is also convergent, but it need more computation. The results can be seen in Table 1. In the table, “FG(B)” denotes FGPBi-CG with preconditioning Bi-CGSTAB, and so on, while “MV” represents the number of matrix-vector multiplication, “OIt” denotes the number of outer iteration.

From Figure 1 and Table 1, we can see that for the problem that GPBi-CG and Bi-CGSTAB method can convergent fast, FGPBi-CG and FBi-CGSTAB will not gain too much. While FGPBi-CG(GPBi-CG) and FBiCGSTAB(GPBi-CG) will be faster than FGPBiCG(Bi-CGSTAB) and FBi-CGSTAB(Bi-CGSTAB) re-

spectively. Because GPBi-CG used in the inner iteration usually converges faster than Bi-CGSTAB.

Now, we consider another Toeplitz matrix of order 200 with a parameter as following.

In this experiment, we choose to be 1.9 and the inner iteration stopping criteria to be the maximum iteration is and relative residuals range from to.

We can see from the Figure 2 and Table 2 that GPBiCG is convergent while Bi-CGSTAB is not. As a result, when Bi-CGSTAB is used as an inner iteration, the number of matrix vector multiplication is not influenced by the inner relative residual stopping criteria, i.e., the inner iteration is not terminated until it reaches N_max (the largest iterative number of inner loop). For this reason, GPBiCG used as the inner iteration performs better.

3.2. Examples for Model Problem

We consider the finite difference discretization of the par-

tial differential equation ([3,5,7])

(5)

on a unit square, where f is such that the exact solution to the discretized equation is. The parameters and are chosen to have a nonsymmetric matrix. In our experiment, and or. The mesh is chosen of equal size in both dimension (32 nodes), and the corresponding matrix is thus of order 1024.

In the first example, we take, and the inner iteration stopping criteria is ranges from 30 to 70 and relative residuals is.

For this choice, Figure 3 and Table 3 show that both Bi-CGSTAB and GPBi-CG perform quite well for this example, flexible versions of these algorithms are also convergent. If the inner-loop stopping criterion is N_max = 40 and, the FBi-CGSTAB(Bi-CGSTAB) needs 316 matrix vector multiplications to reach the prescribed tolerance, faster than that of Bi-CGSTAB.

In the next experiment, we choose, and the inner iteration stopping criteria is ranges from 90 to 1000 and relative residuals is.

Neither Bi-CGSTAB nor GPBi-CG without preconditioning is convergent for this problem (see Figure 4).

We see from Table 4 that FGPBi-CG and FBiCGSTAB with flexible precondition converges, but the cost of FGPBi-CG is about one and a half that of FBi-

CGSTAB, because there are three inner-loops in the FGPBi-CG algorithm rather than two in FBi-CGSTAB.

And from this table, we see FGPBi-CG (GPBi-CG) converges for most of the inner-loop stopping criteria. When appropriate stopping criteria is used in the inner iteration, the flexible version will be a good choice.

4. Conclusion

We have formulated a flexible version of GPBi-CG for the large sparse nonsymmetric linear systems. The preconditioning is carried out by roughly solving Az = v by an iterative method to a certain degree of precision. In our proposal, the iteration for solving Az = v is stopped according to satisfy a certain accuracy of approximation or the maximum number of iterations, so the preconditioner is changed at each outer iteration. Our numerical experiments show that FGPBi-CG is a viable alternative to GPBi-CG. And some examples show that FGPBi-CG is convergent when GPBi-CG suffers from stagnation.

REFERENCES

NOTES

^*The project is partly supported by the NSF of China (No. 61170309, No. 60973151, and No. 91130024) and the major project of scientific and technical development of China Academy of Engineering Physics (2011A0202012).

^#Corresponding author.