Dual-Simultaneous Scaling Algorithm for Large-Scale Origin-Destination Matrix Balancing: Mathematical Foundations, Vectorization, and Cross-Disciplinary Applications

Source abstract

Doubly constrained matrix balancing—the process of scaling a non-negative base matrix to satisfy strict row and column sum constraints—is a foundational problem in urban transportation planning, input-output economics, survey statistics, and optimal transport. Classical algorithms such as the Fratar method and Furness / Iterative Proportional Fitting (IPF) operate via sequential or location-factor-based adjustments, which exhibit significant computational overhead and memory bandwidth bottlenecks when scaled to large-scale matrices (N ≥ 1000). In this paper, we propose and rigorously formalize the Dual-Simultaneous Scaling (DSS) Algorithm, a vectorized, single-pass matrix balancing technique that updates row and column scale factors simultaneously using a dynamic global normalization invariant. We provide a rigorous mathematical proof demonstrating that the proposed operator minimizes Kullback-Leibler relative entropy subject to marginal constraints, and prove unique fixed-point convergence under Karush-Kuhn-Tucker (KKT) optimality conditions. Extensive computational benchmarks on synthetic and real-world matrices ranging from N = 3 x 3 to N = 3000 x 3000 (9 million cells) demonstrate that the proposed method achieves a 2x to 680x+ speedup in execution time and a drastic reduction in iteration counts compared to classical Fratar and Furness implementations. Furthermore, we prove that the DSS operator is domain-agnostic, extending its mathematical applicability to input-output economic RAS modeling, demographic raking, and Sinkhorn optimal transport distance estimation.