An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing

Edward Chlebus; Viswatej Kasapu

doi:10.5802/crmath.398

Algebra, Control theory

An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing

Edward Chlebus ¹ ; Viswatej Kasapu ¹

¹ Department of Computer Science, Illinois Institute of Technology, 10 W. 31st St., Chicago, Illinois 60616, USA

Comptes Rendus. Mathématique, Volume 361 (2023), pp. 737-746.

Abstract

We have developed a new simple iterative algorithm to determine entries of a normalized matrix given its marginal probabilities. Our method has been successfully used to obtain two different solutions by maximizing the entropy of a desired matrix and by minimizing its Kullback–Leibler divergence from the initial probability distribution. The latter is fully equivalent to the well-known RAS balancing algorithm. The presented method has been evaluated using a traffic matrix of the GÉANT pan-European network and randomly generated matrices of various sparsities. It turns out to be computationally faster than RAS. We have shown that our approach is suitable for efficient balancing both dense and sparse matrices.

Received: 2021-09-28
Revised: 2022-02-03
Accepted: 2022-06-12
Published online: 2023-05-11

DOI: 10.5802/crmath.398

Classification: 65F35, 65F50, 65K05, 90B20, 94A17

Author's affiliations:

Edward Chlebus ¹; Viswatej Kasapu ¹

¹ Department of Computer Science, Illinois Institute of Technology, 10 W. 31st St., Chicago, Illinois 60616, USA

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{CRMATH_2023__361_G4_737_0,
     author = {Edward Chlebus and Viswatej Kasapu},
     title = {An {Entropy} {Optimizing} {RAS-Equivalent} {Algorithm} for {Iterative} {Matrix} {Balancing}},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {737--746},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {361},
     year = {2023},
     doi = {10.5802/crmath.398},
     language = {en},
}

TY  - JOUR
AU  - Edward Chlebus
AU  - Viswatej Kasapu
TI  - An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing
JO  - Comptes Rendus. Mathématique
PY  - 2023
SP  - 737
EP  - 746
VL  - 361
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.398
LA  - en
ID  - CRMATH_2023__361_G4_737_0
ER  -

%0 Journal Article
%A Edward Chlebus
%A Viswatej Kasapu
%T An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing
%J Comptes Rendus. Mathématique
%D 2023
%P 737-746
%V 361
%I Académie des sciences, Paris
%R 10.5802/crmath.398
%G en
%F CRMATH_2023__361_G4_737_0

Edward Chlebus; Viswatej Kasapu. An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing. Comptes Rendus. Mathématique, Volume 361 (2023), pp. 737-746. doi : 10.5802/crmath.398. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.398/

References
Cited by

[1] Zeyuan Allen-Zhu; Yuanzhi Li; Rafael Oliveira; Avi Wigderson Much faster algorithms for matrix scaling, Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), (Berkeley, CA), Oct. 15-17 (2017), pp. 890-901 | DOI

[2] Michael Bacharach Biproportional Matrices and Input-Output Change, University of Cambridge, Department of Applied Economics Monographs, Cambridge University Press, 1970 no. 16 | MR | Zbl

[3] David F. Batten Spatial Analysis of Interacting Economies: The Role of Entropy and Information Theory in Spatial Input-Output Modeling, Springer, 1983 | DOI

[4] Michael B. Cohen; Aleksander Madry; Dimitris Tsipras; Adrian Vladu Matrix scaling and balancing via box constrained Newton’s method and interior point methods, Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), (Berkeley, CA), Oct. 15-17 (2017), pp. 902-913 | DOI

[5] GÉANT About GÉANT (http://about.geant.org/about/)

[6] GÉANT GÉANT Tools Portal (http://tools.geant.org/portal/)

[7] Donald A. Gilchrist; Larry V. St Louis Completing input–output tables using partial information, with an application to Canadian data, Economic Systems Research, Volume 11 (1999) no. 2, pp. 185-194 | DOI

[8] G. Günlük-Şenesen; J. M. Bates Some experiments with methods of adjusting unbalanced data matrices, Journal of the Royal Statistical Society: Series A (Statistics in Society), Volume 151 (1988) no. 3, pp. 473-490 | DOI

[9] C. T. Ireland; Solomon Kullback Contingency tables with given marginals, Biometrika, Volume 55 (1968) no. 1, pp. 179-188 | DOI | MR | Zbl

[10] Bahman Kalantari; Isabella Lari; Federica Ricca; Bruno Simeone On the complexity of general matrix scaling and entropy minimization via the RAS algorithm, Mathematical Programming, Volume 112 (2008) no. 2, pp. 371-401 | DOI | MR | Zbl

[11] Michael L. Lahr; Louis de Mesnard Biproportional techniques in input-output analysis: table updating and structural analysis, Economic Systems Research, Volume 16 (2004) no. 2, pp. 115-134 | DOI

[12] André Lemelin A GRAS variant solving for minimum information loss, Economic Systems Research, Volume 21 (2009) no. 4, pp. 399-408 | DOI

[13] Manfred Lenzen; Blanca Gallego; Richard Wood Matrix balancing under conflicting information, Economic Systems Research, Volume 21 (2009) no. 1, pp. 23-44 | DOI

[14] Robert A. McDougall Entropy theory and RAS are friends, GTAP Working Papers (1999) no. 6 (Department of Agricultural Economics, Purdue University)

[15] Michael H. Schneider; Stavros A. Zenios A comparative study of algorithms for matrix balancing, Operations Research, Volume 38 (1990) no. 3, pp. 439-455 | DOI | Zbl

[16] Yin Zhang; Matthew Roughan; Nick Duffield; Albert Greenberg Fast accurate computation of large-scale IP traffic matrices from link loads, ACM SIGMETRICS Performance Evaluation Review, Volume 31 (2003) no. 1, pp. 206-217 | DOI

Cited by Sources:

Comments - Policy