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}{\mathbf{x}}^{m-1}=\mathbf{b}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathcal {A}}{\textbf{x}}^{m-1} ={\textbf{b}}$$\end{document}

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}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathcal {M}}$$\end{document}

-splitting,

\mathcal{H}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathcal {H}}$$\end{document}

-splitting,

\mathcal{H}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathcal {H}}$$\end{document}

-compatible splitting, and direct splitting of tensors. Some iterative methods and associated comparison theorems for solving the multilinear system

\mathcal{A}{\mathbf{x}}^{m-1}=\mathbf{b}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathcal {A}}{\textbf{x}}^{m-1} ={\textbf{b}}$$\end{document}

, when

\mathcal{A}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathcal {A}}$$\end{document}

is an

\mathcal{H}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathcal {H}}$$\end{document}

-tensor, and a fast and smooth iterative method to solve

\mathcal{A}{\mathbf{x}}^{m-1}=\mathbf{b}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathcal {A}}{\textbf{x}}^{m-1}={\textbf{b}}$$\end{document}

with the symmetric coefficient tensor

\mathcal{A}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathcal {A}}$$\end{document}

are given in the second part.

Keywords

Tensor splitting / Multilinear system /

\mathcal{H}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\mathcal {H}}$$\end{document}

-tensor / 15A69 / 65F10

References

[1] Bai X, He H, Ling C, Zhou G. A nonnegativity preserving algorithm for multilinear systems with nonsingular M\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\cal{M} }}$$\end{document}-tensors. Numer. Algorithms, 2021, 87(3): 1301-1320

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

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

[4] Bozorgmanesh H, Hajarian M. Solving tensor E-eigenvalue problem faster. Appl. Math. Lett., 2020, 100: 106020

[5] Bru R, Corral C, Gimenez I, Mas J. Classes of general H-matrices. Linear Algebra Appl., 2008, 429(10): 2358-2366

[6] Bu C, Zhang X, Zhou J, Wang W, Wei W. The inverse, rank, and product of tensors. Linear Algebra Appl., 2014, 446: 269-280

[7] Che M, Qi L, Wei L. Positive-definite tensors to nonlinear complementarity problems. J. Optim. Theory Appl., 2016, 168: 475-487

[8] Che M, Wei Y. Theory and Computation of Complex Tensors and Its Applications, 2020, Singapore, Springer

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

[10] Csordas G, Varga RS. Comparisons of regular splittings of matrices. Numer. Math., 1984, 44: 23-35

[11] Cui LB, Li MH, Song Y. Preconditioned tensor splitting iterations method for solving multi-linear systems. Appl. Math. Lett., 2019, 96: 89-94

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

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

[14] Ding W, Luo Z, Qi L. P-tensors, P0\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\rm P}_0$$\end{document}-tensors, and their applications. Linear Algebra Appl., 2018, 555: 336-354

[15] Ding W, Qi L, Wei Y. M\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\cal{M} }}$$\end{document}-tensors and nonsingular M\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\cal{M} }}$$\end{document}-tensors. Linear Algebra Appl., 2013, 439(10): 3264-3278

[16] Ding W, Wei Y. Solving multi-linear system with M\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\cal{M} }}$$\end{document}-tensors. J. Sci. Comput., 2016, 68: 689-715

[17] Du S, Zhang L, Chen C, Qi L. Tensor absolute value equations. Sci. Chin. Math., 2018, 61: 1695-1710

[18] Einstein A. Kox AJ, Klein MJ, Schulmann R. The foundation of the general theory of relativity. The Collected Papers of Albert Einstein, 2007, Princeton, Princeton University Press: 146-2006

[19] Frommer A, Szyld DB. H-splittings and two-stage iterative methods. Numer. Math., 1992, 63: 345-356

[20] Han L. A homotopy method for solving multilinear systems with M\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\cal{M} }}$$\end{document}-tensors. Appl. Math. Lett., 2017, 69: 49-54

[21] He H, Ling C, Qi L, Zhou G. A globally and quadratically convergent algorithm for solving multilinear systems with M\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\cal{M} }}$$\end{document}-tensors. J. Sci. Comput., 2018, 76(3): 1718-1741

[22] Hofbauer J, Sigmund K. Evolutionary game dynamics. Bull. Am. Math. Soc., 2003, 40: 479-519

[23] Jiang Z, Li J. Solving tensor absolute value equation. Appl. Numer. Math., 2021, 170: 255-268

[24] Jiang Z, Li J. Slice tensor splitting method for solving tensor equation. Appl. Math. Comput., 2024, 463 128367

[25] Karimi S, Dehdezi EK. Tensor splitting preconditioners for multilinear systems. J. Math. Model., 2024, 12(3): 481-499

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

[27] Kolda TG, Bader BW. 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 M\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\cal{M}}}$$\end{document}-tensor equation (2018). arXiv:1811.11343

[29] Li DH, Xie S, Xu HR. Splitting methods for tensor equations. Numer. Linear Algebra Appl., 2017, 24(5): e2102

[30] Li W, Liu D, Vong SW. Comparison results for splitting iterations for solving multi-linear systems. Appl. Numer. Math., 2018, 134: 105-121

[31] Li X, Luo Z, Chen Y. Sparse least squares solutions of multilinear equations. Linear Multilinear Algebra, 2024, 72(8): 1279-1291

[32] Li X, Ng MK. Solving sparse non-negative tensor equations: algorithms and applications. Front. Math. Chin., 2015, 10: 649-680

[33] Li Z, Dai Y, Gao H. Alternating projection method for a class of tensor equations. J. Comput. Appl. Math., 2019, 346: 490-504

[34] Liang M, Zheng B, Zhao R. 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] Liu D, Li W, Vong SW. The tensor splitting with application to solve multilinear systems. J. Comput. Appl. Math., 2018, 330: 75-94

[37] Liu D, Li W, Vong SW. A new preconditioned SOR method for solving multilinear systems with an M\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\cal{M} }}$$\end{document}-tensors. Calcolo, 2020, 57(2): 15

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

[39] Lv CQ, Ma CF. 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] Marek I, Szyld DB. Comparison theorems for weak splittings of bounded operators. Numer. Math., 1990, 58(1): 387-397

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

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

[44] Neumaier A. On the comparison of H\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$H$$\end{document}-matrices with M\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$M$$\end{document}-matrices. Linear Algebra Appl., 1986, 83: 135-141

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

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

[47] Qi L, Luo Z. Tensor Analysis: Spectral Theory and Special Tensors, 2017, Philadelphia, SIAM

[48] Schröder J. Operator Inequalities, 1980, New York, Academic Press

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

[50] Smith JM, Price GR. The logic of animal conflict. Nature, 1973, 246: 15-18

[51] Taylor PH, Jonker LB. Evolutionary stable strategies and game dynamics. Math. Biosci., 1978, 40: 145-156

[52] Wang C, Chen H, Wang Y, Yan H. An alternating shifted inverse power method for the extremal eigenvalues of fourth-order partially symmetric tensors. Appl. Math. Lett., 2023

[53] Wang X, Che M, Mo C, Wei Y. Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method. J. Comput. Appl. Math., 2023

[54] Wang X, Che M, Wei Y. Neural networks based approach solving multi-linear systems with M\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\cal{M} }}$$\end{document}-tensors. Neurocomputing, 2019, 351: 33-42

[55] Wang X, Che M, Wei Y. Preconditioned tensor splitting AOR iterative methods for H\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\cal{H} }$$\end{document}-tensor equations. Numer. Linear Algebra Appl., 2020, 27(6): e2329

[56] Xie Z, Jin XQ, Wei Y. Tensor methods for solving symmetric M\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${{\cal{M} }}$$\end{document}-tensor systems. J. Sci. Comput., 2018, 74(1): 412-425

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

[58] Zhang L, Qi L, Zhou G. M-tensors and some applications. SIAM J. Matrix Anal. Appl., 2014, 35(2): 437-452

RIGHTS & PERMISSIONS

Shanghai University