Applied Mathematics, 2011, 2, 1462-1468
doi:10.4236/am.2011.212208 Published Online December 2011 (http://www.SciRP.org/journal/am)
On the Behavior of Combination High-Order Compact
Approximations with Preconditioned Methods in the
Diffusion-Convection Equation
Ahmad Golbabai1*, Mahboubeh Molavi-Arabshahi2
1Islamic Azad University, Karaj Branch, Karaj, Iran
2Faculty of Mathematics, Iran University of Science and Technology, Narmak, Iran
Received July 20, 201 1; revised November 20, 2011; accepted November 24, 2011
Abstract
In this paper, a family of high-order compact finite difference methods in combination preconditioned me-
thods are used for solution of the Diffusion-Convection equation. We developed numerical methods by re-
placing the time and space derivatives by compact finite- difference approximations. The system of resulting
nonlinear finite difference equations are solved by preconditioned Krylov subspace methods. Numerical re-
sults are given to verify the behavior of high-order compact approximations in combination preconditioned
methods for stability, convergence. Also, the accuracy and efficiency of the proposed scheme are considered.
Keywords: Compact High-Order Approximation, Diffusion-Convection Equation, Krylov Subspace Methods,
Preconditioner
1. Introduction
Recently, various powerful mathematical methods such
as the homotopy perturbation method, variational itera-
tion method, Adomian decomposition method and others
[1-3] have been proposed to obtain approximate solu-
tions in partial differential equations (PDEs). The 2-D
parabolic differential equations appeared in many scien-
tific fields of engineering and science such as neutron
diffusion, heat transfer and fluid flow problems. Many
computational models give rise to large sparse linear sy-
stems. For such systems iterative methods are usually
preferred to direct methods which are expensive both in
memory and computing requirements. Krylov subspace
methods are one of the widely used and successful classes
of numerical algorithms for solving large and sparse sys-
tems of algebraic equations but the speed of these meth-
ods are slow for problems which arise from typical appli-
cations. In order to be effective an d obtaining faster con-
vergence, these methods should be combined with a sui-
table preconditioner. The convergence rate generally de-
pends on the co ndition number of the corresponding ma-
trix. Since the preconditioner plays a critical role in pre-
conditioned Krylov subspace methods, many precondi-
tioner have been proposed and studied [4-6]. The ADI
method is a preconditioner [7,8] that can be effective for
the 2-D problems but this method is not effective for
more general tri-block diagonal systems. Bhuruth and
Evans [9] proposed BLAGE method as a preconditioner
for a class of non-symmetric linear systems. Based on
author’s observatio ns, there is not a comprehensiv e study
for comparison of preconditioning techn iques to solve li-
near systems. In this paper, we accomplish a comprehen-
sive study for different preconditioners in combination
with Krylov subspace methods for solving linear systems
arising from the compact finite difference schemes [10,
11] for 2-D pa r a bol i c e qu a t i on
(,,,,,, )
x
xyy xy
uufxytuuuu
t


 (1.1)
is defined in the region

0,1, 0Wx xyt,
where α, β are positive constants. The initial conditions
are:
0
(, ,0)(, ),0,1uxyuxyx y

, (1.2)
and boundary conditions consists of
01
(0, ,)(,),(1, ,)(,),0uythytuythytt

 (1.3)
01
( ,0,)( ,),( ,1,)( ,),0,uxtgxtuxtgxtt

 (1.4)
The resulting block tri-diagonal lin ear system of equa-
tions is solved by using Krylov subspace methods.

A. GOLBABAI ET AL.1463
Krylov subspace methods are one of the widely used
and successful classes of numerical algorithms for solv-
ing large and sparse systems of algebraic equations but
the speed of these methods are slow for problems which
arise from typical applications [12-15]. In order to be
effective and obtaining faster convergence, these meth-
ods should be combined with a suitable preconditioner.
The rate of convergence generally depends on the condi-
tion number of the corresponding matrix. Since the pre-
conditioner plays a critical ro le in preconditioned Krylov
subspace methods, many preconditioners have been pro-
posed and studied [6,16-18] amongst the ADI precondi-
tioner.
In this paper, we accomplish a comprehensive study
for different preconditio ners in combination with Krylov
subspace methods for solving linear systems arising from
the compact high-order approximations. The resulting
block tri-diagonal linear system of equations is solved by
using Krylov subspace m e t hods.
The outline of the paper is as follows:
In Section 2, we briefly introduce Krylov subspace
methods and in Section 3, we consider some available
preconditioners. In Section 4, we consider Diffusion-
Convection problem arising from the compact high-order
approximations. We present the results of our compara-
tive study in the final section.
2. Krylov Subspace Methods
Consider the linear system
A
xb, (2.1),
where A is a large sparse non-symmetric matrix. Let 0
x
present an arbitrary initial guess to x and 00
rbAx


be a corresponding residual vector. An iterative scheme
for solving (2.1) is called a Krylov subspace method if
for any choice of w, it produces approximate solutions of
the form 0
x
xw.
In Section 4, we solve our problem with well-known
Krylov subspace methods such as Generalized minimal
residual method GMRES (m), Quasi minimal residual me-
thod (QMR), Bi-Conjugate Gradient method (BiCG), Con-
jugate gradient squared method (CGS) and Bi-Conjugate
Gradient Stabilized method (BiCGSTAB) for more com-
plete explanation refer to [13-15].
3. Preconditioner
The convergence rate of iterative methods highly de-
pends on the eigen-value distribution of the coefficient
matrix. A criterion for the width of the spectrum is the
Euclidean cond ition number for SPD matrices is
1max min
22() ()
K
AAA A 

 (3.1)
with (1)(KK
 1)

 , the distance to the exact
solution
x

in the iteration is bounded by
th
i
*0
22
2
ii*
x
xKxx   , (3.2)
the right hand side of (3.2) increases with growing con-
dition number. Hence, lower condition numbers usually
accelerate the speed of convergence. Hence we will at-
tempt to transform the linear system into ano ther equiva-
lent system in the sense that it has th e same solution, but
has more favorable spectral properties. A preconditioner
is a matrix that effects such as a transformation. If the
preconditioner be as 12
M
MM

then the precondi-
tioned system is as
11 1
122 1
()
M
AMMxMb
 
, (3.3)
the matrices 1
M
and 2
M
are called the left and right
preconditioners, respectively. Now, we briefly describe
preconditioners that we use for solving linear systems
and matrix A is block tri-diagonal.
3.1. Preconditioner Based on Relaxation
Technique
Let A = D + L + U such that D, L and U are diagonal,
lower and upper triangular block matrices, respectively.
A splitting of the coefficient matrix is as A = M – N
where the stationary iteration for solving a linear system
is as
1
1kk
1
x
MNx Mb



. (3.4)
If the preconditioner M is defined as M = D, then this
preconditioner is called Jacobi. Also, if M is defined as
1()
M
DL


 then we have SOR preconditioner
where for 1


, we have Gauss-Seidel preconditioner.
If M is defined as 1
1()(
(2 ))
M
DLDDU 



,
we get SSOR preconditioner. In the above notation,

is called the relaxation parameter. We have chosen ma-
trix M in Jacobi, G-S and SOR methods as a left precon-
ditioner and in SSOR preconditioner, we have chosen
11(
(2 ))
M
DL




)
as a left preconditioner and
1
2(
M
DD U 

 as a right preconditioner. Also, we
take 2
2
11
opt
J


 [6].
3.2. ADI Preconditioner
Let
A
HV

 and matrix A is in the form

A. GOLBABAI ET AL. 1464
11
22 2
111nnn
nn
BC
AB C
A
ABC
AB









 
where
111
{,,}
i iii
A
tridiagabc{,,
i
Ctridiagabc, and
333iii of order where H and V
are given in the form 31
222
{,,}
i iii
Btridiagabc
}NN
{0.5,,}
iii
H
Bb b
}c
,
11 33iiiii
. The alternative direction im-
plicit method [19] for solving the linear system
{0.5,,,,VBaca
A
xb

is in following form:
(1/2) ()
11
() ()
k, k
H
rI ubVrI u

 (3.5)
(1) (1/2)
22
()( )
kk
VrIub HrIu

 ,
)
(3.6)
The ADI preconditioner is defined as
12
()(
M
HrIVrI and 11 ()
M
HrI and
22
()
M
VrI where Parameters 1 and 2 are ac-
celeration parameters. Young and Varga [20,21] proved
r r
that the optimum value for and is
1
r2 r

 where
ii
,

   and ,
ii

 are eigen-values of matrices
H and V respectively.
3.3. BLAGE Preconditioner
The block alternating group explicit (BLAGE) method
[22,23] was originally introduced as analogue of the al-
ternating group explicit (AGE) method [24]. The BLA-
GE uses fractional splitting technique that is applied in
two half steps on linear systems with block tri-diagonal
matrices of order and in the form
2
NN2

11
222
111nnn
nn
BC
AB C
A
ABC
AB









 
where i ,
i
A
B
N
G
and i are tri-diagonal matrices of order
. The splitting of matrix A is sum of matrices
and 2 in which
C
N1 G
12
A
GG where and
are of the form 1
G2 G
1
22
33
1
11nn
nn
B
BC
AB
G
BC
AB



























and
11
22
222
11
nn
nn
n
BC
AB
GBC
AB
B


















for odd values of n where 1
2
i
B
i
B
)
. The BLAGE pre-
conditioner is as 112 2
()(
M
GIG I



 that
111
()
M
GI


 and 222 ()
M
GI


 where 1

and
2

are optimal iteration parameters. We have experi-
mentally chosen the relaxation parameter 112

 
and 221

  where 1min1 ()
M

 ,
1max1
()
M



and 2min2 ()
M



, 2max2 ()
M

 
so that we will have the minimum condition number.
4. Numerical Illustrations
In this section, we present one numerical example to
show the computational efficiency of the preconditioner
which introduced in Section 3. Our initial guess is the
zero vector and the iterations are stopped when the rela-
tive residual is less than . We show the number of
outer iterations and inner iterations GMRES (m) method
with “ou” and “in” respectively in following tables. Also,
we show the iteration number without using precondi-
tioner by “no pre” and the coefficient matrix is order of
. The computations have been done on a P.C.
with Corw 2 Pue 2.0 Ghz and 1024 MB RAM.
6
10
2
NN2
y
Test: We consider 2 -D partial differential equation:
exp( )cos()
xxyyx yt
uuuuru tx


  (4.1)
with Dirichlet boundary conditions on the unit square
where
(,, )exp()cos()sin()uxyttx y

. (4.2)
where 4 510 

 . We apply the fourth-order ap-
proximation for discretization of Equation (4.1) (Figure
1). We have shown the number of iteration for different
preconditioned methods in Tables 1-5 or different pre-
conditioners. The convergence behavior of precondi-
tioned Krylov subspace methods is given by Figures 2-7.
Also, in Figures 8-10 for we show the distribution of
eigen-values SSOR, ADI and BLAGE preconditioners.
In this test the condition number of problem is high and
our problem is ill-conditioned. So, in regard of other
preconditioner, results show the ADI preconditioner re-
quires more iteration. It is seen that we obtain the opti-
mal convergence with SSOR and BLAGE preconditioner
and our time consumption is reduced.

A. GOLBABAI ET AL.1465
Tabale 1. Number of iterations with GMRES.
h no pre Jacobi SORSSOR ADI BLAGE
1/20 75 54 36 21 33 26
1/40 124 89 61 36 61 51
1/60 119 87 60 35 65 54
1/80 139 102 58 37 76 63
1/100 162 119 58 40 87 72
Tabale 2. Number of iterations with QMR.
h no pre Jacobi SORSSOR ADI BLAGE
1/20 79 56 48 22 40 34
1/40 152 96 99 33 72 55
1/60 162 109 95 39 77 61
1/80 189 137 67 34 97 77
1/100 225 149 63 39 102 79
Tabale 3. Number of iterations with CGS.
H no pre Jacobi SORSSOR ADI BLAGE
1/20 62 36 28 14 27 18
1/40 81 50 43 18 40 35
1/60 93 56 37 20 42 34
1/80 114 74 41 26 57 47
1/100 146 N 42 31 73 49
Tabale 4. Number of iterations with BiCG.
h no pre Jacobi SORSSOR ADI BLAGE
1/20 85 57 52 22 41 34
1/40 152 99 97 36 72 55
1/60 162 108 86 39 77 67
1/80 190 137 67 34 95 73
1/100 223 131 67 39 99 87
Tabale 5. Number of iterations with BiCGSTAB.
h no pre Jacobi SORSSOR ADI BLAGE
1/20 62 46 23 15 31 17
1/40 81 60 36 21 43 25
1/60 86 54 38 19 45 30
1/80 103 72 37 22 52 41
1/100 135 95 36 26 65 49
Figure 1. The 3D error of the compact fite diffence scheme
with time T = 10.
Figure 2. Convergence plot of GMRES.
Figure 3. Convergence plot of GMRES (15).

A. GOLBABAI ET AL. 1466
Figure 4. Convergence plot of QMR.
Figure 5. Convergence plot of CGS.
Figure 6. Convergence plot of BiCG.
Figure 7. Convergence plot of BiCGSTAB.
Figure 8. Distribution of eigen-values in SSOR precondi-
tioner.
Figure 9. Distribution of eigen-values in ADI Preconditioner.

A. GOLBABAI ET AL.1467
Figure 10. Distribution of eigen-values in BLAGE precon-
ditioner.
5. Conclusions
A high-order compact scheme in combination precondi-
tioner was applied successfully to Diffusion- Convection
equation. We study comparison of different precondi-
tioners in combination Krylov subspace methods. High-
order approximation are designed by the need to produce
more stable schemes which are efficient with respect to
the operation number and that do not experience difficul-
ties near boundaries. The numerical results which is given
in the previous section d emonstrate the good accuracy of
this scheme and efficiency of preconditioned Krylov sub-
space methods. We got to this conclusion that the ADI
preconditioner is effective for model problems rather
than other. So we propose using ADI preconditioner in
combination with Krylov subspace methods for solving
non-symmetric systems because this preconditioner needs
to less computing time and have the less iteration number
than other. Also, we propose the BiCGSTAB method
because of the need to less iteration number, simplicity
in implementation, flat convergence and to save in comp
tational time.
6. References
[1] L. C. Evans, “Partial Differential Equations,” American
Mathematical Society Providence, Rhode Island, 1999.
[2] A. Golbabai and M. M. Arabshahi, “A Numerical Method
for Diffusion-Convection Equation Using High-Order
Difference Schemes,” Computer Physics Communica-
tions, Vol. 181, No. 7, 2010, pp. 1224-1230.
doi:10.1016/j.cpc.2010.03.008
[3] A. Golbabai and M. M. Arabshahi, “On the Behavior of
High-Order Compact Approximations in One Dimen-
sional Sine-Gordon Equation,” Physica Scripta, Vol. 83,
No. 1, 2011, Article ID 015015.
doi:10.1088/0031-8949/83/01/015015
[4] L. C. Evans, “Partial Differential Equations,” American
Mathematical Society Providence, Rhode Island, 1999.
[5] S. Sundar and B. K. Bhagavan, “CGS, Comparison of
Krylov Subspace Methods with Preconditioning Tech-
niques for Solving Boundary Value Problems,” Com-
puters and Mathematics with Applications, Vol. 38, No.
11-12, 1999, pp. 197-206.
doi:10.1016/S0898-1221(99)00298-9
[6] A. M. Bruaset, “A Survey of Preconditioned Iterative
Methods,” Longman Scientific and Technical, UK, 1995.
[7] K. J. Hout and B. D. Welfert, “Unconditional Stability of
Second-Order ADI Schemes Applied to Multi-Dimen-
sional Diffusion Equations with Mixed Derivative Terms,”
Applied Numerical Mathematics, 2008, Article in Press.
[8] S. Ma and Y. Saad, “Block-ADI Preconditioners for
Solving Sparse Non-Symmetric Linear Systems of Equa-
tions,” Numerical Linear Algebra, 1993, pp. 165-178.
[9] M. Bhuruth and D. J. Evans, “Block Alternating Group
Explicit Preconditioning (BLAGE) for a Class of Fourth-
Order Difference Schemes,” International Journal of
Computer Mathematics, Vol. 63, No. 1-2, 1997, pp. 121-
136. doi:10.1080/00207169708804555
[10] M. K. Jain, R. K. Jain and R. K. Mohanty, “Fourth-Order
Finite Difference Method for 2-D Parabolic Partial Dif-
ferential Equations with Non-Linear First-Derivative
Terms,” Numerical Methods for Partial Differential
Equations, Vol. 8, No. 1, 1992, pp. 21-31.
doi:10.1002/num.1690080102
[11] G. I. Shishkin and L. P. Shishkina, “A Higher Order
Richardson Scheme for a Singularly Perturbed Semilinear
Elliptic Convection-Diffusion Equation,” Computational
Mathematics and Mathematical Physics, Vol. 50, No. 3,
2010, pp. 437-456. doi:10.1134/S0965542510030061
[12] Y. Zhang, “Matrix Theory Basic Results and Tech-
niques,” Springer, Berlin, 1999.
[13] R. Barrett, et al., “Templates for the Solution of Linear
Systems: Building Blocks for Iterative Methods,” Society
for Industrial and Applied Mathematics (SIAM), 1994, pp.
xvii+118. doi:10.1137/1.9781611971538
[14] Y. Saad, “Iterative Methods for Sparse Linear Systems,”
Second Edition, PWS Publishing Company, Boston,
2000.
[15] H. A. Van der Vorst, “Iterative Krylov Subspace Methods
for Large Linear Systems,” Cambridge University Press,
Cambridge, 2003. doi:10.1017/CBO9780511615115
[16] O. Axelsson, “Iterative Solution Methods,” Cambridge
University Press, New York, 1996.
[17] M. H. Koulaei and F. Toutounian, “On Computing of
Block ILU Preconditioner for Block Tri-Diagonal Sys-
tems,” Journal of Computational and Applied Mathemat-
ics, Vol. 202, No. 2, 2007, pp. 248-257.
doi:10.1016/j.cam.2006.02.029
[18] R.C. Mittal and A.H. Al-Kurdi, “An Efficient Method for
Constructing an ILU Preconditioner for Solving Large
Sparse Non-Symmetric Linear Systems by the GMRES
Method,” Computers and Mathematics with Applications,
Vol. 45, 2003, pp. 1757-1772.

A. GOLBABAI ET AL. 1468
doi:10.1016/S0898-1221(03)00154-8
[19] D. W. Peaceman and H. H. Rachford, “The Numerical
Solution of Parabolic and Elliptic Differential Equations,”
Journal of the Society for Industrial and Applied Mathe-
matics, Vol. 3, No. 1, 1955, pp. 28-41.
doi:10.1137/0103003
[20] D. M. Young, “Iterative Solution of Large Linear Sys-
tems,” Academic Press, New York, 1971.
[21] R. S. Varga, “Matrix Iterative Analysis,” Prentice Hall,
Englewood Cliffs, 1962.
[22] D. J. Evans and W. S. Yousif, “The Block Alternating
Group Explicit Method (BLAGE) for the Solution of El-
liptic Difference Equations,” International Journal of
Computer Mathematics, Vol. 22, No. 2, 1987, pp. 177-
185. doi:10.1080/00207168708803590
[23] R. K. Mohanty, “Three-Step BLAGE Iterative Method
for Two-Dimensional Elliptic Boundary Value Problems
with Singularity,” International Journal of Computer
Mathematics, Vol. 84, No. 11, 2007, pp. 1613-1624.
doi:10.1080/00207160600825205
[24] D. J. Evans and M. Sahimi, “The Alternating Group Ex-
plicit (AGE) Iterative Method to Solve Parabolic and
Hyperbolic Partial Differential Equations,” Annual Re-
view of Numerical Fluid Mechanics and Heat Transfer,
Vol. 11, 1989, pp. 283-390.