New preconditioned Gauss-Seidel type methods for solving multi-linear systems with $ \mathcal{M} $-tensors

Xiuwen Zheng; Jingjing Cui; Zhengge Huang; Xiuwen Zheng; Jingjing Cui; Zhengge Huang

doi:10.3934/era.2025153

Electronic Research Archive

2025, Volume 33, Issue 6: 3450-3481. doi: 10.3934/era.2025153

Previous Article Next Article

Research article

New preconditioned Gauss-Seidel type methods for solving multi-linear systems with $ \mathcal{M} $-tensors

School of Mathematical Sciences, Center for Applied Mathematics of Guangxi, Guangxi Minzu University, Nanning 530006, China

Received: 21 January 2025 Revised: 06 April 2025 Accepted: 19 May 2025 Published: 04 June 2025

In this paper, we propose a new preconditioner for the multi-linear systems with $ \mathcal{M} $-tensors by utilizing some elements in the first row and column of the majorization matrix associated with the system tensor. The new preconditioner generalizes the one proposed in (Calcolo, 57(2020) 15). Then, we establish three new preconditioned Gauss-Seidel type methods for solving the multi-linear systems with $ \mathcal{M} $-tensors. Theoretically, convergence theorems and comparison theorems are given, which show that the proposed methods are convergent, and the third one has the fastest convergence rate and performs better than the original Gauss-Seidel method and the one in (Calcolo, 57(2020) 15). Also, the monotonic theorem is studied. Finally, numerical experiments including some applications in the higher-order Markov chain and directed graph verify the correctness of the theoretical analyses and the effectiveness of the proposed methods, and illustrate that they are superior to the original Gauss-Seidel method and the preconditioned Gauss-Seidel methods in (Calcolo, 57(2020) 15) and (Appl. Numer. Math., 134(2018) 105–121).
- multi-linear systems with $ \mathcal{M} $-tensors,
- preconditioning,
- tensor splitting,
- preconditioned Gauss-Seidel type method,
- convergence theorems,
- comparison theorems
Citation: Xiuwen Zheng, Jingjing Cui, Zhengge Huang. New preconditioned Gauss-Seidel type methods for solving multi-linear systems with $ \mathcal{M} $-tensors[J]. Electronic Research Archive, 2025, 33(6): 3450-3481. doi: 10.3934/era.2025153

Related Papers:

Abstract

In this paper, we propose a new preconditioner for the multi-linear systems with $ \mathcal{M} $-tensors by utilizing some elements in the first row and column of the majorization matrix associated with the system tensor. The new preconditioner generalizes the one proposed in (Calcolo, 57(2020) 15). Then, we establish three new preconditioned Gauss-Seidel type methods for solving the multi-linear systems with $ \mathcal{M} $-tensors. Theoretically, convergence theorems and comparison theorems are given, which show that the proposed methods are convergent, and the third one has the fastest convergence rate and performs better than the original Gauss-Seidel method and the one in (Calcolo, 57(2020) 15). Also, the monotonic theorem is studied. Finally, numerical experiments including some applications in the higher-order Markov chain and directed graph verify the correctness of the theoretical analyses and the effectiveness of the proposed methods, and illustrate that they are superior to the original Gauss-Seidel method and the preconditioned Gauss-Seidel methods in (Calcolo, 57(2020) 15) and (Appl. Numer. Math., 134(2018) 105–121).

References

[1]	L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40 (2005), 1302–1324. https://doi.org/10.1016/j.jsc.2005.05.007 doi: 10.1016/j.jsc.2005.05.007
[2]	H. R. Xu, D. H. Li, S. L. Xie, An equivalent tensor equation to the tensor complementarity problem with positive semi-definite $\mathcal{Z}$-tensor, Optim. Lett., 13 (2019), 685–694. https://doi.org/10.1007/s11590-018-1268-4 doi: 10.1007/s11590-018-1268-4
[3]	L. B. Cui, C. Chen, W. Li, M. K. Ng, An eigenvalue problem for even order tensors with its applications, Linear Multilinear Algebra, 64 (2016), 602–621. https://doi.org/10.1080/03081087.2015.1071311 doi: 10.1080/03081087.2015.1071311
[4]	W. Li, M. K. Ng, On the limiting probability distribution of a transition probability tensor, Linear Multilinear Algebra, 62 (2014), 362–385. https://doi.org/10.1080/03081087.2013.777436 doi: 10.1080/03081087.2013.777436
[5]	D. Liu, W. Li, S. W. Vong, Relaxation methods for solving the tensor equation arising from the higher-order Markov chains, Numer. Linear Algebra Appl., 330 (2018), 75–94. https://doi.org/10.1002/nla.2260 doi: 10.1002/nla.2260
[6]	D. F. Gleich, L. H. Lim, Y. Yu, Multilinear pagerank, SIAM J. Matrix Anal. Appl., 36 (2015), 1507–1541. https://doi.org/10.1137/140985160 doi: 10.1137/140985160
[7]	W. Ding, L. Qi, Y. Wei, $\mathcal{M}$-tensors and nonsingular $\mathcal{M}$-tensors, Linear Algebra Appl., 439 (2013), 3264–3278. https://doi.org/10.1016/j.laa.2013.08.038 doi: 10.1016/j.laa.2013.08.038
[8]	W. Ding, Y. Wei, Solving multi-linear system with $\mathcal{M}$-tensors, J. Sci. Comput., 68 (2016), 689–715. https://doi.org/10.1007/s10915-015-0156-7 doi: 10.1007/s10915-015-0156-7
[9]	L. Han, A homotopy method for solving multilinear systems with $\mathcal{M}$-tensors, Appl. Math. Lett., 69 (2017), 49–54. https://doi.org/10.1016/j.aml.2017.01.019 doi: 10.1016/j.aml.2017.01.019
[10]	Z. J. Xie, X. Q. Jin, Y. M. Wei, Tensor methods for solving symmetric $\mathcal{M}$-tensor systems, J. Sci. Comput., 74 (2018), 412–425. https://doi.org/10.1007/s10915-017-0444-5 doi: 10.1007/s10915-017-0444-5
[11]	X. Z. Wang, M. L. Che, Y. M. Wei, Neural networks based approach solving multi-linear systems with $\mathcal{M}$-tensors, Neurocomputing, 351 (2019), 33–42. https://doi.org/10.1016/j.neucom.2019.03.025 doi: 10.1016/j.neucom.2019.03.025
[12]	H. He, C. Ling, L. Qi, G. Zhou, A globally and quadratically convergent algorithm for solving multi-linear systems with $\mathcal{M}$-tensors, J. Sci. Comput., 76 (2018), 1718–1741. https://doi.org/10.1007/s10915-018-0689-7 doi: 10.1007/s10915-018-0689-7
[13]	D. Liu, W. Li, S. W. Vong, The tensor splitting with application to solve multi-linear systems, J. Comput. Appl. Math., 330 (2018), 75–94. https://doi.org/10.1016/j.cam.2017.08.009 doi: 10.1016/j.cam.2017.08.009
[14]	W. Li, D. Liu, S. W. Vong, Comparison results for splitting iterations for solving multi-linear systems, Appl. Numer. Math., 134 (2018), 105–121. https://doi.org/10.1016/j.apnum.2018.07.009 doi: 10.1016/j.apnum.2018.07.009
[15]	L. B. Cui, M. H. Li, Y. S. Song, Preconditioned tensor splitting iterations method for solving multi-linear systems, Appl. Math. Lett., 96 (2019), 89–94. https://doi.org/10.1016/j.aml.2019.04.019 doi: 10.1016/j.aml.2019.04.019
[16]	Y. Zhang, Q. Liu, Z. Chen, Preconditioned Jacobi type method for solving multi-linear systems with $\mathcal{M}$-tensors, Appl. Math. Lett., 104 (2020), 106287. https://doi.org/10.1016/j.aml.2020.106287 doi: 10.1016/j.aml.2020.106287
[17]	D. Liu, W. Li, S. W. Vong, A new preconditioned SOR method for solving multi-linear systems with an $\mathcal{M}$-tensor, Calcolo, 57 (2020), 15. https://doi.org/10.1007/s10092-020-00364-8 doi: 10.1007/s10092-020-00364-8
[18]	Y. Chen, C. Li, A new preconditioned AOR method for solving multi-linear systems, Linear Multilinear Algebra, 72 (2024), 1385–1402. https://doi.org/10.1080/03081087.2023.2179586 doi: 10.1080/03081087.2023.2179586
[19]	L. B. Cui, X. Q. Zhang, S. L. Wu, A new preconditioner of the tensor splitting iterative method for solving multi-linear systems with $\mathcal{M}$-tensors, Comput. Appl. Math., 39 (2020), 173. https://doi.org/10.1007/s40314-020-01194-8 doi: 10.1007/s40314-020-01194-8
[20]	K. Xie, S. X. Miao, A new preconditioner for Gauss-Seidel method for solving multi-linear systems, Jpn. J. Ind. Appl. Math., 40 (2023), 1159–1173. https://doi.org/10.1007/s13160-023-00573-y doi: 10.1007/s13160-023-00573-y
[21]	M. Nobakht-Kooshkghazi, M. Najafi-Kalyani, Improving the Gauss-Seidel iterative method for solving multi-linear systems with $\mathcal{M}$-tensor, Jpn. J. Ind. Appl. Math., 41 (2024), 1061–1077. https://doi.org/10.1007/s13160-023-00637-z doi: 10.1007/s13160-023-00637-z
[22]	X. L. An, X. M. Lv, S. X. Miao, A new preconditioned Gauss-Seidel method for solving $\mathcal{M}$-tensor multi-linear system, Jpn. J. Ind. Appl. Math., 42 (2025), 245–258. https://doi.org/10.1007/s13160-024-00670-6 doi: 10.1007/s13160-024-00670-6
[23]	X. Wang, M. Che, Y. Wei, Preconditioned tensor splitting AOR iterative methods for $\mathcal{H}$-tensor equations, Numer Linear Algebra Appl., 27 (2020), e2329. https://doi.org/10.1002/nla.2329 doi: 10.1002/nla.2329
[24]	L. B. Cui, Y. D. Fan, Y. T. Zheng, A general preconditioner accelerated SOR-type iterative method for multi-linear systems with $\mathcal{Z}$-tensors, Comput. Appl. Math., 41 (2022), 26. https://doi.org/10.1007/s40314-021-01712-2 doi: 10.1007/s40314-021-01712-2
[25]	F. P. A. Beik, M. Najafi-Kalyani, K. Jbilou, Preconditioned iterative methods for multi-linear systems based on the majorization matrix, Linear Multilinear Algebra, 70 (2022), 5827–5846. https://doi.org/10.1080/03081087.2021.1931654 doi: 10.1080/03081087.2021.1931654
[26]	Z. Jiang, J. Li, A new preconditioned AOR-type method for $\mathcal{M}$-tensor equation, Appl. Numer. Math., 189 (2023), 39–52. https://doi.org/10.1016/j.apnum.2023.03.013 doi: 10.1016/j.apnum.2023.03.013
[27]	T. G. Kolda, B. W. Bader, Tensor decompositions and applications, SIAM Rev., 51 (2009), 455–500. https://doi.org/10.1137/07070111X doi: 10.1137/07070111X
[28]	K. C. Chang, K. Pearson, T. Zhang, Perron-Frobenius theorem for nonnegative tensors, Commun. Math. Sci., 6 (2008), 507–520.
[29]	W. H. Liu, W. Li, On the inverse of a tensor, Linear Algebra Appl., 495 (2016), 199–205. https://doi.org/10.1016/j.laa.2016.01.011 doi: 10.1016/j.laa.2016.01.011
[30]	M. Che, L. Qi, Y. Wei, Positive-definite tensors to nonlinear complementarity problems, J. Optim Theory Appl., 168 (2016), 475–487. https://doi.org/10.1007/s10957-015-0773-1 doi: 10.1007/s10957-015-0773-1
[31]	W. Ding, Z. Luo, L. Qi, $\mathcal{P}$-tensors, $\mathcal{P}_{0}$-tensors, and their applications, Linear Algebra Appl., 555 (2018), 336–354. https://doi.org/10.1016/j.laa.2018.06.028 doi: 10.1016/j.laa.2018.06.028
[32]	P. Azimzadeh, E. Bayraktar, High order bellman equations and weakly chained diagonally dominant tensors, SIAM J. Matrix Anal. Appl., 40 (2019), 276–298. https://doi.org/10.1137/18M1196923 doi: 10.1137/18M1196923
[33]	M. K. Ng, L. Qi, G. Zhou, Finding the largest eigenvalue of a nonnegative tensor, SIAM J. Matrix Anal. Appl., 31 (2010), 1090–1099. https://doi.org/10.1137/09074838X doi: 10.1137/09074838X
[34]	J. Y. Shao, A general product of tensors with applications, Linear Algebra Appl., 439 (2013), 2350–2366. https://doi.org/10.1016/j.laa.2013.07.010 doi: 10.1016/j.laa.2013.07.010
[35]	Y. N. Yang, Q. Z. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors, SIAM J. Matrix Anal. Appl., 31 (2010), 2517–2530. https://doi.org/10.1137/090778766 doi: 10.1137/090778766
[36]	A. E. Raftery, A model for high-order Markov chains, J. R. Stat. Soc. Ser. B, 47 (1985), 528–539. https://doi.org/10.1111/j.2517-6161.1985.tb01383.x doi: 10.1111/j.2517-6161.1985.tb01383.x
[37]	Z. Xu, Q. Lu, K. Y. Zhang, X. H. An, Theories and Applications of $H$-matrices, Science Press, 2013.

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)