Matrix Balancing on a Massively Parallel Connection Machine

Abstract

Matrix balancing models find applications in economics, transportation, regional sciences, statistics, stochastic modeling and other areas. The iterative scaling algorithm RAS that is used for the solution of these problems is shown here to be suitable for data level parallelism on the Connection Machine (CM). We develop synchronous and asynchronous parallel versions of RAS and discuss designs for implementation of both dense and sparse problems on the CM. We report numerical experiences with matrices of dimension up to 1000 × 1000 and 990000 nonzero entries. Problems of this size are solved within seconds on a Connection Machine model CM-2 with 32K processing elements, and the algorithm achieves peak rate of computing in excess of 300μFLOPS.INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.