×

A globally and quadratically convergent algorithm for solving multilinear systems with \(\mathcal {M}\)-tensors. (English) Zbl 1397.65047

Summary: We consider multilinear systems of equations whose coefficient tensors are \({{\mathcal {M}}}\)-tensors. Multilinear systems of equations have many applications in engineering and scientific computing, such as data mining and numerical partial differential equations. In this paper, we show that solving multilinear systems with \({{\mathcal {M}}}\)-tensors is equivalent to solving nonlinear systems of equations where the involving functions are P-functions. Based on this result, we propose a Newton-type method to solve multilinear systems with \({{\mathcal {M}}}\)-tensors. For a multilinear system with a nonsingular \({{\mathcal {M}}}\)-tensor and a positive right side vector, we prove that the sequence generated by the proposed method converges to the unique solution of the multilinear system and the convergence rate is quadratic. Numerical results are reported to show that the proposed method is promising.

MSC:

65F10 Iterative numerical methods for linear systems
15A18 Eigenvalues, singular values, and eigenvectors
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bader, B.W., Kolda, T.G., et al.: MATLAB Tensor Toolbox Version 2.6. Available online (2015). http://www.sandia.gov/ tgkolda/TensorToolbox/
[2] Benzi, M, Preconditioning techniques for large linear systems: a survey, J. Comput. Phys., 182, 418-477, (2002) · Zbl 1015.65018 · doi:10.1006/jcph.2002.7176
[3] Berman, A., Plemmons, R.: Nonnegative Matrices in the Mathematical Sciences. SIAM, Philadelphia (1994) · Zbl 0815.15016 · doi:10.1137/1.9781611971262
[4] Brazell, M; Li, N; Navasca, C; Tamon, C, Solving multilinear systems via tensor inversion, SIAM J. Matrix Anal. Appl., 34, 542-570, (2013) · Zbl 1273.15028 · doi:10.1137/100804577
[5] Chang, K; Qi, L; Zhang, T, A survey on the spectral theory of nonnegative tensors, Numer. Linear Algebra Appl., 20, 891-912, (2013) · Zbl 1313.15015 · doi:10.1002/nla.1902
[6] Chen, H; Chen, Y; Li, G; Qi, L, A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test, Numer. Linear Algebra Appl., (2017) · Zbl 1438.65060 · doi:10.1002/nla.2125
[7] Ding, W; Qi, L; Wei, Y, M-tensor and nonsingular M-tensors, Linear Algebra Appl., 439, 3264-3278, (2013) · Zbl 1283.15074 · doi:10.1016/j.laa.2013.08.038
[8] Ding, W; Wei, Y, Solving multilinear systems with M-tensors, J. Sci. Comput., 68, 689-715, (2016) · Zbl 1371.65032 · doi:10.1007/s10915-015-0156-7
[9] Facchinei, F; Kanzow, C, Beyond monotonicity in regularization methods for nonlinear complementarity problems, SIAM J. Control Optim., 37, 1150-1161, (1999) · Zbl 0997.90085 · doi:10.1137/S0363012997322935
[10] Facchinei, F., Pang, J.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003) · Zbl 1062.90001
[11] Han, L, A homotopy method for solving multilinear systems with M-tensors, Appl. Math. Lett., 69, 49-54, (2017) · Zbl 1375.65060 · doi:10.1016/j.aml.2017.01.019
[12] Kressner, D; Tobler, C, Krylov subspace methods for linear systems with tensor product structure, SIAM J. Matrix Anal. Appl., 31, 1688-1714, (2010) · Zbl 1208.65044 · doi:10.1137/090756843
[13] Li, D; Xie, S; Xu, H, Splitting methods for tensor equations, Numer. Linear Algebra Appl., (2017) · Zbl 1463.65049 · doi:10.1002/nla.2102
[14] Li, X; Ng, M, Solving sparse non-negative tensor equations: algorithms and applications, Front. Math. China, 10, 649-680, (2015) · Zbl 1323.65027 · doi:10.1007/s11464-014-0377-3
[15] Matsuno, Y, Exact solutions for the nonlinear Klein-Gordon and Liouville equations in four-dimensional Euclidean space, J. Math. Phys., 28, 2317-2322, (1987) · Zbl 0663.35077 · doi:10.1063/1.527764
[16] Qi, HD, A regularized smoothing Newton method for box constrained variational inequality problems with \(P_0\)-functions, SIAM J. Optim., 10, 315-330, (2000) · Zbl 0955.90136 · doi:10.1137/S1052623497324047
[17] Qi, L, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40, 1302-1324, (2005) · Zbl 1125.15014 · doi:10.1016/j.jsc.2005.05.007
[18] Qi, L., Luo, Z.: Tensor Analysis: Spectral Theory and Special Tensors. SIAM, Philadelphia (2017) · Zbl 1370.15001 · doi:10.1137/1.9781611974751
[19] Qi, L; Sun, D; Zhou, G, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Math. Program., 87, 1-35, (2000) · Zbl 0989.90124 · doi:10.1007/s101079900127
[20] Tobler, C.: Low-rank tensor methods for linear systems and eigenvalue problems. Ph.D. Thesis, Eidgenssische Technische Hochschule ETH Zrich, No. 20320 (2012)
[21] Varga, R, On recurring theorems on diagonal dominance, Linear Algebra Appl., 13, 1-9, (1976) · Zbl 0336.15007 · doi:10.1016/0024-3795(76)90037-9
[22] Xie, Z; Jin, X; Wei, Y, Tensor methods for solving symmetric M-tensor systems, J. Sci. Comput., (2017) · Zbl 1392.65080 · doi:10.1007/s10915-017-0444-5
[23] Zhang, L; Qi, L; Zhou, G, \(M\)-tensors and some applications, SIAM J. Matrix Anal. Appl., 35, 437-452, (2014) · Zbl 1307.15034 · doi:10.1137/130915339
[24] Zwillinger, D.: Handbook of Differential Equations, 3rd edn. Academic Press Inc., Boston (1997) · Zbl 0678.34001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.