Geodesic
Algèbre, Théorie du contrôle
An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing
Chlebus, Edward1  ; Kasapu, Viswatej1
1 Department of Computer Science, Illinois Institute of Technology, 10 W. 31st St., Chicago, Illinois 60616, USA
Comptes Rendus. Mathématique, Tome 361 (2023) no. G4, pp. 737-746

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/crmath.398
Classification : 65F35, 65F50, 65K05, 90B20, 94A17

Chlebus, Edward 1 ; Kasapu, Viswatej 1

1 Department of Computer Science, Illinois Institute of Technology, 10 W. 31st St., Chicago, Illinois 60616, USA
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{CRMATH_2023__361_G4_737_0,
     author = {Chlebus, Edward and Kasapu, Viswatej},
     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},
     number = {G4},
     year = {2023},
     doi = {10.5802/crmath.398},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.5802/crmath.398/}
}
TY  - JOUR
AU  - Chlebus, Edward
AU  - Kasapu, Viswatej
TI  - An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing
JO  - Comptes Rendus. Mathématique
PY  - 2023
SP  - 737
EP  - 746
VL  - 361
IS  - G4
PB  - Académie des sciences, Paris
UR  - http://geodesic.mathdoc.fr/articles/10.5802/crmath.398/
DO  - 10.5802/crmath.398
LA  - en
ID  - CRMATH_2023__361_G4_737_0
ER  - 
%0 Journal Article
%A Chlebus, Edward
%A Kasapu, Viswatej
%T An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing
%J Comptes Rendus. Mathématique
%D 2023
%P 737-746
%V 361
%N G4
%I Académie des sciences, Paris
%U http://geodesic.mathdoc.fr/articles/10.5802/crmath.398/
%R 10.5802/crmath.398
%G en
%F CRMATH_2023__361_G4_737_0
Chlebus, Edward; Kasapu, Viswatej. An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing. Comptes Rendus. Mathématique, Tome 361 (2023) no. G4, pp. 737-746. doi: 10.5802/crmath.398

Cité par Sources :