New preconditioned Gauss-Seidel type methods for solving multi-linear systems with M-tensors

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

Abstract

In this paper, we propose a new preconditioner for the multi-linear systems with 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 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).

Keywords

multi-linear systems with M-tensors / preconditioning / tensor splitting / preconditioned Gauss-Seidel type method / convergence theorems / comparison theorems

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

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

[2] H. R. Xu, D. H. Li, S. L. Xie, An equivalent tensor equation to the tensor complementarity problem with positive semi-definite Z-tensor, Optim. Lett., 13 (2019), 685-694. https://doi.org/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

[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

[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

[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

[7] W. Ding, L. Qi, Y. Wei, M-tensors and nonsingular M-tensors, Linear Algebra Appl., 439 (2013), 3264-3278. https://doi.org/10.1016/j.laa.2013.08.038

[8] W. Ding, Y. Wei, Solving multi-linear system with M-tensors, J. Sci. Comput., 68 (2016), 689-715. https://doi.org/10.1007/s10915-015-0156-7

[9] L. Han, A homotopy method for solving multilinear systems with M-tensors, Appl. Math. Lett., 69 (2017), 49-54. https://doi.org/10.1016/j.aml.2017.01.019

[10] Z. J. Xie, X. Q. Jin, Y. M. Wei, Tensor methods for solving symmetric M-tensor systems, J. Sci. Comput., 74 (2018), 412-425. https://doi.org/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 M-tensors, Neurocomputing, 351 (2019), 33-42. https://doi.org/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 M-tensors, J. Sci. Comput., 76 (2018), 1718-1741. https://doi.org/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

[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

[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

[16] Y. Zhang, Q. Liu, Z. Chen, Preconditioned Jacobi type method for solving multi-linear systems with M-tensors, Appl. Math. Lett., 104 (2020), 106287. https://doi.org/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 M-tensor, Calcolo, 57 (2020), 15. https://doi.org/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

[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 M-tensors, Comput. Appl. Math., 39 (2020), 173. https://doi.org/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

[21] M. Nobakht-Kooshkghazi, M. Najafi-Kalyani, Improving the Gauss-Seidel iterative method for solving multi-linear systems with M-tensor, Jpn. J. Ind. Appl. Math., 41 (2024), 1061-1077. https://doi.org/10.1007/s13160-023-00637-z

[22] X. L. An, X. M. Lv, S. X. Miao, A new preconditioned Gauss-Seidel method for solving M-tensor multi-linear system, Jpn. J. Ind. Appl. Math., 42 (2025), 245-258. https://doi.org/10.1007/s13160-024-00670-6

[23] X. Wang, M. Che, Y. Wei, Preconditioned tensor splitting AOR iterative methods for H-tensor equations, Numer Linear Algebra Appl., 27 (2020), e2329. https://doi.org/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 Z-tensors, Comput. Appl. Math., 41 (2022), 26. https://doi.org/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

[26] Z. Jiang, J. Li, A new preconditioned AOR-type method for M-tensor equation, Appl. Numer. Math., 189 (2023), 39-52. https://doi.org/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

[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

[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

[31] W. Ding, Z. Luo, L. Qi, P-tensors, P₀-tensors, and their applications , Linear Algebra Appl., 555 (2018), 336-354. https://doi.org/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

[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

[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

[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

[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

[37] Z. Xu, Q. Lu, K. Y. Zhang, X. H. An, Theories and Applications of H-matrices , Science Press, 2013.