DATA-PARALLEL QUADRATIC-PROGRAMMING ON BOX-CONSTRAINED PROBLEMS

We develop designs for the data parallel solution of quadratic program ming problems subject to box constraints. In particular, we consider t he class of algorithms that iterate between projection steps that iden tify candidate active sets and conjugate gradient steps that explore t he working space. Using the algorithm of More and Toraldo [Report MCS- p77-05 89, Argonne National Laboratory, Illinois, 1989] as a specific instance of this class of algorithms we show how its components can be implemented efficiently on a data-parallel SIMD computer architecture . Alternative designs are developed for both arbitrary, unstructured H essian matrices and for structured problems. Implementations are carri ed out on a Connection Machine CM-2. They are shown to be very efficie nt, achieving a peak computing rate over 2 Chops. Problems with severa l hundred thousand variables are solved within one minute of solution time on the 8K CM-2. Extremely large test problems, with up to 2.89 mi llion variables, are also solved efficiently. The data parallel implem entation outperforms a benchmark implementation of interior point algo rithms on an IBM 3090-6009 vector supercomputer and a successive overr elaxation algorithm on an Intel iPSC/860 hypercube.