 Applied Mathematics, 2011, 2, 1462-1468 doi:10.4236/am.2011.212208 Published Online December 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. 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 E-mail: {*golbabai, molavi}@iust.ac.ir 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  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 (,,,,,, )xxyy xyuufxytuuuut (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 Axb, (2.1), where A is a large sparse non-symmetric matrix. Let 0x present an arbitrary initial guess to x and 00rbAx 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 0xxw. 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 min22() ()KAAA A (3.1) with (1)(KK1), the distance to the exact solution x in the iteration is bounded by thi*0222ii*xxKxx , (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 12MMM then the precondi- tioned system is as 11 1122 1()MAMMxMb , (3.3) the matrices 1M and 2M 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 11kk1xMNx 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()MDL then we have SOR preconditioner where for 1, we have Gauss-Seidel preconditioner. If M is defined as 11()((2 ))MDLDDU, 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 ))MDL) as a left preconditioner and 12(MDD U as a right preconditioner. Also, we take 2211optJ . 3.2. ADI Preconditioner Let AHV and matrix A is in the form Copyright © 2011 SciRes. AM A. GOLBABAI ET AL. 1464 1122 2111nnnnnBCAB CAABCAB  where 111{,,}i iiiAtridiagabc{,,iCtridiagabc, and 333iii of order where H and V are given in the form 31222{,,}i iiiBtridiagabc}NN{0.5,,}iiiHBb b}c, 11 33iiiii. The alternative direction im- plicit method  for solving the linear system {0.5,,,,VBacaAxb is in following form: (1/2) ()11() ()k,kHrI ubVrI u (3.5) (1) (1/2)22()( )kkVrIub HrIu ,) (3.6) The ADI preconditioner is defined as 12()(MHrIVrI and 11()MHrI and 22()MVrI where Parameters 1 and 2 are ac-celeration parameters. Young and Varga [20,21] proved r rthat the optimum value for and is 1r2r 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 . 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 2NN211222111nnnnnBCAB CAABCAB  where i, iABNG and i are tri-diagonal matrices of order . The splitting of matrix A is sum of matrices and 2 in which CN1G12AGG where and are of the form 1G2G12233111nnnnBBCABGBCAB and 112222211nnnnnBCABGBCABB for odd values of n where 12iBiB). The BLAGE pre- conditioner is as 112 2()(MGIG I that 111()MGI and 222()MGI 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. 6102NN2yTest: We consider 2 -D partial differential equation: exp( )cos()xxyyx ytuuuuru tx  (4.1) with Dirichlet boundary conditions on the unit square where (,, )exp()cos()sin()uxyttx y. (4.2) where 4510 . 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. Copyright © 2011 SciRes. AM A. GOLBABAI ET AL.1465 Tabale 1. Number of iterations with GMRES. h no pre Jacobi SORSSOR ADI BLAGE1/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 BLAGE1/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 BLAGE1/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 BLAGE1/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 BLAGE1/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). Copyright © 2011 SciRes. AM 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. Copyright © 2011 SciRes. AM 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  L. C. Evans, “Partial Differential Equations,” American Mathematical Society Providence, Rhode Island, 1999.  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  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  L. C. Evans, “Partial Differential Equations,” American Mathematical Society Providence, Rhode Island, 1999.  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  A. M. Bruaset, “A Survey of Preconditioned Iterative Methods,” Longman Scientific and Technical, UK, 1995.  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.  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.  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  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  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  Y. Zhang, “Matrix Theory Basic Results and Tech-niques,” Springer, Berlin, 1999.  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  Y. Saad, “Iterative Methods for Sparse Linear Systems,” Second Edition, PWS Publishing Company, Boston, 2000.  H. A. Van der Vorst, “Iterative Krylov Subspace Methods for Large Linear Systems,” Cambridge University Press, Cambridge, 2003. doi:10.1017/CBO9780511615115  O. Axelsson, “Iterative Solution Methods,” Cambridge University Press, New York, 1996.  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  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. Copyright © 2011 SciRes. AM A. GOLBABAI ET AL. Copyright © 2011 SciRes. AM 1468 doi:10.1016/S0898-1221(03)00154-8  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  D. M. Young, “Iterative Solution of Large Linear Sys- tems,” Academic Press, New York, 1971.  R. S. Varga, “Matrix Iterative Analysis,” Prentice Hall, Englewood Cliffs, 1962.  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  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  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.