Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Discrete analysis of domain decomposition approaches for mesh generation via the equidistribution principle

Authors: Ronald D. Haynes and Felix Kwok
Journal: Math. Comp. 86 (2017), 233-273
MSC (2010): Primary 65M55, 65N22, 65Y05, 65M50, 65N50
Published electronically: April 13, 2016
MathSciNet review: 3557799
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Moving mesh methods based on the equidistribution principle are powerful techniques for the space-time adaptive solution of evolution problems. Solving the resulting coupled system of equations, namely the original PDE and the mesh PDE, however, is challenging in parallel. Recently several Schwarz domain decomposition algorithms were proposed for this task and analyzed at the continuous level. However, after discretization, the resulting problems may not even be well posed, so the discrete algorithms require a different analysis, which is the subject of this paper. We prove that when the number of grid points is large enough, the classical parallel and alternating Schwarz methods converge to the unique monodomain solution. Thus, such methods can be used in place of Newton's method, which can suffer from convergence difficulties for challenging problems. The analysis for the nonlinear domain decomposition algorithms is based on $ M$-function theory and is valid for an arbitrary number of subdomains. An asymptotic convergence rate is provided and numerical experiments illustrate the results.

References [Enhancements On Off] (What's this?)

  • [1] Christoph Augustin and Olaf Steinbach, FETI methods for the simulation of biological tissues, Domain decomposition methods in science and engineering XX, Lect. Notes Comput. Sci. Eng., vol. 91, Springer, Heidelberg, 2013, pp. 503-510. MR 3243027,
  • [2] D. Bennequin, M. J. Gander, and L. Halpern, A homographic best approximation problem with application to optimized Schwarz waveform relaxation, Math. Comp. 78 (2009), no. 265, 185-223. MR 2448703 (2010g:65129),
  • [3] Heiko Berninger and Oliver Sander, Substructuring of a Signorini-type problem and Robin's method for the Richards equation in heterogeneous soil, Comput. Vis. Sci. 13 (2010), no. 5, 187-205. MR 2734836 (2011j:65127),
  • [4] Alexander Bihlo and Ronald D. Haynes, Parallel stochastic methods for PDE based grid generation, Comput. Math. Appl. 68 (2014), no. 8, 804-820. MR 3258448,
  • [5] Morton Bjorhus, On domain decomposition, subdomain iteration, and waveform relaxation, Ph.D. thesis, Norwegian Institute of Technology, The University of Trondheim, 1995.
  • [6] Igor P. Boglaev, Iterative algorithms of domain decomposition for the solution of a quasilinear elliptic problem, J. Comput. Appl. Math. 80 (1997), no. 2, 299-316. MR 1455249 (98d:65154),
  • [7] Hermann G. Burchard, Splines (with optimal knots) are better, Applicable Anal. 3 (1973/74), 309-319. MR 0399708 (53 #3551)
  • [8] Xiao-Chuan Cai, Additive Schwarz algorithms for parabolic convection-diffusion equations, Numer. Math. 60 (1991), no. 1, 41-61. MR 1131498 (93a:65127),
  • [9] Xiao-Chuan Cai, Multiplicative Schwarz methods for parabolic problems, Iterative methods in numerical linear algebra (Copper Mountain Resort, CO, 1992), SIAM J. Sci. Comput. 15 (1994), no. 3, 587-603. MR 1273154 (95c:65178),
  • [10] Xiao-Chuan Cai and Maksymilian Dryja, Domain decomposition methods for monotone nonlinear elliptic problems, Domain decomposition methods in scientific and engineering computing (University Park, PA, 1993) Contemp. Math., vol. 180, Amer. Math. Soc., Providence, RI, 1994, pp. 21-27. MR 1312374 (95j:65157),
  • [11] Xiao-Chuan Cai and David E. Keyes, Nonlinearly preconditioned inexact Newton algorithms, SIAM J. Sci. Comput. 24 (2002), no. 1, 183-200 (electronic). MR 1924420 (2003g:65067),
  • [12] Xiao-Chuan Cai, David E. Keyes, and Leszek Marcinkowski, Non-linear additive Schwarz preconditioners and application in computational fluid dynamics, LMS Workshop on Domain Decomposition Methods in Fluid Mechanics (London, 2001), Internat. J. Numer. Methods Fluids 40 (2002), no. 12, 1463-1470. MR 1957600 (2004a:65059),
  • [13] L. Collatz, Aufgaben monotoner Art, Arch. Math. 3 (1952), 366-376 (German). MR 0053603 (14,799h)
  • [14] Thu-Huyen Dao, Michael Ndjinga, and Frédéric Magoulès, A Schur complement method for compressible Navier-Stokes equations, Domain Decomposition Methods in Science and Engineering XX, Springer, 2013, pp. 543-550.
  • [15] Carl de Boor, Good approximation by splines with variable knots. II, Conference on the Numerical Solution of Differential Equations (Univ. Dundee, Dundee, 1973) Lecture Notes in Math., Vol. 363, Springer, Berlin, 1974, pp. 12-20. MR 0431606 (55 #4603)
  • [16] M. Dryja and W. Hackbusch, On the nonlinear domain decomposition method, BIT 37 (1997), no. 2, 296-311. MR 1450962 (97m:65100),
  • [17] Martin J. Gander, A waveform relaxation algorithm with overlapping splitting for reaction diffusion equations, Czech-US Workshop in Iterative Methods and Parallel Computing, Part 2 (Milovy, 1997), Numer. Linear Algebra Appl. 6 (1999), no. 2, 125-145. MR 1695405 (2000m:65110),$ \langle $125::AID-NLA152$ \rangle $3.0.CO;2-4
  • [18] Martin J. Gander, Optimized Schwarz methods, SIAM J. Numer. Anal. 44 (2006), no. 2, 699-731 (electronic). MR 2218966 (2007d:65121),
  • [19] Martin J. Gander and Laurence Halpern, Absorbing boundary conditions for the wave equation and parallel computing, Math. Comp. 74 (2005), no. 249, 153-176. MR 2085406 (2005h:65158),
  • [20] M. J. Gander and L. Halpern, Optimized Schwarz waveform relaxation methods for advection reaction diffusion problems, SIAM J. Numer. Anal. 45 (2007), no. 2, 666-697 (electronic). MR 2300292 (2008e:65291),
  • [21] Martin J. Gander, Laurence Halpern, and Frédéric Nataf, Optimal Schwarz waveform relaxation for the one dimensional wave equation, SIAM J. Numer. Anal. 41 (2003), no. 5, 1643-1681. MR 2035001 (2005h:65252),
  • [22] Martin J. Gander and Ronald D. Haynes, Domain decomposition approaches for mesh generation via the equidistribution principle, SIAM J. Numer. Anal. 50 (2012), no. 4, 2111-2135. MR 3022212,
  • [23] Martin J. Gander and Christian Rohde, Overlapping Schwarz waveform relaxation for convection-dominated nonlinear conservation laws, SIAM J. Sci. Comput. 27 (2005), no. 2, 415-439. MR 2202227 (2006i:35234),
  • [24] Martin J. Gander and Andrew M. Stuart, Space-time continuous analysis of waveform relaxation for the heat equation, SIAM J. Sci. Comput. 19 (1998), no. 6, 2014-2031. MR 1638096 (99h:65164),
  • [25] Eldar Giladi and Herbert B. Keller, Space-time domain decomposition for parabolic problems, Numer. Math. 93 (2002), no. 2, 279-313. MR 1941398 (2003j:65088),
  • [26] Florian Häberlein and Laurence Halpern, Optimized Schwarz waveform relaxation for nonlinear systems of parabolic type, Domain Decomposition Methods in Science and Engineering XXI, Springer, 2014.
  • [27] Florian Haeberlein, Laurence Halpern, and Anthony Michel, Newton-Schwarz optimised waveform relaxation Krylov accelerators for nonlinear reactive transport, Domain decomposition methods in science and engineering XX, Lect. Notes Comput. Sci. Eng., vol. 91, Springer, Heidelberg, 2013, pp. 387-394. MR 3243014,
  • [28] Ronald D. Haynes and Alexander J. M. Howse, Alternating Schwarz methods for partial differential equation-based mesh generation, Int. J. Comput. Math. 92 (2015), no. 2, 349-376. MR 3293531,
  • [29] Weizhang Huang, Practical aspects of formulation and solution of moving mesh partial differential equations, J. Comput. Phys. 171 (2001), no. 2, 753-775. MR 1848733 (2002e:65132),
  • [30] Weizhang Huang, Yuhe Ren, and Robert D. Russell, Moving mesh partial differential equations (MMPDES) based on the equidistribution principle, SIAM J. Numer. Anal. 31 (1994), no. 3, 709-730. MR 1275109 (94m:65149),
  • [31] Weizhang Huang and Robert D. Russell, A moving collocation method for solving time dependent partial differential equations, Workshop on the method of lines for time-dependent problems (Lexington, KY, 1995), Appl. Numer. Math. 20 (1996), no. 1-2, 101-116. MR 1385237,
  • [32] Weizhang Huang and Robert D. Russell, Adaptive moving mesh methods, Applied Mathematical Sciences, vol. 174, Springer, New York, 2011. MR 2722625 (2012a:65243)
  • [33] Wei Zhang Huang and David M. Sloan, A simple adaptive grid method in two dimensions, SIAM J. Sci. Comput. 15 (1994), no. 4, 776-797. MR 1278001 (95a:65155),
  • [34] Feng-Nan Hwang and Xiao-Chuan Cai, A parallel nonlinear additive Schwarz preconditioned inexact Newton algorithm for incompressible Navier-Stokes equations, J. Comput. Phys. 204 (2005), no. 2, 666-691. MR 2131857 (2005k:76096),
  • [35] Feng-Nan Hwang and Xiao-Chuan Cai, A class of parallel two-level nonlinear Schwarz preconditioned inexact Newton algorithms, Comput. Methods Appl. Mech. Engrg. 196 (2007), no. 8, 1603-1611. MR 2277041 (2007m:65125),
  • [36] P.-L. Lions, On the Schwarz alternating method. I, First International Symposium on Domain Decomposition Methods for Partial Differential Equations (Paris, 1987) SIAM, Philadelphia, PA, 1988, pp. 1-42. MR 972510 (90a:65248)
  • [37] S.-H. Lui, On linear monotone iteration and Schwarz methods for nonlinear elliptic PDEs, Numer. Math. 93 (2002), no. 1, 109-129. MR 1938324 (2003j:65128),
  • [38] Shiu-Hong Lui, On monotone and Schwarz alternating methods for nonlinear elliptic PDEs, M2AN Math. Model. Numer. Anal. 35 (2001), no. 1, 1-15. MR 1811978 (2001k:65187),
  • [39] Tarek P. A. Mathew, Domain decomposition methods for the numerical solution of partial differential equations, Lecture Notes in Computational Science and Engineering, vol. 61, Springer-Verlag, Berlin, 2008. MR 2445659 (2010b:65006)
  • [40] Gérard Meurant, A review on the inverse of symmetric tridiagonal and block tridiagonal matrices, SIAM J. Matrix Anal. Appl. 13 (1992), no. 3, 707-728. MR 1168018 (93d:15007),
  • [41] J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Classics in Applied Mathematics, vol. 30, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. Reprint of the 1970 original. MR 1744713 (2000j:65005)
  • [42] Serguei Ovtchinnikov and Xiao-Chuan Cai, One-level Newton-Krylov-Schwarz algorithm for unsteady non-linear radiation diffusion problem, Numer. Linear Algebra Appl. 11 (2004), no. 10, 867-881. MR 2104789 (2005g:65138),
  • [43] R. Peluso and T. Politi, Some improvements for two-sided bounds on the inverse of diagonally dominant tridiagonal matrices, Linear Algebra Appl. 330 (2001), no. 1-3, 1-14. MR 1826644 (2002c:15033),
  • [44] Werner C. Rheinboldt, On $ M$-functions and their application to nonlinear Gauss-Seidel iterations and to network flows, J. Math. Anal. Appl. 32 (1970), 274-307. MR 0269101 (42 #3997)
  • [45] Oliver Sander, Coupling geometrically exact Cosserat rods and linear elastic continua, Domain decomposition methods in science and engineering XX, Lect. Notes Comput. Sci. Eng., vol. 91, Springer, Heidelberg, 2013, pp. 443-450. MR 3243020,
  • [46] Xue-Cheng Tai and Magne Espedal, Rate of convergence of some space decomposition methods for linear and nonlinear problems, SIAM J. Numer. Anal. 35 (1998), no. 4, 1558-1570. MR 1626026 (99k:65101),
  • [47] Andrea Toselli and Olof Widlund, Domain decomposition methods--algorithms and theory, Springer Series in Computational Mathematics, vol. 34, Springer-Verlag, Berlin, 2005. MR 2104179 (2005g:65006)
  • [48] X. Xu, W. Huang, R. D. Russell, and J. F. Williams, Convergence of de Boor's algorithm for the generation of equidistributing meshes, IMA J. Numer. Anal. 31 (2011), no. 2, 580-596. MR 2813185 (2012m:65462),

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65M55, 65N22, 65Y05, 65M50, 65N50

Retrieve articles in all journals with MSC (2010): 65M55, 65N22, 65Y05, 65M50, 65N50

Additional Information

Ronald D. Haynes
Affiliation: Department of Mathematics and Statistics, Memorial University of Newfoundland, St. John’s, Newfoundland, Canada, A1C 5S7

Felix Kwok
Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong

Keywords: Domain decomposition, Schwarz methods, moving meshes, equidistribution, discretization, $M$-functions
Received by editor(s): June 11, 2014
Received by editor(s) in revised form: April 16, 2015
Published electronically: April 13, 2016
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society