Abstract
For the large sparse linear complementarity problem, a class of accelerated modulus-based matrix splitting iteration methods is established by reformulating it as a general implicit fixed-point equation, which covers the known modulus-based matrix splitting iteration methods. The convergence conditions are presented when the system matrix is either a positive definite matrix or an H +-matrix. Numerical experiments further show that the proposed methods are efficient and accelerate the convergence performance of the modulus-based matrix splitting iteration methods with less iteration steps and CPU time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahn, B.H.: Solutions of nonsymmetric linear complementarity problems by iterative methods. J. Optim. Theory Appl. 33, 175–185 (1981)
Bai, Z.-Z.: The convergence of parallel iteration algorithms for linear complementarity problems. Comput. Math. Appl. 32, 1–17 (1996)
Bai, Z.-Z.: On the convergence of the multisplitting methods for the linear complementarity problem. SIAM J. Matrix Anal. Appl. 21, 67–78 (1999)
Bai, Z.-Z.: Experimental study of the asynchronous multisplitting relaxation methods for linear complementarity problems. J. Comput. Math. 20, 561–574 (2002)
Bai, Z.-Z.: Modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 6, 917–933 (2010)
Bai, Z.-Z., Evans, D.J.: Matrix multisplitting relaxation methods for linear complementarity problems. Int. J. Comput. Math. 63, 309–326 (1997)
Bai, Z.-Z., Evans, D.J.: Matrix multisplitting methods with applications to linear complementarity problems: parallel synchronous and chaotic methods. Réseaux et Systèmes Répartis: Calculateurs Parallelès 13, 125–154 (2001)
Bai, Z.-Z., Evans, D.J.: Matrix multisplitting methods with applications to linear complementarity problems: parallel asynchronous methods. Int. J. Comput. Math. 79, 205–232 (2002)
Bai, Z.-Z., Huang, Y.-G.: A class of asynchronous parallel multisplitting relaxation methods for large sparse linear complementarity problem. J. Comput. Math. 21, 773–790 (2003)
Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences. Academic, New York (1979)
Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic, SanDiego (1992)
Cryer, C.W.: The solution of a quadratic programming using systematic overrelaxation. SIAM J. Control 9, 385–392 (1971)
Dong, J.-L., Jiang, M.-Q.: A modified modulus method for symmetric positive-definite linear complementarity problems. Numer. Linear Algebra Appl. 16, 129–143 (2009)
Frommer, A., Mayer, G.: Convergence of relaxed parallel multisplitting methods. Linear Algebra Appl. 119, 141–152 (1989)
Frommer, A., Szyld, D.B.: H-splittings and two-stage iterative methods. Numer. Math. 63, 345–356 (1992)
Hadjidimos, A., Tzoumas, M.: Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem. Linear Algebra Appl. 431, 197–210 (2009)
Hadjidimos, A., Lapidakis, M., Tzoumas, M.: On iterative solution for linear complementarity problem with an H +-matrix. SIAM J. Matrix Anal. Appl. 33, 97–110 (2011)
Kappel, N.W., Watson, L.T.: Iterative algorithms for the linear complementarity problems. Int. J. Comput. Math 19, 273–297 (1986)
Mangasarian, O.L.: Solutions of symmetric linear complementarity problems by iterative methods. J. Optim. Theory Appl. 22, 465–485 (1977)
Murty, K.G.: Linear Complementarity, Linear and Nonlinear Programming. Heldermann, Berlin (1988)
Pang, J.-S.: Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem. J. Optim. Theory Appl. 42, 1–17 (1984)
Schäfer, U.: A linear complementarity problem with a P-matrix. SIAM Rev. 46, 189–201 (2004)
van Bokhoven, W.M.G.: A Class of Linear Complementarity Problems is Solvable in Polynomial Time. Unpublished Paper, Dept. of Electrical Engineering, University of Technology, The Netherlands (1980)
Varga, R.S.: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs (1962)
Zhang, L.-L.: Two-step modulus based matrix splitting iteration for linear complementarity problems. Numer. Algorithms 57, 83–99 (2011)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by the National Natural Science Foundation of China (No. 11271289 and No. U1135003).
Rights and permissions
About this article
Cite this article
Zheng, N., Yin, JF. Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem. Numer Algor 64, 245–262 (2013). https://doi.org/10.1007/s11075-012-9664-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-012-9664-9