Top

Journal of Scientific Computing

Published in:

08-03-2018

A Globally and Quadratically Convergent Algorithm for Solving Multilinear Systems with \({{\mathcal {M}}}\)-tensors

Authors: Hongjin He, Chen Ling, Liqun Qi, Guanglu Zhou

Published in: Journal of Scientific Computing | Issue 3/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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.

previous article A New Primal–Dual Algorithm for Minimizing the Sum of Three Functions with a Linear Operator

next article An Energy Stable Approach for Discretizing Hyperbolic Equations with Nonconforming Discontinuous Galerkin Methods

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

http://homepages.umflint.edu/~lxhan/software.html.

Bader, B.W., Kolda, T.G., et al.: MATLAB Tensor Toolbox Version 2.6. Available online (2015). http://www.sandia.gov/~tgkolda/TensorToolbox/

Benzi, M.: Preconditioning techniques for large linear systems: a survey. J. Comput. Phys. 182, 418–477 (2002)MathSciNetCrossRefMATH

Berman, A., Plemmons, R.: Nonnegative Matrices in the Mathematical Sciences. SIAM, Philadelphia (1994)CrossRefMATH

Brazell, M., Li, N., Navasca, C., Tamon, C.: Solving multilinear systems via tensor inversion. SIAM J. Matrix Anal. Appl. 34(2), 542–570 (2013)MathSciNetCrossRefMATH

Chang, K., Qi, L., Zhang, T.: A survey on the spectral theory of nonnegative tensors. Numer. Linear Algebra Appl. 20(6), 891–912 (2013)MathSciNetCrossRefMATH

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). https://doi.org/10.1002/nla.2125 MATH

Ding, W., Qi, L., Wei, Y.: M-tensor and nonsingular M-tensors. Linear Algebra Appl. 439, 3264–3278 (2013)MathSciNetCrossRefMATH

Ding, W., Wei, Y.: Solving multilinear systems with M-tensors. J. Sci. Comput. 68, 689–715 (2016)MathSciNetCrossRefMATH

Facchinei, F., Kanzow, C.: Beyond monotonicity in regularization methods for nonlinear complementarity problems. SIAM J. Control Optim. 37(4), 1150–1161 (1999)MathSciNetCrossRefMATH

10.

Facchinei, F., Pang, J.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)MATH

11.

Han, L.: A homotopy method for solving multilinear systems with M-tensors. Appl. Math. Lett. 69, 49–54 (2017)MathSciNetCrossRefMATH

12.

Kressner, D., Tobler, C.: Krylov subspace methods for linear systems with tensor product structure. SIAM J. Matrix Anal. Appl. 31(4), 1688–1714 (2010)MathSciNetCrossRefMATH

13.

Li, D., Xie, S., Xu, H.: Splitting methods for tensor equations. Numer. Linear Algebra Appl. (2017). https://doi.org/10.1002/nla.2102 MathSciNetMATH

14.

Li, X., Ng, M.: Solving sparse non-negative tensor equations: algorithms and applications. Front. Math. China 10, 649–680 (2015)MathSciNetCrossRefMATH

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)MathSciNetCrossRefMATH

16.

Qi, H.D.: A regularized smoothing Newton method for box constrained variational inequality problems with \(P_0\)-functions. SIAM J. Optim. 10(2), 315–330 (2000)MathSciNetCrossRef

17.

Qi, L.: Eigenvalues of a real supersymmetric tensor. J. Symbolic Comput. 40(6), 1302–1324 (2005)MathSciNetCrossRefMATH

18.

Qi, L., Luo, Z.: Tensor Analysis: Spectral Theory and Special Tensors. SIAM, Philadelphia (2017)CrossRefMATH

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), 1–35 (2000)MathSciNetCrossRefMATH

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)MathSciNetCrossRefMATH

22.

Xie, Z., Jin, X., Wei, Y.: Tensor methods for solving symmetric M-tensor systems. J. Sci. Comput. (2017). https://doi.org/10.1007/s10915-017-0444-5 MATH

23.

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

24.

Zwillinger, D.: Handbook of Differential Equations, 3rd edn. Academic Press Inc., Boston (1997)MATH

Title: A Globally and Quadratically Convergent Algorithm for Solving Multilinear Systems with -tensors
Authors: Hongjin He
Chen Ling
Liqun Qi
Guanglu Zhou
Publication date: 08-03-2018
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 3/2018
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-018-0689-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2018

Asymptotically Exact Posteriori Error Estimates for the Local Discontinuous Galerkin Method Applied to Nonlinear Convection–Diffusion Problems

Optimal Monotonicity-Preserving Perturbations of a Given Runge–Kutta Method

WSGD-OSC Scheme for Two-Dimensional Distributed Order Fractional Reaction–Diffusion Equation

A Hybridizable Discontinuous Galerkin Method for the Navier–Stokes Equations with Pointwise Divergence-Free Velocity Field

Discontinuous Galerkin Method with Staggered Hybridization for a Class of Nonlinear Stokes Equations

Monotone Mixed Finite Difference Scheme for Monge–Ampère Equation

Premium Partner