A Parallel Network Equilibration Algorithm for a Class of Constrained Matrix Problems

In this paper we propose a network equilibration algorithm for the solution of a class of constrained matrix problems with transportation-type constraints. The algorithm decomposes the problem into two series of supply and demand network equilibrium problems with special structure which can then be solved exactly and in parallel. The theoretical results obtained include the proof of convergence, the rate of convergence, and computational complexity analysis, and are obtained by interpreting the algorithm as a dual method. Computational results on datasets illustrate the theory and the efficiency of this approach.