A parallel algorithm for solving the Linear Complementarity Problem

The concept of multitasking mathematical programs is discussed, and an application of multitasking to the multiple-cost-row Linear programming problem is considered. Based on this, an algorithm for solving the linear Complementarity Problem (LCP) in parallel is presented. A variety of computational results are presented using this multitasking approach on the CRAY X-MP/48. These results were obtained for randomly generated LCP’s where the n×n dense matrix M has no special properties (hence, the problem is NP-hard), based on these results, an average time performance of O(n⁴) is observed.