Computational complexity study on Krylov integration factor WENO method for high spatial dimension convection-diffusion problems. (English) Zbl 1381.65067
Summary: Integration factor (IF) methods are a class of efficient time discretization methods for solving stiff problems via evaluation of an exponential function of the corresponding matrix for the stiff operator. The computational challenge in applying the methods for partial differential equations (PDEs) on high spatial dimensions (multidimensional PDEs) is how to deal with the matrix exponential for very large matrices. Compact integration factor methods developed in [Q. Nie et al., J. Comput. Phys. 227, No. 10, 5238–5255 (2008; Zbl 1142.65072)] provide an approach to reduce the cost prohibitive large matrix exponentials for linear diffusion operators with constant diffusion coefficients in high spatial dimensions to a series of much smaller one dimensional computations. This approach is further developed in [D. Wang et al., J. Comput. Phys. 258, 585–600 (2014; Zbl 1349.65401)] to deal with more complicated high dimensional reaction-diffusion equations with cross-derivatives in diffusion operators. Another approach is to use Krylov subspace approximations to efficiently calculate large matrix exponentials. In [S. Chen and Y.-T. Zhang, J. Comput. Phys. 230, No. 11, 4336–4352 (2011; Zbl 1416.65341)], Krylov subspace approximation is directly applied to the implicit integration factor (IIF) methods for solving high dimensional reaction-diffusion problems. Recently the method is combined with weighted essentially non-oscillatory (WENO) schemes in [T. Jiang and Y.-T. Zhang, J. Comput. Phys. 253, 368–388 (2013; Zbl 1349.65305)] to efficiently solve semilinear and fully nonlinear convection-reaction-diffusion equations. A natural question that arises is how these two approaches may perform differently for various types of problems. In this paper, we study the computational power of Krylov IF-WENO methods for solving high spatial dimension convection-diffusion PDE problems (up to four spatial dimensions). Systematical numerical comparison and complexity analysis are carried out for the computational efficiency of the two different approaches. We show that although the Krylov IF-WENO methods have linear computational complexity, both the compact IF method and the Krylov IF method have their own advantages for different type of problems. This study provides certain guidance for using IF-WENO methods to solve general high spatial dimension convection-diffusion problems.
MSC:
| 65M06 | Finite difference methods for initial value and initial-boundary value problems involving PDEs |
| 35K55 | Nonlinear parabolic equations |
| 65Y20 | Complexity and performance of numerical algorithms |
Keywords:
implicit integration factor methods; weighted essentially non-oscillatory schemes; Krylov subspace approximation; high spatial dimensions; nonlinear convection-diffusion equations; numerical example; computational complexityReferences:
| [1] | Ascher, U., Ruuth, S., Wetton, B.: Implicit-explicit methods for time-dependent PDE’s. SIAM J. Numer. Anal. 32, 797-823 (1995) · Zbl 0841.65081 · doi:10.1137/0732037 |
| [2] | Ashe, H.L., Levine, M.: Local inhibition and long-range enhancement of Dpp signal transduction by Sog. Nature 398, 427-431 (1999) · doi:10.1038/18892 |
| [3] | Beylkin, G., Keiser, J.M., Vozovoi, L.: A new class of time discretization schemes for the solution of nonlinear PDEs. J. Comput. Phys. 147, 362-387 (1998) · Zbl 0924.65089 · doi:10.1006/jcph.1998.6093 |
| [4] | Bourlioux, A., Layton, A.T., Minion, M.L.: High-order multi-implicit spectral deferred correction methods for problems of reactive flow. J. Comput. Phys. 189, 651-675 (2003) · Zbl 1061.76053 · doi:10.1016/S0021-9991(03)00251-1 |
| [5] | Chen, S., Zhang, Y.-T.: Krylov implicit integration factor methods for spatial discretization on high dimensional unstructured meshes: application to discontinuous Galerkin methods. J. Comput. Phys. 230, 4336-4352 (2011) · Zbl 1416.65341 · doi:10.1016/j.jcp.2011.01.010 |
| [6] | Christlieb, A., Ong, B., Qiu, J.-M.: Integral deferred correction methods constructed with high order Runge-Kutta integrators. Math. Comput. 79, 761-783 (2010) · Zbl 1209.65073 · doi:10.1090/S0025-5718-09-02276-5 |
| [7] | Cox, S.M., Matthews, P.C.: Exponential time differencing for stiff systems. J. Comput. Phys. 176, 430-455 (2002) · Zbl 1005.65069 · doi:10.1006/jcph.2002.6995 |
| [8] | Dutt, A., Greengard, L., Rokhlin, V.: Spectral deferred correction methods for ordinary differential equations. BIT 40(2), 241-266 (2000) · Zbl 0959.65084 · doi:10.1023/A:1022338906936 |
| [9] | Fokker, A.D.: Die mittlere energie rotierender elektrischer dipole im strahlungsfeld. Ann. Phys. 348, 810-820 (1914) · doi:10.1002/andp.19143480507 |
| [10] | Gallopoulos, E., Saad, Y.: Efficient solution of parabolic equations by Krylov approximation methods. SIAM J. Sci. Stat. Comput. 13(5), 1236-1264 (1992) · Zbl 0757.65101 · doi:10.1137/0913071 |
| [11] | Gottlieb, S., Shu, C.-W.: Total variation diminishing Runge-Kutta schemes. Math. Comput. 67, 73-85 (1998) · Zbl 0897.65058 · doi:10.1090/S0025-5718-98-00913-2 |
| [12] | Gottlieb, S., Shu, C.-W., Tadmor, E.: Strong stability preserving high order time discretization methods. SIAM Rev. 43, 89-112 (2001) · Zbl 0967.65098 · doi:10.1137/S003614450036757X |
| [13] | Harten, A., Engquist, B., Osher, S., Chakravarthy, S.: Uniformly high order essentially non-oscillatory schemes, III. J. Comput. Phys. 71, 231-303 (1987) · Zbl 0652.65067 · doi:10.1016/0021-9991(87)90031-3 |
| [14] | Higham, N.J.: The scaling and squaring method for the matrix exponential revisited. SIAM Rev. 51(4), 747-764 (2009) · Zbl 1178.65040 · doi:10.1137/090768539 |
| [15] | Hu, C., Shu, C.-W.: Weighted essentially non-oscillatory schemes on triangular meshes. J. Comput. Phys. 150, 97-127 (1999) · Zbl 0926.65090 · doi:10.1006/jcph.1998.6165 |
| [16] | Huang, J., Jia, J., Minion, M.: Arbitrary order Krylov deferred correction methods for differential algebraic equations. J. Comput. Phys. 221(2), 739-760 (2007) · Zbl 1110.65076 · doi:10.1016/j.jcp.2006.06.040 |
| [17] | Hochbruck, M., Lubich, C.: On Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 34, 1911-1925 (1997) · Zbl 0888.65032 · doi:10.1137/S0036142995280572 |
| [18] | Hundsdorfer, W., Verwer, J.: Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations. Springer, Berlin (2003) · Zbl 1030.65100 · doi:10.1007/978-3-662-09017-6 |
| [19] | Jiang, G.-S., Shu, C.-W.: Efficient implementation of weighted ENO schemes. J. Comput. Phys. 126, 202-228 (1996) · Zbl 0877.65065 · doi:10.1006/jcph.1996.0130 |
| [20] | Jiang, T., Zhang, Y.-T.: Krylov implicit integration factor WENO methods for semilinear and fully nonlinear advection-diffusion-reaction equations. J. Comput. Phys. 253, 368-388 (2013) · Zbl 1349.65305 · doi:10.1016/j.jcp.2013.07.015 |
| [21] | Jiang, T., Zhang, Y.-T.: Krylov single-step implicit integration factor WENO methods for advection-diffusion-reaction equations. J. Comput. Phys. 311, 22-44 (2016) · Zbl 1349.65306 · doi:10.1016/j.jcp.2016.01.021 |
| [22] | Ju, L., Zhang, J., Zhu, L., Du, Q.: Fast explicit integration factor methods for semilinear parabolic equations. J. Sci. Comput. 62, 431-455 (2015) · Zbl 1317.65172 · doi:10.1007/s10915-014-9862-9 |
| [23] | Kanevsky, A., Carpenter, M.H., Gottlieb, D., Hesthaven, J.S.: Application of implicit-explicit high order Runge-Kutta methods to discontinuous-Galerkin schemes. J. Comput. Phys. 225(2), 1753-1781 (2007) · Zbl 1123.65097 · doi:10.1016/j.jcp.2007.02.021 |
| [24] | Kassam, A.-K., Trefethen, L.N.: Fourth-order time stepping for stiff PDEs. SIAM J. Sci. Comput. 26(4), 1214-1233 (2005) · Zbl 1077.65105 · doi:10.1137/S1064827502410633 |
| [25] | Kennedy, C.A., Carpenter, M.H.: Additive Runge-Kutta schemes for convection-diffusion-reaction equations. Appl. Numer. Math. 44, 139-181 (2003) · Zbl 1013.65103 · doi:10.1016/S0168-9274(02)00138-1 |
| [26] | Layton, A.T., Minion, M.L.: Conservative multi-implicit spectral deferred correction methods for reacting gas dynamics. J. Comput. Phys. 194(2), 697-715 (2004) · Zbl 1100.76048 · doi:10.1016/j.jcp.2003.09.010 |
| [27] | Lander, A., Nie, Q., Wan, F., Zhang, Y.-T.: Localized ectopic expression of Dpp receptors in a Drosophila embryo. Stud. Appl. Math. 123, 175-214 (2009) · Zbl 1167.92003 · doi:10.1111/j.1467-9590.2009.00450.x |
| [28] | Liu, X.-D., Osher, S., Chan, T.: Weighted essentially non-oscillatory schemes. J. Comput. Phys. 115, 200-212 (1994) · Zbl 0811.65076 · doi:10.1006/jcph.1994.1187 |
| [29] | Liu, X.F., Nie, Q.: Compact integration factor methods for complex domains and adaptive mesh refinement. J. Comput. Phys. 229(16), 5692-5706 (2010) · Zbl 1194.65111 · doi:10.1016/j.jcp.2010.04.003 |
| [30] | Liu, Y., Zhang, Y.-T.: A robust reconstruction for unstructured WENO schemes. J. Sci. Comput. 54, 603-621 (2013) · Zbl 1263.65087 · doi:10.1007/s10915-012-9598-3 |
| [31] | Lu, D., Zhang, Y.-T.: Krylov integration factor method on sparse grids for high spatial dimension convection-diffusion equations. J. Sci. Comput. 69, 736-763 (2016) · Zbl 1370.65045 · doi:10.1007/s10915-016-0216-7 |
| [32] | Lu, J., Fang, J., Tan, S., Shu, C.-W., Zhang, M.: Inverse Lax-Wendroff procedure for numerical boundary conditions of convection-diffusion equations. J. Comput. Phys. 317, 276-300 (2016) · Zbl 1349.65319 · doi:10.1016/j.jcp.2016.04.059 |
| [33] | Maday, Y., Patera, A.T., Ronquist, E.M.: An operator-integration-factor splitting method for time-dependent problems: application to incompressible fluid flow. J. Sci. Comput. 5, 263-292 (1990) · Zbl 0724.76070 · doi:10.1007/BF01063118 |
| [34] | Minion, M.L.: Semi-implicit spectral deferred correction methods for ordinary differential equations. Commun. Math. Sci. 1(3), 471-500 (2003) · Zbl 1088.65556 · doi:10.4310/CMS.2003.v1.n3.a6 |
| [35] | Mizutani, C.M., Nie, Q., Wan, F., Zhang, Y.-T., Vilmos, P., Sousa-Neves, R., Bier, E., Marsh, L., Lander, A.: Formation of the BMP activity gradient in the Drosophila embryo. Dev. Cell 8, 915-924 (2005) · doi:10.1016/j.devcel.2005.04.009 |
| [36] | Moler, C., Van Loan, C.: Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Rev. 45, 3-49 (2003) · Zbl 1030.65029 · doi:10.1137/S00361445024180 |
| [37] | Nie, Q., Zhang, Y.-T., Zhao, R.: Efficient semi-implicit schemes for stiff systems. J. Comput. Phys. 214, 521-537 (2006) · Zbl 1089.65094 · doi:10.1016/j.jcp.2005.09.030 |
| [38] | Nie, Q., Wan, F., Zhang, Y.-T., Liu, X.-F.: Compact integration factor methods in high spatial dimensions. J. Comput. Phys. 227, 5238-5255 (2008) · Zbl 1142.65072 · doi:10.1016/j.jcp.2008.01.050 |
| [39] | Planck, M.: Sitzber. Preuss. Akad. Wiss., p. 324 (1917) · Zbl 0841.65081 |
| [40] | Risken, H.: The Fokker-Planck Equation: Methods of Solutions and Applications. Springer, Berlin (1996) · Zbl 0866.60071 · doi:10.1007/978-3-642-61544-3_4 |
| [41] | Shu, C.-W.: TVD time discretizations. SIAM J. Sci. Stat. Comput. 9, 1073-1084 (1988) · Zbl 0662.65081 · doi:10.1137/0909073 |
| [42] | Shu, C.-W., Osher, S.: Efficient implementation of essentially non-oscillatory shock-capturing schemes. J. Comput. Phys. 77, 439-471 (1988) · Zbl 0653.65072 · doi:10.1016/0021-9991(88)90177-5 |
| [43] | Shu, C.-W.: Essentially non-oscillatory and weighted essentially non-oscillatory schemes for hyperbolic conservation laws. In: Cockburn, B., Johnson, C., Shu, C.-W., Tadmor, E., Quarteroni, A. (eds.) Advanced Numerical Approximation of Nonlinear Hyperbolic Equations. Lecture Notes in Mathematics, vol. 1697. Springer (1998) · Zbl 0927.65111 |
| [44] | Sjoberg, P., Lotstedt, P., Elf, J.: Fokker-Planck approximation of the master equation in molecular biology. Comput. Vis. Sci. 12, 37-50 (2009) · Zbl 1522.92026 · doi:10.1007/s00791-006-0045-6 |
| [45] | Strang, G.: On the construction and comparison of difference schemes. SIAM J. Numer. Anal 8(3), 506-517 (1968) · Zbl 0184.38503 · doi:10.1137/0705041 |
| [46] | Ta, C., Wang, D., Nie, Q.: An integration factor method for stochastic and stiff reaction-diffusion systems. J. Comput. Phys. v295, 505-522 (2015) · Zbl 1349.65540 · doi:10.1016/j.jcp.2015.04.028 |
| [47] | Trefethen, L.N., Bau, D.: Numerical Linear Algebra. SIAM, Philadelphia (1997) · Zbl 0874.65013 · doi:10.1137/1.9780898719574 |
| [48] | Verwer, J.G., Sommeijer, B.P., Hundsdorfer, W.: RKC time-stepping for advection-diffusion-reaction problems. J. Comput. Phys. 201, 61-79 (2004) · Zbl 1059.65085 · doi:10.1016/j.jcp.2004.05.002 |
| [49] | Wang, D., Zhang, L., Nie, Q.: Array-representation integration factor method for high-dimensional systems. J. Comput. Phys. 258, 585-600 (2014) · Zbl 1349.65401 · doi:10.1016/j.jcp.2013.11.002 |
| [50] | Wang, D., Chen, W., Nie, Q.: Semi-implicit integration factor methods on sparse grids for high-dimensional systems, J. Comput. Phys. v292, 43-55 (2015) · Zbl 1349.65340 · doi:10.1016/j.jcp.2015.03.033 |
| [51] | Zhang, Y.-T., Shu, C.-W.: High order WENO schemes for Hamilton-Jacobi equations on triangular meshes. SIAM J. Sci. Comput. 24, 1005-1030 (2003) · Zbl 1034.65051 · doi:10.1137/S1064827501396798 |
| [52] | Zhang, Y.-T., Shu, C.-W.: Third order WENO scheme on three dimensional tetrahedral meshes. Commun. Comput. Phys. 5, 836-848 (2009) · Zbl 1364.65177 |
| [53] | Zhong, X.: Additive semi-implicit Runge-Kutta methods for computing high-speed nonequilibrium reactive flows. J. Comput. Phys. 128, 19-31 (1996) · Zbl 0861.76057 · doi:10.1006/jcph.1996.0193 |
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.
