Stable, globally non-iterative, non-overlapping domain decomposition parallel solvers for parabolic problems

ABSTRACT

In this paper, we report a class of stabilized explicit-implicit domain decomposition (SEIDD) methods for the parallel solution of parabolic problems, based on the explicit-implicit domain decomposition (EIDD) methods. EIDD methods are globally non-iterative, non-overlapping domain decomposition methods which, when compared with Schwarz alternating algorithm based parabolic solvers, are computationally and communicationally efficient for each simulation time step but suffer from time step size restrictions due to conditional stability or conditional consistency. By adding a stabilization step to the EIDD methods, the SEIDD methods are freed from time step size restrictions while retaining EIDD's computational and communicational efficiency for each time step, rendering themselves excellent candidates for large-scale parallel simulations. Three algorithms of the SEIDD type are implemented, which are experimentally tested to show excellent stability, computation and communication efficiencies, and high parallel speedup and scalability.

REFERENCES

• 1: Kelly Black, Polynomial collocation using a domain decomposition solution to parabolic PDE's via the penalty method and explicit/implicit time marching, Journal of Scientific Computing, v.7 n.4, p.313-338, Dec. 1992 [doi>10.1007/BF01108035]
• 2: X.-C. Cai,Additive Schwarz algorithms for parabolic convection-diffusion equations, Numer. Math., 60 (1991), 41-61.
• 3: Xiao-Chuan Cai, Multiplicative Schwarz methods for parabolic problems, SIAM Journal on Scientific Computing, v.15 n.3, p.587-603, May 1994 [doi>10.1137/0915039]
• 4: X.-C. Cai, W. D. Gropp and D. E. Keyes,A comparison of some domain decomposition algorithms for nonsymmetric elliptic problems, J. Numer. Lin. Alg. Appl., 1993.
• 5: T. F. Chan and T. Mathew,Domain decomposition algorithms, Acta Numerica, 1994, 61-143.
• 6: Clint N. Dawson , Todd F. Dupont, Explicit/implicit, conservative domain decomposition procedures for parabolic problems based on block-centered finite differences, SIAM Journal on Numerical Analysis, v.31 n.4, p.1045-1061, Aug. 1994 [doi>10.1137/0731055]
• 7: C. Dawson, Q. Du, and T. Dupont,A finite difference domain decomposition algorithm for numerical solution of the heat equation, Math. Comp. 57 (1991), no. 195, 63-71.
• 8: J. Douglas and J. Gunn,A general formulation of alternating direction method: Part I. Parabolic and hyperbolic problems, Numer. Math., 6 (1964), 428-453.
• 9: M. Dryja,Substructuring methods for parabolic problems. Fourth International Symposium on Domain Decomposition Methods for Partial Differential Equations (Moscow, 1990), 264-271, SIAM, Philadelphia, PA, 1991.
• 10: M. Dryja and O. B. Widlund,An additive variant of the Schwarz alternating method for the case of many subregions, Tech. Rep. 339, Courant Inst., New York Univ., 1987.
• 11: William D. Gropp , David E. Keyes, Domain decomposition on parallel computers, IMPACT of Computing in Science and Engineering, v.1 n.4, p.420-439, Dec. 1989
• 12: D. E. Keyes,Domain decomposition: a bridge between nature and parallel computers, NASA ICASE Technical Report No. 92-44, NASA Langley Research Center Hampton, VA 23681-0001, 1992.
• 13: David E. Keyes , William D. Gropp, A comparison of domain decomposition techniques for elliptic partial differential equations and their parallel implementation, SIAM Journal on Scientific and Statistical Computing, v.8 n.2, p.166-202, March 1, 1987 [doi>10.1137/0908020]
• 14: Y. A. Kuznetsov,New algorithms for approximate realization of implicit difference schemes, Sov. J. Numer. Ana.Math. Modell. 3 (1988), 99-114.
• 15: Yu. M. Layevskii, A domain partitioning algorithm without subdomain overlap for solving parabolic equations, Computational Mathematics and Mathematical Physics, v.32 n.11, p.1569-1580, Nov. 1992
• 16: Yu. M. Laevsky,Explicit-implicit domain decomposition method for solving parabolic equations. (Russian) Computing methods and technology for solving problems in mathematical physics (Russian), 30-46, Ross. Akad. Nauk Sibirsk. Otdel., Vychisl. Tsentr, Novosibirsk, 1993.
• 17: Y. M. Laevsky and S. V. Gololobov,Explicit-implicit domain decomposition methods for the solution of parabolic equations. (Russian) Sibirsk. Mat. Zh. 36 (1995), no. 3, 590-601, ii; translation in Siberian Math. J. 36 (1995), no. 3, 506-516.
• 18: Yu. M. Laevsky and O. V. Rudenko,Splitting methods for parabolic problems in non-rectangular domains. Appl. Math. Lett. 8 (1995), no. 6, 9-14.
• 19: T. P. Mathew , P. L. Polyakov , G. Russo , J. Wang, Domain Decomposition Operator Splittings for the Solution of Parabolic Equations, SIAM Journal on Scientific Computing, v.19 n.3, p.912-932, May 1998 [doi>10.1137/S1064827595288206]
• 20: Barry F. Smith , Petter E. Bjørstad , William D. Gropp, Domain decomposition: parallel multilevel methods for elliptic partial differential equations, Cambridge University Press, New York, NY, 1996
• 21: Y. Zhuang,Classically Unstable Approximations for Linear Evolution Equations and Applications, Ph.D. dissertation, Department of Mathematics, Louisiana State University Baton Rouge, August 2000.
• 22: Yu Zhuang , Donald H. Kraft , Xian-He Sun, A class of stable, globally noniterative, nonoverlapping domain decomposition algorithms for the simulation of parabolic evolutionary systems, 2000

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Domain decomposition methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Parallel

General Terms:
Algorithms, Design, Performance