Article

Matrix scaling by network flow

Authors:

Günter Rote,

Martin ZachariasenAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 848 - 854

Published: 07 January 2007 Publication History

Get Access

Abstract

A given nonnegative n x n matrix A = (a_ij) is to be scaled, by multiplying its rows and columns by unknown positive multipliers λ_i and μ_j, such that the resulting matrix (a_ijλ_iμ_j) has specified row and column sums r_i and s_j.

We give an algorithm that achieves the desired row and column sums with a maximum absolute error ε in O(n⁴(log n + log h/ε)) steps, where h is the overall total of the result matrix.

Our algorithm is a scaling algorithm. It solves a sequence of more and more refined discretizations. The discretizations are minimum-cost network flow problems with convex piecewise linear costs. These discretizations are interesting in their own right because they arise in proportional elections.

References

[1]

M. Bacharach. Biproportional Matrices and Input-Output Change. Cambridge University Press, 1970.

Google Scholar

[2]

Michel Balinski and Gabrielle Demange. Algorithms for proportional matrices in reals and integers. Math. Programming, 45:193--210, 1989.

Digital Library

Google Scholar

[3]

Michel Balinski and Svetlozar T. Rachev. Rounding proportions: methods of rounding. Math. Scientist, 22:1--26, 1997.

Google Scholar

[4]

William R. Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver. Combinatorial Optimization. Wiley, 1998.

Digital Library

Google Scholar

[5]

Martin Fürer. Quadratic convergence for scaling of matrices. In Lars Arge, Giuseppe F. Italiano, and Robert Sedgewick, editors, Proc. ALENEX/ANALC 2004, 6th Workshop on Algorithm Engineering and Experiments and 1st Workshop on Analytic Algorithmics and Combinatorics, New Orleans, pages 216--223. SIAM, January 2004.

Google Scholar

[6]

Norbert Gaffke and Friedrich Pukelsheim. Divisor methods for proportional representation systems: an optimization approach to vector and matrix problems. Technical Report (Preprint) 06--18, Universität Magdeburg, Fakultät für Mathematik, March 2006. http://www.math.uni-magdeburg.de/preprints/shadows/06-18report.html.

Google Scholar

[7]

Dorit Hochbaum. Complexity and algorithms for convex network optimization and other nonlinear problems. 4OR, 3(3):171--216, 2005.

Google Scholar

[8]

Bahman Kalantari and Leonid Khachiyan. On the complexity of nonnegative-matrix scaling. Linear Algebra Appl., 240:87--104, 1996.

Google Scholar

[9]

Alexander V. Karzanov and S. Thomas McCormick. Polynomial methods for separable convex optimization in unimodular linear spaces with applications. SIAM J. Comput., 26(4):1245--1275, 1997.

Digital Library

Google Scholar

[10]

Nathan Linial, Alex Samorodnitsky, and Avi Wigderson. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica, 20(4):545--568, 2000.

Google Scholar

[11]

U. Rothblum and H. Schneider. Scaling of matrices which have prespecified row sums and column sums via optimization. Linear Algebra Appl., 114--115:737--764, 1989.

Google Scholar

[12]

Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Statist., 35:876--879, 1964.

Google Scholar

[13]

D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362--381, 1983.

Digital Library

Google Scholar

[14]

George W. Soules. The rate of convergence of Sinkhorn balancing. Linear Algebra Appl., 150:3--40, 1991.

Google Scholar

Cited By

View all

Freire AAcuña VCrescenzi PFerreira CLacroix VMilreu PMoreno ESagot M(2012)Minimum ratio cover of matrix columns by extreme rays of its induced coneProceedings of the Second international conference on Combinatorial Optimization10.1007/978-3-642-32147-4_16(165-177)Online publication date: 19-Apr-2012
https://dl.acm.org/doi/10.1007/978-3-642-32147-4_16

Matrix scaling by network flow
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis

Recommendations

An iterative algorithm for searching a scaling matrix for diagonal dominance

Diagonal dominance of matrices and M-matrices (and H-matrices) play an important role in stability theory of dynamical systems. But it is difficult to determine the scaling matrix G=diag(g"1,...,g"n) (g"1,...,g"n>0) with AG being a strictly diagonally ...
Scaling Matrices to Prescribed Row and Column Maxima

A nonnegative symmetric matrix $B$ has row maxima prescribed by a given vector $r$, if for each index $i$, the maximum entry in the $i$th row of $B$ equals $r_i$. This paper presents necessary and sufficient conditions so that for a given nonnegative ...
Polynomial scaling in the conjugate gradient method and related topics in matrix scaling

Comments

Information & Contributors

Information

Published In

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
281
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Freire AAcuña VCrescenzi PFerreira CLacroix VMilreu PMoreno ESagot M(2012)Minimum ratio cover of matrix columns by extreme rays of its induced coneProceedings of the Second international conference on Combinatorial Optimization10.1007/978-3-642-32147-4_16(165-177)Online publication date: 19-Apr-2012
https://dl.acm.org/doi/10.1007/978-3-642-32147-4_16

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Recommendations

An iterative algorithm for searching a scaling matrix for diagonal dominance

Scaling Matrices to Prescribed Row and Column Maxima

Polynomial scaling in the conjugate gradient method and related topics in matrix scaling

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations