A fast algorithm for matrix balancing

Philip Knight, Daniel Ruiz

Research output: Contribution to journalArticlepeer-review

153 Citations (Scopus)
609 Downloads (Pure)


As long as a square nonnegative matrix A contains sufficient nonzero elements, then the matrix can be balanced, that is we can find a diagonal scaling of A that is doubly stochastic. A number of algorithms have been proposed to achieve the balancing, the most well known of these being Sinkhorn-Knopp. In this paper we derive new algorithms based on inner-outer iteration schemes. We show that Sinkhorn-Knopp belongs to this family, but other members can converge much more quickly. In particular, we show that while stationary iterative methods offer little or no improvement in many cases, a scheme using a preconditioned conjugate gradient method as the inner iteration can give quadratic convergence at low cost.
Original languageEnglish
Pages (from-to)1029-1047
Number of pages19
JournalIMA Journal of Numerical Analysis
Issue number3
Early online date26 Oct 2012
Publication statusPublished - 2013


  • matrix balancing
  • quadratic convergence
  • diagonal scaling
  • Sinkhorn-Knopp algorithm
  • doubly stochastic matrix
  • conjugate gradient iteration

Cite this