Parallel gradient projection successive overrelaxation for symmetric linear complementarity problems and linear programs |
| |
Authors: | O L Mangasarian R De Leone |
| |
Institution: | (1) Computer Sciences Department, University of Wisconsin, 53706 Madison, WI, USA |
| |
Abstract: | A gradient projection successive overrelaxation (GP-SOR) algorithm is proposed for the solution of symmetric linear complementary problems and linear programs. A key distinguishing feature of this algorithm is that when appropriately parallelized, the relaxation factor interval (0, 2) isnot reduced. In a previously proposed parallel SOR scheme, the substantially reduced relaxation interval mandated by the coupling terms of the problem often led to slow convergence. The proposed parallel algorithm solves a general linear program by finding its least 2-norm solution. Efficiency of the algorithm is in the 50 to 100 percent range as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-86-0255. |
| |
Keywords: | Parallel algorithms SOR gradient projection linear programming linear complementarity problem |
本文献已被 SpringerLink 等数据库收录! |