On the Multilinear Systems, Part I: Comparison of Splittings of Tensors

Abstract

Tensors (hypermatrices) are multidimensional analogs of matrices. In the last few years, the tensor splitting problem has attracted much attention and has been studied extensively, from theory to solution methods and applications. This work, with its two parts, aims to contribute to reviewing the state-of-the-art studies for the tensor splittings and iterative methods for solving multilinear systems (tensor equations). In the first part of this paper, some new comparison theorems for two regular and weak regular splittings of real tensors are derived. These theorems are extensions of the classical comparison theorems of splittings of matrices. We show that, under certain conditions, the iterates implied for solving the multilinear system ${\mathcal {A}}{\textbf{x}}^{m-1} ={\textbf{b}}$ are monotone. We generalize theorems about H-splittings from matrices to tensors. These and comparison theorems for two regular and weak regular splittings can be easily extended for complex tensors. In addition, we discuss triangular splitting, ${\mathcal {M}}$-splitting, ${\mathcal {H}}$-splitting, ${\mathcal {H}}$-compatible splitting, and direct splitting of tensors. Some iterative methods and associated comparison theorems for solving the multilinear system ${\mathcal {A}}{\textbf{x}}^{m-1} ={\textbf{b}}$, when ${\mathcal {A}}$ is an ${\mathcal {H}}$-tensor, and a fast and smooth iterative method to solve ${\mathcal {A}}{\textbf{x}}^{m-1}={\textbf{b}}$ with the symmetric coefficient tensor ${\mathcal {A}}$ are given in the second part.

Keywords

Tensor splitting / Multilinear system / ${\mathcal {H}}$-tensor / 15A69 / 65F10

References

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

[2] BeauwensR. Factorization iterative methods, M-operators and H-operators. Numer. Math., 1979, 31: 335-357

[3] BeikFPA, Najafi-KalyaniM. Preconditioned iterative methods for multi-linear systems based on the majorization matrix. Linear Multilinear Algebra, 2022, 70(20): 5827-5846

[4] BozorgmaneshH, HajarianM. Solving tensor E-eigenvalue problem faster. Appl. Math. Lett., 2020, 100106020

[5] BruR, CorralC, GimenezI, MasJ. Classes of general H-matrices. Linear Algebra Appl., 2008, 429(10): 2358-2366

[6] BuC, ZhangX, ZhouJ, WangW, WeiW. The inverse, rank, and product of tensors. Linear Algebra Appl., 2014, 446: 269-280

[7] CheM, QiL, WeiL. Positive-definite tensors to nonlinear complementarity problems. J. Optim. Theory Appl., 2016, 168: 475-487

[8] CheM, WeiYTheory and Computation of Complex Tensors and Its Applications, 2020, Singapore. Springer.

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

[10] CsordasG, VargaRS. Comparisons of regular splittings of matrices. Numer. Math., 1984, 44: 23-35

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

[12] DehdeziEK. Iterative methods for sparse symmetric multilinear systems. Bull. Iran Math. Soc., 2024, 50(3): 1-20

[13] DehdeziEK, KarimiS. A gradient based iterative method and associated preconditioning technique for solving the large multilinear systems. Calcolo, 2021, 58(4): 1-19

[14] DingW, LuoZ, QiL. P-tensors, ${\rm P}_0$-tensors, and their applications. Linear Algebra Appl., 2018, 555: 336-354

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

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

[17] DuS, ZhangL, ChenC, QiL. Tensor absolute value equations. Sci. Chin. Math., 2018, 61: 1695-1710

[18] EinsteinAKoxAJ, KleinMJ, SchulmannR. The foundation of the general theory of relativity. The Collected Papers of Albert Einstein, 2007, Princeton. Princeton University Press. 1462006

[19] FrommerA, SzyldDB. H-splittings and two-stage iterative methods. Numer. Math., 1992, 63: 345-356

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

[21] 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

[22] HofbauerJ, SigmundK. Evolutionary game dynamics. Bull. Am. Math. Soc., 2003, 40: 479-519

[23] JiangZ, LiJ. Solving tensor absolute value equation. Appl. Numer. Math., 2021, 170: 255-268

[24] JiangZ, LiJ. Slice tensor splitting method for solving tensor equation. Appl. Math. Comput., 2024, 463. 128367

[25] KarimiS, DehdeziEK. Tensor splitting preconditioners for multilinear systems. J. Math. Model., 2024, 12(3): 481-499

[26] KofidisE, RegaliaP. On the best rank-1 approximation of higher-order supersymmetric tensors. SIAM J. Matrix Anal. Appl., 2002, 23: 863-884

[27] KoldaTG, BaderBW. Tensor decompositions and applications. SIAM Rev., 2009, 51(3): 455-500

[28] Li, D., Guan, H.B., Wang, X.Z.: Finding a nonnegative solution to an ${{\cal{M}}}$-tensor equation (2018). arXiv:1811.11343

[29] LiDH, XieS, XuHR. Splitting methods for tensor equations. Numer. Linear Algebra Appl., 2017, 245e2102

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

[31] LiX, LuoZ, ChenY. Sparse least squares solutions of multilinear equations. Linear Multilinear Algebra, 2024, 72(8): 1279-1291

[32] LiX, NgMK. Solving sparse non-negative tensor equations: algorithms and applications. Front. Math. Chin., 2015, 10: 649-680

[33] LiZ, DaiY, GaoH. Alternating projection method for a class of tensor equations. J. Comput. Appl. Math., 2019, 346: 490-504

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

[35] Lim, L.H.: Singular values and eigenvalues of tensors: a variational approach. In: Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. CAMSAP, vol. 05, no. 1, pp. 129–132. IEEE Computer Society Press, Piscataway (2005)

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

[37] LiuD, LiW, VongSW. A new preconditioned SOR method for solving multilinear systems with an ${{\cal{M} }}$-tensors. Calcolo, 2020, 57215

[38] LiuW, LiW. On the inverse of a tensor. Linear Algebra Appl., 2016, 495: 199-205

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

[40] Ma, W., Ding, W., Wei, Y.: Noda iteration for computing generalized tensor eigenpairs (2023). arXiv:2303.01327

[41] MarekI, SzyldDB. Comparison theorems for weak splittings of bounded operators. Numer. Math., 1990, 58(1): 387-397

[42] MollahsaniS, BeikFPA. Absolute value equations with tensor product structure: unique solvability and numerical solution. Appl. Math-Czech., 2022, 67(5): 657-674

[43] NeumaierA. New techniques for the analysis of linear interval equations. Linear Algebra Appl., 1984, 58: 273-325

[44] NeumaierA. On the comparison of $H$-matrices with $M$-matrices. Linear Algebra Appl., 1986, 83: 135-141

[45] PearsonK. Essentially positive tensors. Int. J. Algebra, 2010, 4: 421-427

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

[47] QiL, LuoZTensor Analysis: Spectral Theory and Special Tensors, 2017, Philadelphia. SIAM.

[48] SchröderJOperator Inequalities, 1980, New York. Academic Press.

[49] ShaoJ. A general product of tensors with applications. Linear Algebra Appl., 2013, 439: 2350-2366

[50] SmithJM, PriceGR. The logic of animal conflict. Nature, 1973, 246: 15-18

[51] TaylorPH, JonkerLB. Evolutionary stable strategies and game dynamics. Math. Biosci., 1978, 40: 145-156

[52] WangC, ChenH, WangY, YanH. An alternating shifted inverse power method for the extremal eigenvalues of fourth-order partially symmetric tensors. Appl. Math. Lett., 2023.

[53] WangX, CheM, MoC, WeiY. Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method. J. Comput. Appl. Math., 2023.

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

[55] WangX, CheM, WeiY. Preconditioned tensor splitting AOR iterative methods for ${\cal{H} }$-tensor equations. Numer. Linear Algebra Appl., 2020, 276e2329

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

[57] YangY, YangQ. Further results for Perron-Frobenius theorem for nonnegative tensors. SIAM J. Matrix Anal. Appl., 2010, 31(5): 2517-2530

[58] ZhangL, QiL, ZhouG. M-tensors and some applications. SIAM J. Matrix Anal. Appl., 2014, 35(2): 437-452

RIGHTS & PERMISSIONS

Shanghai University

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.