ORIGINAL PAPERS

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

  • Dongdong Liu ,
  • Ting Hu ,
  • Xifu Liu
Expand
  • 1. School of Mathematics and Statistics, Guangdong University of Technology, Guangzhou, 510520, Guangdong, China;
    2. School of Mathematical Sciences, Chongqing Normal University, Chongqing, 401331, China

Received date: 2023-11-13

  Revised date: 2024-06-07

  Accepted date: 2024-06-11

  Online published: 2024-10-25

Supported by

D. Liu was supported in part by the National Natural Science Foundation of China (No. 12101136), the Guangdong Basic and Applied Basic Research Foundations (No. 2023A1515011633), the Project of Science and Technology of Guangzhou (No. 2024A04J2056), the Opening Project of Guangdong Province Key Laboratory of Computational Science at the Sun Yat-sen University (No. 2021004), the Open Project of Key Laboratory, School of Mathematical Sciences, Chongqing Normal University (No. CSSXKFKTQ202002). X. Liu was funded by the Science and Technology Research Program of Chongqing Municipal Education Commission (Grant No. KJQN202100505), the Natural Science Foundation Project of Chongqing of China (Grant No. cstc2021jcyj-msxmX0195), and the Program of Chongqing Innovation Research Group Project in University (Grant No. CXQT19018).

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.

Cite this article

Dongdong Liu , Ting Hu , Xifu Liu . Restarted Nonnegativity Preserving Tensor Splitting Methods via Relaxed Anderson Acceleration for Solving Multilinear Systems[J]. Communications on Applied Mathematics and Computation, 2025 , 7(5) : 2061 -2079 . DOI: 10.1007/s42967-024-00439-1

References

[1] Azimzadeh, P., Bayraktar, E.: High order Bellman equations and weakly chained diagonally dominant tensors. SIAM J. Matrix Anal. Appl. 40(1), 276-298 (2019)
[2] Bai, X., He, H., Ling, C., Zhou, G.: A nonnegativity preserving algorithm for multilinear systems with nonsingular \begin{document}$ {\cal{M} } $\end{document}-tensors. Numer. Algorithms 87(3), 1301-1320 (2021)
[3] Chen, Y., Li, C.: A new preconditioned AOR method for solving multi-linear systems. Linear Multilinear Algebra 72(9), 1385-1402 (2024)
[4] Cui, L., Li, M., Song, Y.: Preconditioned tensor splitting iterations method for solving multi-linear systems. Appl. Math. Lett. 96, 89-94 (2019)
[5] Ding, W., Qi, L., Wei, Y.: \begin{document}$ {\cal{M} } $\end{document}-tensors and nonsingular \begin{document}$ {\cal{M} } $\end{document}-tensors. Linear Algebra Appl. 439, 3264-3278 (2013)
[6] Ding, W., Wei, Y.: Solving multi-linear system with \begin{document}$ {\cal{M} } $\end{document}-tensors. J. Sci. Comput. 68(2), 689-715 (2016)
[7] Han, L.: A homotopy method for solving multilinear systems with \begin{document}$ {\cal{M} } $\end{document}-tensors. Appl. Math. Lett. 69, 49-54 (2017)
[8] He, H., Ling, C., Qi, L., Zhou, G.: A globally and quadratically convergent algorithm for solving multilinear systems with \begin{document}$ {\cal{M} } $\end{document}-tensors. J. Sci. Comput. 76(3), 1718-1741 (2018)
[9] Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51, 455-500 (2009)
[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] Li, D., Guan, H.B., Wang, X.Z.: Finding a nonnegative solution to an \begin{document}$ {\cal{M} } $\end{document}-tensor equation. Pac. J. Optim. 16(3), 419-440 (2020)
[12] Li, D., Xie, S., Xu, H.: Splitting methods for tensor equations. Numer. Linear Algebra Appl. 24(5), e2102 (2017)
[13] Li, D., Xu, J., Guan, H.: Newton’s method for \begin{document}$ {\cal{M} } $\end{document}-tensor equations. J. Optim. Theory Appl. 190(2), 628-649 (2021)
[14] Li, W., Liu, D., Vong, S.W.: Comparison results for splitting iterations for solving multi-linear systems. Appl. Numer. Math. 134, 105-121 (2018)
[15] Liang, M., Zheng, B., Zhao, R.: Alternating iterative methods for solving tensor equations with applications. Numer. Algorithms 80(4), 1437-1465 (2019)
[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] Liu, D., Li, W., Vong, S.W.: The tensor splitting with application to solve multi-linear systems. J. Comput. Appl. Math. 330, 75-94 (2018)
[18] Liu, D., Li, W., Vong, S.W.: A new preconditioned SOR method for solving multi-linear systems with an \begin{document}$ {\cal{M} } $\end{document}-tensor. Calcolo 57(2), 1-18 (2020)
[19] Liu, L., Li, X., Liu, S.: Further study on existence and uniqueness of positive solution for tensor equations. Appl. Math. Lett. 124, 107686 (2022)
[20] Lyu, C., Ma, C.: A Levenberg-Marquardt method for solving semi-symmetric tensor equations. J. Comput. Appl. Math. 332, 13-25 (2018)
[21] Ni, Q., Qi, L.: A quadratically convergent algorithm for finding the largest eigenvalue of a nonnegative homogeneous polynomial map. J. Glob. Optim. 61(4), 627-641 (2015)
[22] Niu, J., Du, L., Sogabe, T., Zhang, S.: A tensor alternating Anderson-Richardson method for solving multilinear systems with \begin{document}$ {\cal{M}} $\end{document}-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] Qi, L.: Eigenvalues of a real supersymmetric tensor. J. Symb. Comput. 40, 1302-1324 (2005)
[25] Qi, L., Luo, Z.: Tensor Analysis: Spectral Theory and Special Tensors. Society for Industrial and Applied Mathematics (2017)
[26] Toth, A., Kelley, C.T.: Convergence analysis for Anderson acceleration. SIAM J. Numer. Anal. 53(2), 805-819 (2015)
[27] Walker, H.F., Ni, P.: Anderson acceleration for fixed-point iterations. SIAM J. Numer. Anal. 49(4), 1715-1735 (2011)
[28] Wang, X., Che, M., Wei, Y.: Neural networks based approach solving multi-linear systems with \begin{document}$ {\cal{M} } $\end{document}-tensors. Neurocomputing 351, 33-42 (2019)
[29] Wang, X., Mo, C., Che, M., Wei, Y.: Accelerated dynamical approaches for finding the unique positive solution of \begin{document}$ {\cal{K}} {\cal{S}} $\end{document}-tensor equations. Numer. Algorithms 88(4), 1787-1810 (2021)
[30] Xie, Z., Jin, X., Wei, Y.: Tensor methods for solving symmetric \begin{document}$ {\cal{M} } $\end{document}-tensor systems. J. Sci. Comput. 74(1), 412-425 (2018)
[31] Zhang, L., Qi, L., Zhou, G.: \begin{document}$ {\cal{M} } $\end{document}-tensors and some applications. SIAM J. Matrix Anal. Appl. 35, 437-452 (2014)
[32] Zhang, Y., Liu, Q., Chen, Z.: Preconditioned Jacobi type method for solving multi-linear systems with \begin{document}$ {\cal{M} } $\end{document}-tensors. Appl. Math. Lett. 104, 106287 (2020)
Options
Outlines

/