Matrix Balancing in Lp Norms

Matrix balancing is a preprocessing step in linear algebra computations such as the computation of eigenvalues of a matrix. Such computations are known to be numerically unstable if the matrix is unbalanced, that is the L2 norm of some rows and their corresponding columns are different by orders of magnitude. Given an unbalanced matrix A, the goal of matrix balancing is to find an invertible diagonal matrix D such that DAD^{−1} is balanced or approximately balanced in the sense that every row and its corresponding column have the same norm. In thesis, we study a classic iterative algorithm for matrix balancing due to Osborne (1960). The original algorithm was proposed for balancing rows and columns in the L2 norm, and it works by iterating over balancing a row-column pair in fixed round-robin order. Variants of the algorithm for other norms have been heavily studied and are implemented as standard preconditioners in many numerical linear algebra packages. Despite the popularity of Osborne’s algorithm in practice and extensive research on it there were no polynomial-time upper bound on the running time of this algorithm to explain the excellent performance of this algorithm in practice. Recently (in 2015), Schulman and Sinclair, in a first result of its kind for any norm, analyzed the rate of convergence of a variant of Osborne’s algorithm that uses the L∞ norm and a different order of choosing row-column pairs. In this thesis we study matrix balancing in the L1 norm and other Lp norms. We consider two notions of approximately balancing matrices and refer to them as ε-balancing and strict ε-balancing. As the names suggest strict ε-balancing implies ε-balancing. These notions will be defined in the body of the thesis.We prove upper bounds on the convergence rate of Osborne’s algorithm and some of its vari- ants. We prove fast convergence of different variants of the algorithm to an ε-balanced matrix, and propose a variant that converges to a strictly ε-balanced matrix in polynomial time. These results resolve a problem that has been open since Osborne proposed his algorithm in 1960. The following is a summary of our results for any real matrix A = (a_{ij})_{i,j}:1. We propose a simple greedy variant of Osborne’s algorithm and show that it converges to an ε-balanced matrix in K = O(min{ε^{−2} log w, ε^{−1}n^{3/2} log(w/ε)}) iterations that cost a total of O(m + Kn log n) arithmetic operations over O(n log(w/ε))-bit numbers. Here m is the number of non-zero entries of A, and w = \sum_{i,j} |a_{ij} |/a_{min} with a_{min}= min{|a_{ij} | : a_{ij} ̸= 0}.2. We show that the original round-robin implementation of Osborne’s algorithm converges to an ε-balanced matrix in O(ε^{−2}n^2 log w) iterations totaling O(ε^{−2}mn log w) arithmetic operations over O(n log(w/ε))-bit numbers.3. We devise a random implementation of the iteration and show that it converges to an ε-balanced matrix in O(ε^{−2} log w) iterations using O(m + ε^{−2}n log w) arithmetic operations over O(log(wn/ε))-bit numbers.4. We propose a variant of Osborne’s algorithm and prove that it converges to a strictly ε-balanced matrix in O (ε^{−2}n^9 log(wn/ε) log w/ log n) iterations that requireO (ε^{−2}n^10 log(wn/ε) log w/ log n) arithmetic operations over O(n log w/ε)-bit numbers.5. We demonstrate a lower bound of Ω(1/\sqrt{ε}) on the convergence rate of any implementation of the iteration. Thus, the dependence of our upper bounds on 1/ε is in the right ballpark.All our results are proved for balancing in L1 norm, but we observe, through a known trivial reduction, that our results for L1 balancing apply to any Lp norm for all finite p, at the cost of increasing the number of iterations by only a factor of p (or p2 in some cases)