We study a classical iterative algorithm for balancing matrices in the @math norm via a scaling transformation. This algorithm, which goes back to Osborne and Parlett & Reinsch in the 1960s, is implemented as a standard preconditioner in many numerical linear algebra packages. Surprisingly, despite its widespread use over several decades, no bounds were known on its rate of convergence. In this paper we prove that, for any irreducible @math (real or complex) input matrix @math , a natural variant of the algorithm converges in @math elementary balancing operations, where @math measures the initial imbalance of @math and @math is the target imbalance of the output matrix. (The imbalance of @math is @math , where @math are the maximum entries in magnitude in the @math th row and column respectively.) This bound is tight up to the @math factor. A balancing operation scales the @math th row and column so that their maximum entries are equal, and requires @math arithmetic operations on average, where @math is the number of non-zero elements in @math . Thus the running time of the iterative algorithm is @math . This is the first time bound of any kind on any variant of the Osborne-Parlett-Reinsch algorithm. We also prove a conjecture of Chen that characterizes those matrices for which the limit of the balancing process is independent of the order in which balancing operations are performed.
@cite_6: A weighted directed graph G is a triple V, A, g where V, A is a directed graph and g is an arbitrary real-valued function defined on the arc set A. Let G be a strongly-connected, simple weighted directed graph. We say that G is max-balanced if for every nontrivial subset of the vertices W, the maximum weight over arcs leaving W equals the maximum weight over arcs entering W. We show that there exists a up to an additive constant unique potential pv for v ∈ V such that V, A, gp is max-balanced where gap = pu + ga-pv for a = u, v ∈ A. We describe an O|V|2|A| algorithm for computing p using an algorithm for computing the maximum cycle-mean of G. Finally, we apply our principal result to the similarity scaling of nonnegative matrices.
@cite_8: We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum-balance algorithm to obtain a faster minimum-balance algorithm. For a graph with n vertices and m edges, our parametric shortest path algorithm and our minimum-balance algorithm both run in O(nm + n2 log n) time, improved from O(nm log n) for the parametric shortest path algorithm of Karp and Orlin and O(n2m) for the minimum-balance algorithm of Schneider and Schneider. An important application of the parametric shortest path algorithm is in finding a minimum mean cycle. Experiments on random graphs suggest that the expected time for finding a minimum mean cycle with our algorithm is O(n log n + m).
A sequence of two papers offers an alternative, and substantially more complex, non-iterative algorithm for matrix balancing in the @math norm. Schneider and Schneider @cite_6 gave an @math -time algorithm based on finding maximum mean-weight cycles in a graph; the running time was improved to @math using Fibonnaci heaps and other techniques by Young, Tarjan and Orlin @cite_8 . This is asymptotically faster than the @math worst case running time we establish for the iterative algorithm; and for some graphs (e.g., the cycle) it is faster than the actual running time of the iterative algorithm.