Restarted Nonnegativity Preserving Tensor Splitting Methods via Relaxed Anderson Acceleration for Solving Multilinear Systems

Abstract

Multilinear systems play an important role in scientific calculations of practical problems. In this paper, we consider a tensor splitting method with a relaxed Anderson acceleration for solving the multilinear systems. The new method preserves the nonnegativity for every iterative step and improves the existing ones. Furthermore, the convergence analysis of the proposed method is given. The new algorithm performs effectively for numerical experiments.

Keywords

Tensor splitting / Multilinear systems / Anderson acceleration / ${{\mathcal {M}}}$-tensor')">Strong ${{\mathcal {M}}}$-tensor / 15A48 / 15A69 / 65F10 / 65H10

References

[1] AzimzadehP, BayraktarE. High order Bellman equations and weakly chained diagonally dominant tensors. SIAM J. Matrix Anal. Appl., 2019, 40(1): 276-298

[2] BaiX, HeH, LingC, ZhouG. A nonnegativity preserving algorithm for multilinear systems with nonsingular ${\cal{M} } $-tensors. Numer. Algorithms, 2021, 87(3): 1301-1320

[3] ChenY, LiC. A new preconditioned AOR method for solving multi-linear systems. Linear Multilinear Algebra, 2024, 72(9): 1385-1402

[4] CuiL, LiM, SongY. Preconditioned tensor splitting iterations method for solving multi-linear systems. Appl. Math. Lett., 2019, 96: 89-94

[5] DingW, QiL, WeiY. ${\cal{M} } $-tensors and nonsingular ${\cal{M} } $-tensors. Linear Algebra Appl., 2013, 439: 3264-3278

[6] DingW, WeiY. Solving multi-linear system with ${\cal{M} } $-tensors. J. Sci. Comput., 2016, 68(2): 689-715

[7] HanL. A homotopy method for solving multilinear systems with ${\cal{M} } $-tensors. Appl. Math. Lett., 2017, 69: 49-54

[8] HeH, LingC, QiL, ZhouG. A globally and quadratically convergent algorithm for solving multilinear systems with ${\cal{M} } $-tensors. J. Sci. Comput., 2018, 76(3): 1718-1741

[9] KoldaTG, BaderBW. Tensor decompositions and applications. SIAM Rev., 2009, 51: 455-500

[10] Lai, F., Li, W., Peng, X., Chen, Y.: Anderson accelerated fixed-point iteration for multilinear PageRank. Numer. Linear Algebra Appl. 30(5), e2499 (2023)

[11] LiD, GuanHB, WangXZ. Finding a nonnegative solution to an ${\cal{M} } $-tensor equation. Pac. J. Optim., 2020, 16(3): 419-440

[12] LiD , XieS, XuH. Splitting methods for tensor equations. Numer. Linear Algebra Appl., 2017, 245e2102

[13] LiD, XuJ, GuanH. Newton’s method for ${\cal{M} } $-tensor equations. J. Optim. Theory Appl., 2021, 190(2): 628-649

[14] LiW, LiuD, VongSW. Comparison results for splitting iterations for solving multi-linear systems. Appl. Numer. Math., 2018, 134: 105-121

[15] LiangM, ZhengB, ZhaoR. Alternating iterative methods for solving tensor equations with applications. Numer. Algorithms, 2019, 80(4): 1437-1465

[16] Lim, L.-H.: Singular values and eigenvalues of tensors: a variational approach. In: CAMSAP’05: Proceeding of the IEEE International Workshop on Computational Advances in Multi-sensor Adaptive Processing, pp. 129–132 (2005)

[17] LiuD, LiW, VongSW. The tensor splitting with application to solve multi-linear systems. J. Comput. Appl. Math., 2018, 330: 75-94

[18] LiuD, LiW, VongSW. A new preconditioned SOR method for solving multi-linear systems with an ${\cal{M} } $-tensor. Calcolo, 2020, 57(2): 1-18

[19] LiuL, LiX, LiuS. Further study on existence and uniqueness of positive solution for tensor equations. Appl. Math. Lett., 2022, 124107686

[20] LyuC, MaC. A Levenberg-Marquardt method for solving semi-symmetric tensor equations. J. Comput. Appl. Math., 2018, 332: 13-25

[21] NiQ, QiL. A quadratically convergent algorithm for finding the largest eigenvalue of a nonnegative homogeneous polynomial map. J. Glob. Optim., 2015, 61(4): 627-641

[22] Niu, J., Du, L., Sogabe, T., Zhang, S.: A tensor alternating Anderson-Richardson method for solving multilinear systems with ${\cal{M}} $-tensors (2024). arXiv:2401.07602

[23] Ortega, J.M., Rheinboldt, W.C.: Iterative solution of nonlinear equations in several variables. In: Classics in Applied Mathematics, vol. 30. Society for Industrial and Applied Mathematics, Philadelphia (2000)

[24] QiL. Eigenvalues of a real supersymmetric tensor. J. Symb. Comput., 2005, 40: 1302-1324

[25] Qi, L., Luo, Z.: Tensor Analysis: Spectral Theory and Special Tensors. Society for Industrial and Applied Mathematics (2017)

[26] TothA, KelleyCT. Convergence analysis for Anderson acceleration. SIAM J. Numer. Anal., 2015, 53(2): 805-819

[27] WalkerHF, NiP. Anderson acceleration for fixed-point iterations. SIAM J. Numer. Anal., 2011, 49(4): 1715-1735

[28] WangX, CheM, WeiY. Neural networks based approach solving multi-linear systems with ${\cal{M} } $-tensors. Neurocomputing, 2019, 351: 33-42

[29] WangX, MoC, CheM, WeiY. Accelerated dynamical approaches for finding the unique positive solution of ${\cal{K}} {\cal{S}} $-tensor equations. Numer. Algorithms, 2021, 88(4): 1787-1810

[30] XieZ, JinX, WeiY. Tensor methods for solving symmetric ${\cal{M} }$-tensor systems. J. Sci. Comput., 2018, 74(1): 412-425

[31] ZhangL, QiL, ZhouG. ${\cal{M} } $-tensors and some applications. SIAM J. Matrix Anal. Appl., 2014, 35: 437-452

[32] ZhangY, LiuQ, ChenZ. Preconditioned Jacobi type method for solving multi-linear systems with ${\cal{M} } $-tensors. Appl. Math. Lett., 2020, 104106287

Funding

National Natural Science Foundation of China(12101136)

Guangdong Basic and Applied Basic Research Foundations(2023A1515011633)

the Opening Project of Guangdong Province Key Laboratory of Computational Science at the Sun Yat sen University(2021004)

the Open Project of Key Laboratory, School of Mathematical Sciences, Chongqing Normal University(CSSXKFKTQ202002)

Chongqing Municipal Basic and Frontier Research Project(KJQN202100505)

Natural Science Foundation Project of Chongqing, Chongqing Science and Technology Commission(cstc2021jcyj-msxmX0195)

the Project of Science and Technology of Guangzhou(2024A04J2056)

RIGHTS & PERMISSIONS

Shanghai University