×

Asynchronous parallel successive overrelaxation for the symmetric linear complementarity problem. (English) Zbl 0665.90090

Convergence is established for asynchronous parallel successive overrelaxation (SOR) algorithms for the symmetric linear complementarity problem. For the case of a strictly diagonally dominant matrix convergence is achieved for a relaxation factor interval of (0,2] with line search, and (0,1] without line search. Computational tests on the Sequent Symmetry S81 multiprocessor give speedup efficiency in the 43 %- 91 % range for the cases for which convergence is established. The tests also show superiority of the asynchronous SOR algorithms over their synchronous counterparts.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C05 Linear programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B.H. Ahn, ”Solution of nonsymmetric linear complementarity problems by iterative methods,”Journal of Optimization Theory and Applications 33 (1981) 175–185. · Zbl 0422.90079
[2] G.M. Baudet, ”Asynchronous iterative methods for multiprocessors,”Journal of the Association for Computing Machinery 25 (1978) 226–244. · Zbl 0372.68015
[3] R. De Leone and O.L. Mangasarian, ”Serial and parallel solution of large scale linear programs by augmented Lagrangian successive overrelaxation,” in: A. Kurzhanski, K. Neumann and D. Pallaschke, eds.,Optimization, Parallel Processing and Applications, Lecture Notes in Economics and Mathematical Systems 304 (Springer-Verlag, Berlin, 1988) pp. 103–124. · Zbl 0648.90051
[4] D. DeWitt, R. Finkel and M. Solomon, ”The CRYSTAL multicomputer: Design and implementation experience,”IEEE Transactions on Software Engineering 13 (1987) 953–966. · Zbl 05341896
[5] O.L. Mangasarian, ”Solution of symmetric linear complementarity problem by iterative methods,”Journal of Optimization Theory and Applications 22 (1977) 465–485. · Zbl 0341.65049
[6] O.L. Mangasarian, ”Sparsity-preserving SOR algorithms for separable quadratic and linear programming,”Computer and Operations Research 11 (1984) 105–112. · Zbl 0606.90102
[7] O.L. Mangasarian and R. De Leone, ”Parallel successive overrelaxation methods for symmetric linear complementarity problems and linear programs,”Journal of Optimization Theory and Applications 54 (1987) 437–446. · Zbl 0595.90090
[8] O.L. Mangasarian and R. De Leone, ”Parallel gradient projection successive overrelaxation for symmetric linear complementarity problems and linear programs,” UW Computer Sciences Technical Report #659, August 1986, to appear inAnnals of Operations Research (1988). · Zbl 0739.90068
[9] J.-S. Pang: ”On the convergence of a basic iterative method for the implicit complementarity problem,”Journal of Optimization Theory and Applications 37 (1982) 149–162. · Zbl 0482.90084
[10] Sequent Computer Systems, Inc., ”Symmetry technical summary,” Beaverton, Oregon 97006 (1987).
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.