×

An extrapolation cascadic multigrid method combined with a fourth-order compact scheme for 3D Poisson equation. (English) Zbl 1366.65095

Summary: Extrapolation cascadic multigrid (EXCMG) method is an efficient multigrid method which has mainly been used for solving the two-dimensional elliptic boundary value problems with linear finite element discretization in the existing literature. In this paper, we develop an EXCMG method to solve the three-dimensional Poisson equation on rectangular domains by using the compact finite difference (FD) method with unequal meshsizes in different coordinate directions. The resulting linear system from compact FD discretization is solved by the conjugate gradient (CG) method with a relative residual stopping criterion. By combining the Richardson extrapolation and tri-quartic Lagrange interpolation for the numerical solutions from two-level of grids (current and previous grids), we are able to produce an extremely accurate approximation of the actual numerical solution on the next finer grid, which can greatly reduce the number of relaxation sweeps needed. Additionally, a simple method based on the midpoint extrapolation formula is used for the fourth-order FD solutions on two-level of grids to achieve sixth-order accuracy on the entire fine grid cheaply and directly. The gradient of the numerical solution can also be easily obtained through solving a series of tridiagonal linear systems resulting from the fourth-order compact FD discretizations. Numerical results show that our EXCMG method is much more efficient than the classical V-cycle and W-cycle multigrid methods. Moreover, only few CG iterations are required on the finest grid to achieve full fourth-order accuracy in both the \(L^2\)-norm and \(L^{\infty}\)-norm for the solution and its gradient when the exact solution belongs to \(C^6\). Finally, numerical result shows that our EXCMG method is still effective when the exact solution has a lower regularity, which widens the scope of applicability of our EXCMG method.

MSC:

65N06 Finite difference methods for boundary value problems involving PDEs
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65F10 Iterative numerical methods for linear systems

References:

[1] Strikwerda, J.C.: Finite Difference Schemes and Partial Differential Equations. Chapman & Hall, London (1989) · Zbl 0681.65064
[2] Gupta, M.M.: A fourth-order Poisson solver. J. Comput. Phys. 55, 166-172 (1985) · Zbl 0548.65075 · doi:10.1016/0021-9991(84)90022-6
[3] Gupta, M.M., Kouatchou, J.: Symbolic derivation of finite difference approximations for the three-dimensional Poisson equation. Numer. Methods Part. Differ. Equ. 14, 593-606 (1998) · Zbl 0926.65103 · doi:10.1002/(SICI)1098-2426(199809)14:5<593::AID-NUM4>3.0.CO;2-D
[4] Spotz, W.F., Carey, G.F.: A high-order compact formulation for the 3D poisson equation. Numer. Methods Part. Differ. Equ. 12, 235-243 (1996) · Zbl 0866.65066 · doi:10.1002/(SICI)1098-2426(199603)12:2<235::AID-NUM6>3.0.CO;2-R
[5] Sutmann, G., Steffen, B.: High-order compact solvers for the three-dimensional Poisson equation. J. Comput. Appl. Math. 187, 142-170 (2006) · Zbl 1081.65099 · doi:10.1016/j.cam.2005.03.041
[6] Wang, J., Zhong, W., Zhang, J.: A general meshsize fourth-order compact difference discretization scheme for 3D Poisson equation. Appl. Math. Comput. 183, 804-812 (2006) · Zbl 1109.65090
[7] Gupta, M.M., Kouatchou, J., Zhang, J.: Comparison of second-order and fourth-order discretization for multigrid Poisson solvers. J. Comput. Phys. 132, 226-232 (1997) · Zbl 0881.65120 · doi:10.1006/jcph.1996.5466
[8] Othman, M., Abdullah, A.R.: An efficient multigrid Poisson solver. Int. J. Comput. Math. 71, 541-553 (1999) · Zbl 0958.65129 · doi:10.1080/00207169908804828
[9] Schaffer, S.: High order multi-grid methods. Math. Comput. 43, 89-115 (1984) · Zbl 0557.65065
[10] Zhang, J.: Multigrid method and fourth-order compact scheme for 2D Poisson equation with unequal mesh-size discretization. J. Comput. Phys. 179, 170-179 (2002) · Zbl 1005.65137 · doi:10.1006/jcph.2002.7049
[11] Wang, Y., Zhang, J.: Sixth-order compact scheme combined with multigrid method and extrapolation technique for 2D poisson equation. J. Comput. Phys. 228, 137-146 (2009) · Zbl 1157.65469 · doi:10.1016/j.jcp.2008.09.002
[12] Zhang, J.: Fast and high accuracy multigrid solution of the three dimensional Poisson equation. J. Comput. Phys. 143, 449-161 (1998) · Zbl 0927.65141 · doi:10.1006/jcph.1998.5982
[13] Ge, Y.B.: Multigrid method and fourth-order compact difference discretization scheme with unequal meshsizes for 3D poisson equation. J. Comput. Phys. 229, 6381-6391 (2010) · Zbl 1197.65169 · doi:10.1016/j.jcp.2010.04.048
[14] McCormick, S.F. (ed.): Multigrid Methods. Frontiers in Applied Mathematics. SIAM, Philadelphia (1987) · Zbl 0659.65094
[15] Briggs, W.L., McCormick, S.F., Henson, V.E.: A Multigrid Tutorial, 2nd edn. SIAM, Philadelphia (2000) · Zbl 0958.65128 · doi:10.1137/1.9780898719505
[16] Trottenberg, U., Oosterlee, C.W., Schller, A.: Multigrid. Academic Press, London (2001) · Zbl 0976.65106
[17] Moghaderi, H., Dehghan, M., Hajarian, M.: A fast and efficient two-grid method for solving d-dimensional Poisson equations. Numer. Algorithms 72, 483-537 (2016) · Zbl 1342.65226 · doi:10.1007/s11075-015-0057-8
[18] Altas, I., Dym, J., Gupta, M.M., Manohar, R.P.: Multigrid solution of automatically generated high-order discretizations for the biharmonic equation. SIAM J. Sci. Comput. 19, 1575-1585 (1998) · Zbl 0918.65079 · doi:10.1137/S1464827596296970
[19] Zhang, J., Sun, H., Zhao, J.J.: High order compact scheme with multigrid local mesh refinement procedure for convection diffusion problems. Comput. Methods Appl. Mech. Comput. 191, 4661-4674 (2002) · Zbl 1068.76066 · doi:10.1016/S0045-7825(02)00398-5
[20] Ge, Y.B., Cao, F.J.: Multigrid method based on the transformation-free HOC scheme on nonuniform grids for 2D convection diffusion problems. J. Comput. Phys. 230, 4051-4070 (2011) · Zbl 1216.65173 · doi:10.1016/j.jcp.2011.02.027
[21] Wang, Y., Zhang, J.: Fast and robust sixth-order multigrid computation for the three-dimensional convection-diffusion equation. J. Comput. Appl. Math. 234, 3496-3506 (2010) · Zbl 1195.65149 · doi:10.1016/j.cam.2010.05.022
[22] Bornemann, F.A., Deuflhard, P.: The cascadic multigrid method for elliptic problems. Numer. Math. 75, 135-152 (1996) · Zbl 0873.65107 · doi:10.1007/s002110050234
[23] Shaidurov, V.: Some estimates of the rate of convergence for the cascadic conjugate-gradient method. Comput. Math. Appl. 31, 161-171 (1996) · Zbl 0886.65107 · doi:10.1016/0898-1221(95)00228-6
[24] Braess, D., Dahmen, W.: A cascadic multigrid algorithm for the Stokes equations. Numer. Math. 82, 179-191 (1999) · Zbl 0929.65125 · doi:10.1007/s002110050416
[25] Timmermann, G.: A cascadic multigrid algorithm for semilinear elliptic problems. Numer. Math. 86, 717-731 (2000) · Zbl 0969.65111 · doi:10.1007/PL00005416
[26] Shaidurov, V., Tobiska, L.: The convergence of the cascadic conjugate- gradient method applied to elliptic problems in domains with re-entrant cor- ners. Math. Comput. 69, 501-520 (2000) · Zbl 0947.65037 · doi:10.1090/S0025-5718-99-01138-2
[27] Shaidurov, V., Timmermann, G.: A cascadic multigrid algorithm for semi-linear indefinite elliptic problems. Computing 64, 349-366 (2000) · Zbl 0998.65122 · doi:10.1007/s006070070030
[28] Shi, Z.C., Xu, X.J.: Cascadic multigrid for parabolic problems. J. Comput. Math. 18, 551-560 (2000) · Zbl 0964.65103
[29] Braess, D., Deuflhard, P., Lipnikov, K.: A subspace cascadic multigrid method for mortar elements. Computing 69, 205-225 (2002) · Zbl 1239.65076 · doi:10.1007/s00607-002-1460-2
[30] Stevenson, R.: Nonconforming finite elements and the cascadic multi-grid method. Numer. Math. 91, 351-387 (2002) · Zbl 0996.65139 · doi:10.1007/s002110100344
[31] Zhou, S.Z., Hu, H.X.: On the convergence of a cascadic multigrid method for semilinear elliptic problem. Appl. Math. Comput. 159, 407417 (2004) · Zbl 1066.65149
[32] Du, Q., Ming, P.B.: Cascadic multigrid methods for parabolic problems. Sci. China Ser. A Math. 51, 1415-1439 (2008) · Zbl 1178.65114 · doi:10.1007/s11425-008-0112-1
[33] Xu, X.J., Chen, W.B.: Standard and economical cascadic multigrid methods for the mortar finite element methods. Numer. Math. Theory Methods Appl. 2, 180-201 (2009) · Zbl 1212.65501
[34] Yu, H.X., Zeng, J.P.: A cascadic multigrid method for a kind of semilinear elliptic problem. Numer. Algorithms 58, 143-162 (2011) · Zbl 1227.65124 · doi:10.1007/s11075-011-9450-0
[35] Shi, Z.C., Xu, X.J., Huang, Y.Q.: Economical cascadic multigrid method (ECMG). Sci. China Ser. A Math. 50(12), 1765-1780 (2007) · Zbl 1153.65046 · doi:10.1007/s11425-007-0127-z
[36] Chen, C.M., Hu, H.L., Xie, Z.Q., et al.: Analysis of extrapolation cascadic multigrid method (EXCMG). Sci. China Ser. A-Math. 51, 1349-1360 (2008) · Zbl 1157.65062 · doi:10.1007/s11425-008-0119-7
[37] Chen, C.M., Shi, Z.C., Hu, H.L.: On extrapolation cascadic multigrid method. J. Comput. Math. 29, 684-697 (2011) · Zbl 1265.65194 · doi:10.4208/jcm.1110-m11si05
[38] Hu, H.L., Chen, C.M., Pan, K.J.: Asymptotic expansions of finite element solutions to Robin problems in \[H^3\] H3 and their application in extrapolation cascadic multigrid method. Sci. China Math. 57, 687-698 (2014) · Zbl 1312.65192 · doi:10.1007/s11425-013-4669-y
[39] Hu, H.L., Chen, C.M., Pan, K.J.: Time-extrapolation algorithm (TEA) for linear parabolic problems. J. Comput. Math. 32, 183-194 (2014) · Zbl 1313.65217 · doi:10.4208/jcm.1310-FE1
[40] Pan, K.J., Tang, J.T., Hu, H.L., et al.: Extrapolation cascadic multigrid method for 2.5D direct current resistivity modeling (in Chinese), Chinese. J. Geophys. 55, 2769-2778 (2012)
[41] Pan, K.J., Tang, J.T.: 2.5-D and 3-D DC resistivity modelling using an extrapolation cascadic multigrid method. Geophys. J. Int. 197, 1459-1470 (2014) · doi:10.1093/gji/ggu094
[42] Newman, G.A.: A Review of high-performance computational strategies for modeling and imaging of electromagnetic induction data. Surv. Geophys. 35, 85-100 (2014) · doi:10.1007/s10712-013-9260-0
[43] Berikelashuili, G., Gupta, M.M., Mirianashvili, M.: Convergence of fourth-order compact difference schemes for three-dimensional convection-diffusion equations. SIAM J. Numer. Anal. 45, 443-455 (2007) · Zbl 1140.65074 · doi:10.1137/050622833
[44] Pan, K.J., He, D.D., Hu, H.L.: A new extrapolation cascadic multigrid method for 3D elliptic boundary value problems on rectangular domains. arXiv preprint arXiv:1506.02983 (2015) · Zbl 0943.65018
[45] Marchuk, G.I., Shaidurov, V.V.: Difference Methods and Their Extrapolations. Springer, New York (1983) · Zbl 0511.65076 · doi:10.1007/978-1-4613-8224-9
[46] Neittaanmaki, P., Lin, Q.: Acceleration of the convergence in finite-difference method by predictor corrector and splitting extrapolation methods. J. Comput. Math. 5, 181-190 (1987) · Zbl 0626.65092
[47] Fößmeier, R.: On Richardson extrapolation for finite difference methods on regular grids. Numer. Math. 55, 451-462 (1989) · Zbl 0661.65092 · doi:10.1007/BF01396048
[48] Han, G.Q.: Spline finite difference methods and their extrapolation for singular two-point boundary value problems. J. Comput. Math. 11, 289-296 (1993) · Zbl 0806.65080
[49] Sun, H., Zhang, J.: A high order finite difference discretization strategy based on extrapolation for convection diffusion equations. Numer. Methods Part. Differ. Equ. 20, 18-32 (2004) · Zbl 1038.65108 · doi:10.1002/num.10075
[50] Rahul, K., Bhattacharyya, S.N.: One-sided finite-difference approximations suitable for use with Richardson extrapolation. J. Comput. Phys. 219, 13-20 (2006) · Zbl 1106.65094 · doi:10.1016/j.jcp.2006.05.035
[51] Munyakazi, J.B., Patidar, K.C.: On Richardson extrapolation for fitted operator finite difference methods. Appl. Math. Comput. 201, 465-480 (2008) · Zbl 1155.65362
[52] Tam, C.K.W., Kurbatskii, K.A.: A wavenumber based extrapolation and interpolation method for use in conjunction with high-order finite difference schemes. J. Comput. Phys. 157, 588-617 (2000) · Zbl 0943.65018 · doi:10.1006/jcph.1999.6393
[53] Ma, Y., Ge, Y.: A high order finite difference method with Richardson extrapolation for 3D convection diffusion equation. Appl. Math. Comput. 215, 3408-3417 (2010) · Zbl 1181.65131
[54] Marchi, C.H., Novak, L.A., Santiago, C.D., et al.: Highly accurate numerical solutions with repeated Richardson extrapolation for 2D Laplace equation. Appl. Math. Model. 37, 7386-7397 (2013) · Zbl 1426.65154 · doi:10.1016/j.apm.2013.02.043
[55] Collatz, L.: The Numerical Treatment of Differential Equations. Springer, New York (1966) · Zbl 0221.65088
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.