Serial and Parallel Equilibration of Large-Scale Constrained Matrix Problems With Application To the Social and Economic Sciences

Abstract

We have considered the computation of large-scale con strained matrix problems, which arise in numerous ap plications in the social and economic sciences—in par ticular, the general quadratic problem that permits alter native weighting mechanisms on the data and includes the much-studied diagonal problem. The procedure uti lized is row equilibration, column equilibration (RC), which exploits the bipartite network structure of the problem by decomposing it into simpler subproblems that can be solved exactly and in parallel. We compared the efficiency of the RC algorithm to that of a well- known algorithm and established that RC was faster. We used serial RC as a benchmark for our parallel experi mentation and investigated its absolute efficiency on economic data sets and on very large quadratic diagonal problems. We implemented the RC algorithm using Par allel Fortran Prototype on the IBM 3090-600E. The results demonstrate that a constrained matrix problem with as many as a million variables can be solved using RC in minutes of CPU time in a serial environment. Speedups with the parallelized RC algorithm were substantial for the diagonal problems and moderate for the general problems. These computational results broaden the po tential domain of constrained matrix applications.