×

A stabilized explicit Lagrange multiplier based domain decomposition method for parabolic problems. (English) Zbl 1142.65076

Summary: A fully explicit, stabilized domain decomposition method for solving moderately stiff parabolic partial differential equations is presented. Writing the semi-discretized equations as a differential-algebraic equation (DAE) system where the interface continuity constraints between subdomains are enforced by Lagrange multipliers, the method uses the Runge-Kutta-Chebyshev projection scheme to integrate the DAE explicitly and to enforce the constraints by a projection. With mass lumping techniques and node-to-node matching grids, the method is fully explicit without solving any linear system. A stability analysis is presented to show the extended stability property of the method. The method is straightforward to implement and to parallelize. Numerical results demonstrate that it has excellent performance.

MSC:

65M55 Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs
65M20 Method of lines for initial value and initial-boundary value problems involving PDEs
65L80 Numerical methods for differential-algebraic equations
35K55 Nonlinear parabolic equations
65M12 Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs
65Y05 Parallel numerical computation

Software:

RKC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Schwarz, H. A., Gesammelte Mathematicsche Abhandlungen (1890), Springer-Verlag, vol. 2, p. 133
[2] M. Dryja, An additive Schwarz algorithm for two- and three-dimensional finite element elliptic problems, in: T.F. Chan, R. Glowinski, J. Périaux, O. Widlund (Eds.), Proceedings of the Second International Symposium on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, PA, 1989, p. 168.; M. Dryja, An additive Schwarz algorithm for two- and three-dimensional finite element elliptic problems, in: T.F. Chan, R. Glowinski, J. Périaux, O. Widlund (Eds.), Proceedings of the Second International Symposium on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, PA, 1989, p. 168. · Zbl 0681.65075
[3] P.E. Bjørstad, M. Skogen, Domain decomposition algorithms of Schwarz type, designed for massively parallel computers, in: D.E. Keyes, T.F. Chan, G.A. Meurant, J.S. Scroggs, R.G. Voigt (Eds.), Proceedings of the Fifth International Symposium on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, PA, 1992, p. 362.; P.E. Bjørstad, M. Skogen, Domain decomposition algorithms of Schwarz type, designed for massively parallel computers, in: D.E. Keyes, T.F. Chan, G.A. Meurant, J.S. Scroggs, R.G. Voigt (Eds.), Proceedings of the Fifth International Symposium on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, PA, 1992, p. 362. · Zbl 0770.65078
[4] Cai, X. C., Additive Schwarz algorithms for parabolic convection-diffusion equations, Numer. Math., 60, 1, 41 (1991) · Zbl 0737.65078
[5] Cai, X. C.; Widlund, O., Multiplicative Schwarz algorithms for nonsymmetric and indefinite problems, SIAM J. Numer. Anal., 30, 936 (1993) · Zbl 0787.65016
[6] Cai, X. C., Multiplicative Schwarz algorithms for parabolic problems, SIAM J. Sci. Comput., 15, 587 (1994) · Zbl 0803.65096
[7] Zhang, X., Multilevel Schwarz methods, Numer. Math., 63, 4, 521 (1992) · Zbl 0796.65129
[8] Mathew, T. P., Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems, part I: Algorithms and numerical results, Numer. Math., 65, 4, 445 (1993) · Zbl 0801.65106
[9] Bjørstad, P. E.; Widlund, O. B., Iterative methods for the solution of elliptic problems on regions partitioned into substructures, SIAM J. Numer. Anal., 10, 5, 1053 (1986)
[10] Bramble, J. H.; Pasciak, J. E.; Schatz, A. H., An iterative method for elliptic problems on regions partitioned into substructures, Math. Comp., 46, 173, 361 (1986) · Zbl 0595.65111
[11] Funaro, D.; Quarteroni, A.; Zanolli, P., An iterative procedure with interface relaxation for domain decomposition methods, SIAM J. Numer. Anal., 10, 5, 1053 (1988)
[12] Toselli, A.; Widlund, O., Domain Decomposition Methods - Algorithms and Theory (2005), Springer · Zbl 1069.65138
[13] J.F. Bourgat, R. Glowinski, P.L. Tallec, M. Vidrascu, Variational formulation and algorithm for trace operator in domain decomposition calculations, in: T.F. Chan, R. Glowinski, J. Périaux, O. Widlund (Eds.), Proceedings of the Second International Symposium on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, PA, 1989.; J.F. Bourgat, R. Glowinski, P.L. Tallec, M. Vidrascu, Variational formulation and algorithm for trace operator in domain decomposition calculations, in: T.F. Chan, R. Glowinski, J. Périaux, O. Widlund (Eds.), Proceedings of the Second International Symposium on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, PA, 1989. · Zbl 0684.65094
[14] Y.D. Roeck, P.L. Tallec, Analysis and test of a local domain decomposition preconditioner, in: R. Glowinski, Y.A. Kuznetsov, G.A. Meurant, J. Périaux, O. Widlund (Eds.), Proceedings of the Fourth International Symposium on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, PA, 1991.; Y.D. Roeck, P.L. Tallec, Analysis and test of a local domain decomposition preconditioner, in: R. Glowinski, Y.A. Kuznetsov, G.A. Meurant, J. Périaux, O. Widlund (Eds.), Proceedings of the Fourth International Symposium on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, PA, 1991. · Zbl 0770.65082
[15] Tallec, P. L.; Roeck, Y. D.; Vidrascu, M., Domain decomposition methods for large linearly elliptic three-dimensional problems, J. Comput. Appl. Math., 34, 1, 93 (1991) · Zbl 0719.65083
[16] Xu, J.; Zou, J., Some nonoverlapping domain decomposition methods, SIAM Rev., 40, 4, 857 (1998) · Zbl 0913.65115
[17] Farhat, C.; Roux, F. X., A method of finite element tearing and interconnecting and its parallel solution algorithm, Int. J. Numer. Meth. Eng., 32, 1205 (1991) · Zbl 0758.65075
[18] J. Mandel, R. Tezaur, C. Farhat, An optimal Lagrange multiplier based domain decomposition method for plate bending problems, Technical Report UCD-CCM-061, Center for Computational Mathematics, University of Colorado at Denver, 1995.; J. Mandel, R. Tezaur, C. Farhat, An optimal Lagrange multiplier based domain decomposition method for plate bending problems, Technical Report UCD-CCM-061, Center for Computational Mathematics, University of Colorado at Denver, 1995.
[19] Lesoinne, M.; Pierson, K., An efficient FETI implementation on distributed shared memory machines with independent numbers of subdomains and processors, Contemp. Math., 218, 318 (1998) · Zbl 0910.65088
[20] A. Klawonn, O.B. Widlund, A domain decomposition method with Lagrange multipliers for linear elasticity, in: C.H. Lai, P.E. Bjørstad, M. Cross, O.B. Widlund (Eds.), Proceedings of the Eleventh International Conference on Domain Decomposition Methods, Greenwich, UK, 1998.; A. Klawonn, O.B. Widlund, A domain decomposition method with Lagrange multipliers for linear elasticity, in: C.H. Lai, P.E. Bjørstad, M. Cross, O.B. Widlund (Eds.), Proceedings of the Eleventh International Conference on Domain Decomposition Methods, Greenwich, UK, 1998. · Zbl 0980.65145
[21] R. Tezaur, Analysis of Lagrange Multiplier Based Domain Decomposition. PhD thesis, University of Colorado at Denver, 1998.; R. Tezaur, Analysis of Lagrange Multiplier Based Domain Decomposition. PhD thesis, University of Colorado at Denver, 1998.
[22] G. Lube, L. Müller, F.-C. Otto, A non-overlapping DDM of Robin-Robin type for parabolic problems, in: C.H. Lai, P.E. Bjørstad, M. Cross, O.B. Widlund (Eds.), Proceedings of the Eleventh International Conference on Domain Decomposition Methods, Greenwich, UK, 1998.; G. Lube, L. Müller, F.-C. Otto, A non-overlapping DDM of Robin-Robin type for parabolic problems, in: C.H. Lai, P.E. Bjørstad, M. Cross, O.B. Widlund (Eds.), Proceedings of the Eleventh International Conference on Domain Decomposition Methods, Greenwich, UK, 1998.
[23] Israeli, M.; Vozovoi, L.; Averbuch, A., Parallelizing implicit algorithms for time dependent problems by parabolic domain decomposition, J. Sci. Comput., 8, 151 (1993) · Zbl 0783.76073
[24] M. Dryja, X. Tu, A domain decomposition discretization of parabolic problems, Technical Report 860, Courant Institute of Mathematical Sciences, New York University, 2005.; M. Dryja, X. Tu, A domain decomposition discretization of parabolic problems, Technical Report 860, Courant Institute of Mathematical Sciences, New York University, 2005. · Zbl 1130.65097
[25] A.A. Samarskii, P.N. Vabishchevich, Domain decomposition methods for parabolic problems, in: C.H. Lai, P.E. Bjørstad, M. Cross, O.B. Widlund (Eds.), Proceedings of the Eleventh International Conference on Domain Decomposition Methods, Greenwich, UK, 1998.; A.A. Samarskii, P.N. Vabishchevich, Domain decomposition methods for parabolic problems, in: C.H. Lai, P.E. Bjørstad, M. Cross, O.B. Widlund (Eds.), Proceedings of the Eleventh International Conference on Domain Decomposition Methods, Greenwich, UK, 1998. · Zbl 0944.65098
[26] Zhuang, Y.; Sun, X., Stabilized explicit-implicit domain decomposition methods for the numerical solution of parabolic equations, SIAM J. Sci. Comput., 24, 335 (2002) · Zbl 1013.65106
[27] Shi, H.; Liao, H., Unconditional stability of corrected explicit-implicit domain decomposition algorithms for parallel approximation of heat equations, SIAM J. Numer. Anal., 44, 4, 1584 (2006) · Zbl 1125.65087
[28] Dawson, C. N.; Du, Q.; Dupont, T. F., A finite difference domain decomposition algorithm for numerical solution of the heat equation, Math. Comput., 57, 195, 63 (1991) · Zbl 0732.65091
[29] Dawson, C. N.; Dupont, T. F., Explicit/implicit, conservative domain decomposition procedures for parabolic problems based on block-centered finite differences, SIAM J. Numer. Anal., 31, 1045 (1994) · Zbl 0806.65093
[30] J. Zhu, H. Qian, On an efficient parallel algorithm for solving time dependent partial differential equations, in: Proceedings of the PDPTA’98 International Conference, 1998, p. 394.; J. Zhu, H. Qian, On an efficient parallel algorithm for solving time dependent partial differential equations, in: Proceedings of the PDPTA’98 International Conference, 1998, p. 394.
[31] Jun, Y.; Mai, T.-Z., IPIC Domain decomposition algorithm for parabolic problems, Appl. Math. Comput., 177, 1, 352 (2006) · Zbl 1094.65097
[32] van der Houwen, P. J.; Sommeijer, B. P., On the internal stability of explicit, \(m\)-stage Runge-Kutta methods for large \(m\)-values, Z. Angew. Math. Mech., 60, 479 (1980) · Zbl 0455.65052
[33] Verwer, J. G., Explicit Runge-Kutta methods for parabolic differential equations, Appl. Numer. Math., 22, 359 (1996) · Zbl 0868.65064
[34] Sommeijer, B. P.; Shampine, L. F.; Verwer, J. G., RKC: an explicit solver for parabolic PDEs, J. Comp. Appl. Math., 88, 315 (1997) · Zbl 0910.65067
[35] Zheng, Z.; Petzold, L. R., Runge-Kutta-Chebyshev projection method, J. Comp. Phys., 219, 976 (2006) · Zbl 1103.76048
[36] Verwer, J. G.; Sommeijer, B. P.; Hundsdorfer, W., RKC time-stepping for advection-diffusion-reaction problems, J. Comp. Phys., 201, 61 (2004) · Zbl 1059.65085
[37] Verwer, J. G.; Sommeijer, B. P., An implicit-explicit Runge-Kutta-Chebyshev scheme for diffusion-reaction equations, SIAM J. Sci. Comput., 25, 1824 (2004) · Zbl 1061.65090
[38] Bermejo, R.; El Amrani, M., A finite element semi-Lagrangian explicit Runge-Kutta-Chebyshev method for convection dominated reaction-diffusion problems, J. Comput. Appl. Math., 154, 27 (2003) · Zbl 1029.65114
[39] Wu, S. R., Lumped mass matrix in explicit finite element method for transient dynamics of elasticity, Comput. Meth. Appl. Mech. Eng., 195, 5983 (2006) · Zbl 1122.74049
[40] Ben Belgacem, F., The mortar finite element method with Lagrange multipliers, Numer. Math., 84, 73 (1999) · Zbl 0944.65114
[41] Chorin, A. J., Numerical solution of the Navier-Stokes equations, Math. Comp., 22, 104, 745 (1968) · Zbl 0198.50103
[42] Témam, R., Sur l’approximation de la solution des équations de Navier-Stokes par la méthode des pas fractionnaires (II), Arch. Rat. Mech. Anal., 33, 377 (1969) · Zbl 0207.16904
[43] Botella, O., A high-order mass-lumping procedure for B-spline collocation method with application to incompressible flow simulations, Int. J. Numer. Meth. Fluids, 41, 1295 (2003) · Zbl 1047.76096
[44] Ascher, U. M.; Petzold, L. R., Computer methods for ordinary differential equations and differential-algebraic equations, Soc. Ind. Appl. Math. (1998) · Zbl 0908.65055
[45] Z. Zheng, L.R. Petzold, A framework for the analysis of second order projection methods, submitted for publication.; Z. Zheng, L.R. Petzold, A framework for the analysis of second order projection methods, submitted for publication.
[46] Hughes, T. J.R., The Finite Element Method: Linear Static and Dynamic Finite Element Analysis (2000), Dover Publications · Zbl 1191.74002
[47] Ascher, U. M.; Petzold, L. R., Stability of computational methods for constrained dynamics systems, SIAM J. Sci. Statist. Comput., 14, 95 (1993) · Zbl 0773.65044
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.