A Comparative Study of Algorithms for Matrix Balancing

Five applications of matrix balancing are described and the algorithmic and computational performance of balancing procedures that represent the two primary approaches for matrix balancing-matrix scaling and nonlinear optimization are compared.

Abstract

The problem of adjusting the entries of a large matrix to satisfy prior consistency requirements occurs in economics, urban planning, statistics, demography, and stochastic modeling; these problems are called Matrix Balancing Problems. We describe five applications of matrix balancing and compare the algorithmic and computational performance of balancing procedures that represent the two primary approaches for matrix balancing—matrix scaling and nonlinear optimization. The algorithms we study are the RAS algorithm, a diagonal similarity scaling algorithm, and a truncated Newton algorithm for network optimization. We present results from computational experiments with large-scale problems based on producing consistent estimates of Social Accounting Matrices for developing countries.