Overlapping multiplicative Schwarz preconditioning for linear and nonlinear systems. (English) Zbl 07807975
Summary: For linear and nonlinear systems arising from the discretization of PDEs, multiplicative Schwarz preconditioners can be defined based on subsets of the unknowns that derive from domain decomposition, field splitting, or other collections of conveniently solved subproblems, and are well established theoretically for nonoverlapping subsets. For overlapping subsets, establishing the equivalence of the preconditioned and original iterations is less trivial. We derive herein an explicit formulation for a variety of multiplicative Schwarz preconditioners including overlaps representative of interfacial and bulk coupling in multiphysics systems, thus extending theoretical support for the nonlinear multiplicative Schwarz preconditioned inexact Newton (MSPIN) algorithm to these classes. For nonlinear multiplicative Schwarz preconditioners with overlaps, we illustrate the performance through numerical experiments involving applications such as a shocked duct flow and a natural convection cavity flow. We begin with a broad introduction to nonlinear preconditioning to set the context for those new to the technique.
MSC:
| 65Nxx | Numerical methods for partial differential equations, boundary value problems |
| 65Fxx | Numerical linear algebra |
| 65Hxx | Nonlinear algebraic or transcendental equations |
References:
| [1] | Alomairy, R.; Ltaief, H.; Abduljabbar, M.; Keyes, D. E., Abstraction layer for standardizing APIs of task-based engines. IEEE Trans. Parallel Distrib. Syst., 2482-2495 (2020) |
| [2] | Alonazi, A.; Markomanolis, G.; Keyes, D., Asynchronous task-based parallelization of algebraic multigrid, 1-11 |
| [3] | An, H. B., On convergence of the additive Schwarz preconditioned inexact Newton method. SIAM J. Numer. Anal., 1850-1871 (2005) · Zbl 1111.65046 |
| [4] | Arnal, J.; Migallón, V.; Penadés, J.; Szyld, D. B., Newton additive and multiplicative Schwarz iterative methods. IMA J. Numer. Anal., 143-161 (2008) · Zbl 1137.65033 |
| [5] | Balay, S.; Abhyankar, S.; Adams, M. F.; Benson, S.; Brown, J.; Brune, P.; Buschelman, K.; Constantinescu, E. M.; Dalcin, L. A.D.; Eijkhout, V.; Gropp, W. D.; Hapla, V. T.I.; Jolivet, P. D.K.; Kaushik, D.; Knepley, M. G.; Kruger, S.; McInnes, L. C.; Mills, R. T.; Roman, J. E.; Rupp, K.; Smith, B. F.; Zampini, S.; Zhang, H.; Zhang, H. (2022), PETSc Web page. URL |
| [6] | Benzi, M. D.; Tuma, M. C., A sparse approximate inverse preconditioner for the conjugate gradient method. SIAM J. Sci. Comput., 1135-1149 (1996) · Zbl 0856.65019 |
| [7] | Bramble, J.; Pasciak, J.; Xu, J., Parallel multilevel preconditioners. Math. Comput., 1-22 (1990) · Zbl 0703.65076 |
| [8] | Broyden, C., Quasi-Newton methods · Zbl 0277.65031 |
| [9] | Brune, P. R.; Knepley, M.; Smith, B. F.; Tu, X., Composing scalable nonlinear algebraic solvers. SIAM Rev., 535-565 (2015) · Zbl 1336.65030 |
| [10] | Cai, X. C.; Dryja, M., Domain decomposition methods for monotone nonlinear elliptic problems. Contemp. Math., 21-27 (1994) · Zbl 0817.65127 |
| [11] | Cai, X. C.; Keyes, D. E., Nonlinearly preconditioned inexact Newton algorithms. SIAM J. Sci. Comput., 183-200 (2002) · Zbl 1015.65058 |
| [12] | Cai, X. C.; Keyes, D. E.; Marcinkowski, L., Nonlinear additive Schwarz preconditioners and application in computational fluid dynamics. Int. J. Numer. Methods Fluids, 1463-1470 (2002) · Zbl 1025.76040 |
| [13] | Cai, X. C.; Keyes, D. E.; Young, D. P., A nonlinear additive Schwarz preconditioned inexact Newton method for shocked duct flow, 343-350 |
| [14] | Cai, X. C.; Li, X. F., Inexact Newton methods with restricted additive Schwarz based nonlinear elimination for problems with high local nonlinearity. SIAM J. Sci. Comput., 746-762 (2011) · Zbl 1227.65045 |
| [15] | Cai, X. C.; Widlund, O. B., Multiplicative Schwarz algorithms for some nonsymmetric and indefinite problems. SIAM J. Numer. Anal., 936-952 (1993) · Zbl 0787.65016 |
| [16] | Chaouqui, F.; Chow, E.; Szyld, D. B., Asynchronous domain decomposition methods for nonlinear PDEs. Electron. Trans. Numer. Anal., 22-42 (2023) · Zbl 1512.65291 |
| [17] | Chaouqui, F.; Gander, M. J.; Kumbhar, P.; Vanzan, T., Linear and nonlinear substructured restricted additive Schwarz iterations and preconditioning. Numer. Algorithms, 81-107 (2022) · Zbl 1494.65100 |
| [18] | Coffey, T. S.; Kelley, C. T.; Keyes, D. E., Pseudotransient continuation and differential-algebraic equations. SIAM J. Sci. Comput., 553-569 (2003) · Zbl 1048.65080 |
| [19] | De Vahl Davis, G., Natural convection of air in a square cavity: a bench mark numerical solution. Int. J. Numer. Methods Fluids, 249-264 (1983) · Zbl 0538.76075 |
| [20] | Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1996), SIAM: SIAM Philadelphia · Zbl 0847.65038 |
| [21] | Dolean, V.; Gander, M. J.; Kwok, F.; Masson, R.; Kheriji, W., Nonlinear preconditioning: how to use a nonlinear Schwarz method to precondition Newton’s method. SIAM J. Sci. Comput., 3357-3380 (2016) · Zbl 1352.65326 |
| [22] | Dryja, M.; Hackbusch, W., On the nonlinear domain decomposition method. BIT Numer. Math., 296-311 (1997) · Zbl 0891.65126 |
| [23] | Eisenstat, S. C.; Walker, H. F., Globally convergent inexact Newton methods. SIAM J. Optim., 393-422 (1994) · Zbl 0814.65049 |
| [24] | Eisenstat, S. C.; Walker, H. F., Choosing the forcing terms in an inexact Newton method. SIAM J. Sci. Comput., 16-32 (1996) · Zbl 0845.65021 |
| [25] | Ernst, R.; Flemisch, B.; Wohlmuth, B., A multiplicative Schwarz method and its application to nonlinear acoustic-structure interaction. ESAIM: Math. Model. Numer. Anal., 487-506 (2009) · Zbl 1165.74017 |
| [26] | Gander, M. J.; Loisel, S.; Szyld, D. B., An optimal block iterative method and preconditioner for banded matrices with applications to PDEs on irregular domains. SIAM J. Matrix Anal. Appl., 653-680 (2012) · Zbl 1252.65068 |
| [27] | Heinlein, A.; Lanser, M., Additive and hybrid nonlinear two-level Schwarz methods and energy minimizing coarse spaces for unstructured grids. SIAM J. Sci. Comput., A2461-A2488 (2020) · Zbl 1453.65428 |
| [28] | Huang, J.; Yang, C.; Cai, X. C., A nonlinearly preconditioned inexact Newton algorithm for steady lattice Boltzmann equations. SIAM J. Sci. Comput., 1701-1724 (2016) · Zbl 1339.65236 |
| [29] | Hwang, F. N.; Lin, H. L.; Cai, X. C., Two-level nonlinear elimination based preconditioners for inexact Newton methods with application in shocked duct flow calculation. Electron. Trans. Numer. Anal., 239-251 (2010) · Zbl 1205.65180 |
| [30] | Hwang, F. N.; Su, Y. C.; Cai, X. C., A parallel adaptive nonlinear elimination preconditioned inexact Newton method for transonic full potential equation. Comput. Fluids, 96-107 (2015) · Zbl 1390.76271 |
| [31] | Kahou, G. A.A.; Kamgnia, E.; Philippe, B., An explicit formulation of the multiplicative Schwarz preconditioner. Appl. Numer. Math., 1197-1213 (2007) · Zbl 1134.65035 |
| [32] | Kelley, C. T., Iterative Methods for Linear and Nonlinear Equations (1995), SIAM: SIAM Philadelphia · Zbl 0832.65046 |
| [33] | Klawonn, A.; Lanser, M.; Rheinbach, O., Nonlinear FETI-DP and BDDC methods. SIAM J. Sci. Comput., A737-A765 (2014) · Zbl 1296.65178 |
| [34] | Klawonn, A.; Lanser, M.; Rheinbach, O., Toward extremely scalable nonlinear domain decomposition methods for elliptic partial differential equations. SIAM J. Sci. Comput., C667-C696 (2015) · Zbl 1329.65294 |
| [35] | Klawonn, A.; Lanser, M.; Uran, M., Adaptive nonlinear elimination in nonlinear FETI-DP methods (2021), University of Cologne, Technical Report |
| [36] | Knoll, D. A.; Keyes, D. E., Jacobian-free Newton-Krylov methods: a survey of approaches and applications. J. Comput. Phys., 357-397 (2004) · Zbl 1036.65045 |
| [37] | Liu, L.; Hwang, F. N.; Luo, L.; Cai, X. C.; Keyes, D. E., A nonlinear elimination preconditioned inexact Newton algorithm. SIAM J. Sci. Comput., A1579-A1605 (2022) · Zbl 1492.65144 |
| [38] | Liu, L.; Keyes, D. E., Field-split preconditioned inexact Newton algorithms. SIAM J. Sci. Comput., 1388-1409 (2015) · Zbl 1328.65122 |
| [39] | Liu, L.; Keyes, D. E., Convergence analysis for the multiplicative Schwarz preconditioned inexact Newton algorithm. SIAM J. Numer. Anal., 3145-3166 (2016) · Zbl 1352.65142 |
| [40] | Liu, L.; Keyes, D. E., Approximate error bounds on solutions of nonlinearly preconditioned PDEs. SIAM J. Sci. Comput., A2526-A2554 (2021) · Zbl 1469.49028 |
| [41] | Liu, L.; Keyes, D. E.; Krause, R., A note on adaptive nonlinear preconditioning techniques. SIAM J. Sci. Comput., A1171-A1186 (2018) · Zbl 1446.65027 |
| [42] | Liu, L.; Zhang, W.; Keyes, D. E., Nonlinear multiplicative Schwarz preconditioning in natural convection cavity flow, 227-235, ddm.org · Zbl 1445.76074 |
| [43] | Luo, L.; Cai, X. C., PIN-L: preconditioned inexact Newton with learning capability for nonlinear systems of equations. SIAM J. Sci. Comput., A849-A871 (2023) · Zbl 1524.76136 |
| [44] | Luo, L.; Cai, X. C.; Keyes, D. E., Nonlinear preconditioning strategies for two-phase flows in porous media discretized by a fully implicit discontinuous Galerkin method. SIAM J. Sci. Comput., S317-S344 (2021) · Zbl 1490.65203 |
| [45] | Luo, L.; Cai, X. C.; Yan, Z. Z.; Xu, L.; Keyes, D. E., A multilayer nonlinear elimination preconditioned inexact Newton method for steady-state incompressible flow problems in three dimensions. SIAM J. Sci. Comput., B1404-B1428 (2020) · Zbl 1456.76104 |
| [46] | Luo, L.; Shiu, W. S.; Chen, R. L.; Cai, X. C., A nonlinear elimination preconditioned inexact Newton method for blood flow problems in human artery with stenosis. J. Comput. Phys. (2019) · Zbl 1453.65109 |
| [47] | Meijerink, J. A.; Van Der Vorst, H., An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Math. Comput., 148-162 (1977) · Zbl 0349.65020 |
| [48] | Nabben, R.; Szyld, D. B., Convergence theory of restricted multiplicative Schwarz methods. SIAM J. Numer. Anal., 2318-2336 (2003) · Zbl 1040.65031 |
| [49] | Patankar, S. V., Numerical Heat Transfer and Fluid Flow (1980), Taylor & Francis · Zbl 0521.76003 |
| [50] | Saad, Y., Practical use of polynomial preconditionings for the conjugate gradient method. SIAM J. Sci. Stat. Comput., 865-881 (1985) · Zbl 0601.65019 |
| [51] | Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM · Zbl 1002.65042 |
| [52] | Schwarz, H. A., Über einen Grenzübergang durch alternierendes Verfahren. Vierteljahrsschr. Nat.forsch. Ges. Zür., 27-286 (1870) |
| [53] | Shampine, L. F.; Gear, C. W., A user’s view of solving stiff ordinary differential equations. SIAM Rev., 1-17 (1979) · Zbl 0415.65038 |
| [54] | Sheldon, J. W.; Zondak, B.; Cardwell, W. T., One-dimensional, incompressible, noncapillary, two-phase fluid flow in a porous medium. Trans. AIME, 136-143 (1959) |
| [55] | Skogestad, J. O.; Keilegavlen, E.; Nordbotten, J. M., Domain decomposition strategies for nonlinear flow problems in porous media. J. Comput. Phys., 439-451 (2013) |
| [56] | Strang, G. S., Introduction to Applied Mathematics (1986), Wellesley-Cambridge Press · Zbl 0618.00015 |
| [57] | Toselli, A.; Widlund, O., Domain Decomposition Methods—Algorithms and Theory (2006), Springer |
| [58] | Walker, H. F.; Ni, P., Anderson acceleration for fixed-point iterations. SIAM J. Numer. Anal., 1715-1735 (2011) · Zbl 1254.65067 |
| [59] | Wong, Z. Y.; Kwok, F.; Horne, R. N.; Tchelepi, H. A., Sequential-implicit Newton method for multiphysics simulation. J. Comput. Phys., 155-178 (2019) · Zbl 1452.86003 |
| [60] | Yang, H. J.; Hwang, F. N., An adaptive nonlinear elimination preconditioned inexact Newton algorithm for highly local nonlinear multicomponent PDE systems. Appl. Numer. Math., 100-115 (2018) · Zbl 1397.65245 |
| [61] | Yang, H. J.; Yang, C.; Sun, S. Y., Active-set reduced-space methods with nonlinear elimination for two-phase flow problems in porous media. SIAM J. Sci. Comput., B593-B618 (2016) · Zbl 1383.76384 |
| [62] | Yang, H. J.; Yang, C.; Sun, S. Y., Nonlinearly preconditioned semismooth Newton methods for variational inequality solution of two-phase flow in porous media. J. Comput. Phys., 1-20 (2017) · Zbl 1378.76115 |
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.
