Overlapping Domain Decomposition Methods Based on Tensor Format for Solving High-Dimensional Partial Differential Equations

Abstract

Based on the equivalence between the Sylvester tensor equation and the linear equation obtained by discretization of partial differential equations (PDEs), an overlapping Schwarz alternative method based on the tensor format and an overlapping parallel Schwarz method based on the tensor format for solving high-dimensional PDEs are proposed. The complexity of the new algorithms is discussed. Finally, the feasibility and effectiveness of the new methods are verified by some numerical examples.

Keywords

High-dimensional partial differential equations (PDEs) / Sylvester tensor equation / Overlapping Schwarz alternative method based on tensor format / Overlapping parallel Schwarz method based on tensor format

References

[1] BaiZ-Z. On Hermitian and skew-Hermitian splitting iteration methods for continuous Sylvester equations. J. Comput. Math., 2011, 292185-198.

[2] BaiZ-Z, PanJ-YMatrix Analysis and Computations, 2021PhiladelphiaSIAM.

[3] BaurU, BennerP. Cross-Gramian based model reduction for data-sparse systems. Electron. Trans. Numer. Anal., 2008, 31: 256-270

[4] BeikFPA, Ahmadi-AslS. Residual norm steepest descent based iterative algorithms for Sylvester tensor equations. J. Math. Model., 2015, 22115-131

[5] BeikFPA, MovahedFS, Ahmadi-AslS. On the Krylov subspace methods based on tensor format for positive definite Sylvester tensor equations. Numer. Linear Algebra. Appl., 2016, 233444-466.

[6] BoglaevI. On a domain decomposition algorithm for a singularly perturbed reaction-diffusion problem. J. Comput. Appl. Math., 1998, 982213-232.

[7] Boglaev, I: An implicit-explicit domain decomposition algorithm for a singularly perturbed parabolic problem. Comput. Math. Appl. 38(5/6), 41–53 (1999)

[8] Boglaev, I: Domain decomposition in boundary layer for singularly perturbed problem. Appl. Numer. Math. 34(2), 145–166 (2000)

[9] Cai, X.-C., Casarin, M.A., Elliott, F.W.: Overlapping Schwarz algorithms for solving Helmholtz’s equation. In: Domain Decomposition Methods, vol. 10, pp. 391–399 (1998)

[10] ChenY-H, LiC-L. A tensor multigrid method for solving Sylvester tensor equations. IEEE Trans. Auto. Sci. Eng., 2023.

[11] ChenZ, LuL-Z. A projection method and Kronecker product preconditioner for solving Sylvester tensor equations. Sci. China Math., 2012, 5561281-1292.

[12] ChuD, TanRCE. Numerically reliable computing for the row by row decoupling problem with stability. SIAM J. Matrix Anal. Appl., 2002, 2341143-1170.

[13] DattaBN, LinW-W, WangJ-N. Robust partial pole assignment for vibrating systems with aerodynamic effects. IEEE Trans. Autom. Control., 2006, 51211979-1984.

[14] DawsonCN, DuQ, DupontTF. A finite difference domain decomposition algorithm for numerical solution of the heat equation. Math. Comput., 1991, 5719563-63.

[15] DawsonCN, DupontTF. Explicit/implicit, conservative domain decomposition procedures for parabolic problems based on block-centered finite differences. SIAM J. Numer. Anal., 1994, 3141045-1061.

[16] Gander, M.J., Halpern, L., Nataf, F.: Optimized Schwarz methods. In: Proceedings of the 12th International Conference on Domain Decomposition Methods, Japan, pp. 15–27 (2001)

[17] GrasedyckL. Existence and computation of low Kronecker-rank approximations for large linear systems of tensor product structure. Computing, 2004, 723/4247-265

[18] HeyouniM, Saberi-MovahedF, TajaddiniA. A tensor format for the generalized Hessenberg method for solving Sylvester tensor equations. J. Comput. Appl. Math., 2020, 377. 112878

[19] KangL-SDomain Decomposition and Parallel Algorithm, 1987WuhanWuhan University Press.

[20] KangL-S, QuanH-YSplitting Method for Numerical Solution of High Dimensional PDE, 1990ShanghaiSci. Technology Press

[21] KarimiS, DehghanM. Global least squares method based on tensor form to solve linear systems in Kronecker format. Trans. Inst. Meas. Control, 2018, 4072378-2386.

[22] LiJ-H, DingF, YangG-W. Maximum likelihood least squares identification method for input nonlinear finite impulse response moving average systems. Math. Comput. Model., 2012, 55: 442-450.

[23] Lions, P.L.: On Schwarz Alternating Method I: First International Symposium on Domain Decomposition Methods for Partial Differential Equations, pp. 1–42. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1988)

[24] Lions, P.L.: On Schwarz Alternating Method II: Stochastic Interpretation and Order Properties, pp. 47–70. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1989)

[25] Lions, P.L.: On the Schwarz Alternating Method III: a Variant for Nonoverlapping Subdomains, pp. 202–223. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1990)

[26] LuT, ShihTM, LiemCB. Two synchronous parallel algorithms for partial differential equations. J. Comput. Math., 1991, 9174-85

[27] LyuG-X, MaF-M. Finite difference domain decomposition algorithm for two-dimensional heat equation. J. Numer. Methods Comput. Appl., 2006, 27296-105

[28] LyuT, ShiJ-M, LiZ-BDomain Decomposition Methods: New Numerical Techniques for Solving PDE, 1997BeijingScience Press

[29] McInnes, L.C., Susan-Resigna, R., Keyes, D.E.: Additive Schwarz methods with nonreflecting boundary conditions for the parallel computation of Helmholtz problems. In: Domain Decomposition Methods (Boulder, CO, 1997), vol. 10, pp. 325–333 (1998)

[30] MillerK. Numerical analogs to the Schwarz alternating procedure. Numer. Math., 1965, 7291-103.

[31] Najafi-KalyaniM, BeikFPA, JbilouK. On global iterative schemes based on Hessenberg process for (ill-posed) Sylvester tensor equations. J. Comput. Appl. Math., 2020, 373. 112216

[32] NatafF. Absorbing boundary conditions in block Gauss-Seidel methods for the convection problems. Math. Models Methods Appl. Sci., 1996, 64481-502.

[33] NatafF, RogierF. Factorization of the convection-diffusion operator and the Schwarz algorithm. Math. Models Methods Appl. Sci., 1995, 5167-93.

[34] Schwarz, H.A.: Gesammelte Mathematiche Abhandlungen, vol. 2, pp. 133–143. Springer, Berlin (1890) (First published in Viertel jahrsschrift der Naturforschenden Gesellschaft 15(2), 272–286 (1870))

[35] TangW-PSchwarz Splitting and Template Operators, 1987StanfordStanford University

[36] WangW, DingF, DaiJ-Y. Maximum likelihood least squares identification for systems with autoregressive moving average noise. Appl. Math. Model., 2012, 3651842-1853.

[37] ZhangX-F, WangQ-W. Developing iterative algorithms to solve Sylvester tensor equations. Appl. Math. Comput., 2021, 409126403

Funding

National Natural Science Foundation of China(12161027)

Natural Science Foundation of Guangxi Zhuang Autonomous Region(2020GXNSFAA159143)

RIGHTS & PERMISSIONS

Shanghai University