×

Matrix multisplitting methods with applications to linear complementarity problems: Parallel asynchronous methods. (English) Zbl 1011.65033

Summary: We consider parallel matrix multisplitting methods for solving linear complementarity problem that finds a real vector \(z\in\mathbb{R}^n\) such that \(Mz+ q\geq 0\), \(z\geq 0\) and \(z^T(Mz+ q)= 0\), where \(M\in\mathbb{R}^{n\times n}\) is a given real matrix and \(q\in\mathbb{R}^n\) a given real vector. The recently developed parallel asynchronous multisplitting iterative methods based on fixed-point transformation of the problem, explicit projection of the system and implicit splittings of the matrix are reviewed; their asymptotic convergence properties for some typical matrix class are discussed; and their internal relationships are studied. Therefore, systematic algorithmic models in the sense of multisplitting and reliable theoretical guarantees in the sense of asymptotic convergence are presented for solving the large sparse linear complementarity problems on modern high-speed multiprocessor systems.
This paper is a continuity of the recent work of Z. Z. Bai and D. J. Evans [Matrix multisplitting methods with applications to linear complementarity problems: Parallel synchronous and chaotic methods, Calculateurs Parralelès 13, No. 1, 125-154 (2001)], which includes the parallel synchronous and chaotic matrix multisplitting iterative methods and their convergence theories.

MSC:

65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahn B. H., Journal of Optimization Theory and Applications 33 (9) pp 175– (1981) · Zbl 0422.90079
[2] Bai Z. Z., Parallel Iterative Methods for Large-sparse Systems of Algebraic Equations (1993)
[3] Bai Z. Z., Chinese Journal of Engineering Mathematics 10 (2) pp 107– (1993)
[4] Bai Z. Z., Natural Science Journal of Heilongjiang University 10 pp 1– (1993)
[5] Bai Z. Z., Chinese Journal of Engineering Mathematics 11 (1) pp 99– (1994)
[6] Bai Z. Z., Applied Mathematics, A Journal of Chinese Universities 10 pp 133– (1995) · Zbl 0837.15015
[7] Bai Z. Z., Computers and Mathematics with Applications 32 (9) pp 1– (1996) · Zbl 0873.65061
[8] Bai Z. Z., Numerical Mathematics, A Journal of Chinese Universities (English Series. 5 (2) pp 228– (1996)
[9] Bai Z. Z., Numerical Algorithms 14 pp 295– (1997) · Zbl 0889.65055
[10] Bai Z. Z., Numerical Algorithms 15 pp 347– (1997) · Zbl 0892.65029
[11] Bai Z. Z., IMA Journal of Numerical Analysis 18 pp 509– (1998) · Zbl 0914.65072
[12] Bai Z. Z., Applied Mathematics, A Journal of Chinese Universities 13 pp 188– (1998) · Zbl 0910.65049
[13] Bai Z. Z., Journal of Computational Mathematics
[14] Bai Z. Z., SIAM Journal on Matrix Analysis and Applications 21 pp 67– (1999) · Zbl 0942.65059
[15] Bai Z. Z., International Journal of Computer Mathematics 63 pp 309– (1997) · Zbl 0876.90086
[16] Bai Z. Z., Journal of Computational and Applied Mathematics 96 pp 127– (1998) · Zbl 0927.65079
[17] Bai Z. Z., International Journal of Computer Mathematics 70 pp 519– (1999) · Zbl 0921.65046
[18] Bai Z. Z., Calculateurs Paralleles 13 (1) pp 125– (2001)
[19] Bai Z. Z., Parallel Algorithms and Applications 11 pp 113– (1997) · Zbl 0880.65041
[20] Bai Z. Z., Journal of Computational and Applied Mathematics 93 (1) pp 13– (1998) · Zbl 0941.65046
[21] Bai Z. Z., Journal of Computational Mathematics
[22] Bai Z. Z., A class of asynchronous parallel multisplitting relaxation methods for the large sparse linear complementarity problems (1999)
[23] Bai Z. Z., Computers and Mathematics with Applications 32 (12) pp 51– (1996) · Zbl 0870.65025
[24] Bai Z. Z., Numerical Mathematics, A Journal of Chinese Universities (English Series 2 (1) pp 87– (1993)
[25] Bai Z. Z., Mathematica Applicata 9 (1) pp 121– (1996)
[26] Bai Z. Z., Parallel Computing 21 pp 565– (1995) · Zbl 0875.68567
[27] Bai Z. Z., Journal of Computational Mathematics 16 (3) pp 221– (1998)
[28] Bai Z. Z., Journal of Fudan University (Natural Science 36 (2) pp 206– (1997)
[29] Benassi M., SIAM Journal on Numerical Analysis 31 pp 813– (1994) · Zbl 0810.65063
[30] Bru R., Linear Algebra and Its Applications 103 pp 175– (1988) · Zbl 0645.65018
[31] Cottle R. W., Linear Algebra and Its Applications 1 pp 103– (1968) · Zbl 0155.28403
[32] Cottle R. W., Applied Mathematics and Optimization 13 pp 1– (1985) · Zbl 0575.65119
[33] Cottle R. W., The Linear Complementarity Problem (1992)
[34] Cottle R. W., Applied Mathematics and Optimization 4 pp 321– (1977) · Zbl 0391.90087
[35] De Leone R., Mathematical Programming 42 pp 347– (1988) · Zbl 0665.90090
[36] Elsner L., Numerische Mathematik 56 pp 283– (1989) · Zbl 0673.65018
[37] Frommer A., Linear Algebra and Its Applications 119 pp 141– (1989) · Zbl 0676.65022
[38] Hadjidimos A., Mathematics of Computation 32 pp 149– (1978) · Zbl 0412.65046
[39] Iusem A. N., Mathematical Programming 19 pp 33– (1993) · Zbl 0790.90069
[40] Luo Z. Q., SIAM Journal on Control and Optimization 29 pp 1037– (1991) · Zbl 0734.90101
[41] Machida N., Journal of Computational and Applied Mathematics 62 pp 217– (1995) · Zbl 0853.65068
[42] Mangasarian O. L., Journal of Optimization Theory and Applications 22 pp 465– (1977) · Zbl 0341.65049
[43] Mangasarian O. L., Journal of Optimization Theory and Applications 54 pp 437– (1987) · Zbl 0595.90090
[44] Murty K. G., Linear Complementarity, Linear and Nonlinear Programming (1988)
[45] Neumann M., Linear Algebra and Its Applications 88 pp 559– (1987) · Zbl 0626.65025
[46] O’Leary D. P., SIAM Journal on Algebraic and Discrete Methods 6 pp 630– (1985) · Zbl 0582.65018
[47] Pang J. S., Journal of Optimization Theory and Applications 37 pp 149– (1982) · Zbl 0482.90084
[48] Pang J. S., Journal of Optimization Theory and Applications 42 pp 1– (1984) · Zbl 0506.90082
[49] Pang J. S., Mathematical Programming 58 pp 149– (1993) · Zbl 0784.90089
[50] Parsons T. D., Applications of principal pivoting. In: Proceedings of the Princeton Symposium on Mathematical Programming (1970) · Zbl 0275.15012
[51] Varga R. S., Matrix Iterative Analysis (1962) · Zbl 0133.08602
[52] Wang D. R., Linear Algebra and Its Applications 154 pp 473– (1991)
[53] Wang D. R., Parallel Algorithms and Applications 2 pp 173– (1994) · Zbl 1049.68936
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.