Matrix Balancing in Lp Norm

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 L 2 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 Linfinity norm and a different order of choosing row-column pairs. In this thesis we study matrix balancing in the L1 norm and other L p norms. We consider two notions of approximately balancing matrices and refer to them as epsilon-balancing and strict epsilon-balancing . As the names suggest strict epsilon-balancing implies epsilon-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 epsilon-balanced matrix, and propose a variant that converges to a strictly epsilon-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 = (aij)ni,j = 1: 1. We propose a simple greedy variant of Osborne's algorithm and show that it converges to an epsilon-balanced matrix in K = O(min{epsilon--2 log w, epsilon --1n3/2 log(w/epsilon)}) iterations that cost a total of O(m + Kn log n) arithmetic operations over O( n log(w/epsilon))-bit numbers. Here m is the number of non-zero entries of A, and w = sum i,j |aij |/amin with amin = min{|aij | : aij ≠ 0}. 2. We show that the original round-robin implementation of Osborne's algorithm converges to an epsilon-balanced matrix in O(epsilon--2n 2 log w) iterations totaling O(epsilon --2mn log w) arithmetic operations over O(n log(w/epsilon))-bit numbers. 3. We devise a random implementation of the iteration and show that it converges to an epsilon-balanced matrix in O(epsilon --2 log w) iterations using O(m + epsilon--2n log w) arithmetic operations over O(log(wn/epsilon))-bit numbers. 4. We propose a variant of Osborne's algorithm and prove that it converges to a strictly epsilon-balanced matrix in O(epsilon --2n9 log(wn/epsilon) log w/ log n) iterations that require O(epsilon--2n10 log(wn/epsilon) log w/ log n) arithmetic operations over O(n log w/epsilon)-bit numbers. 5. We demonstrate a lower bound of O(1/√epsilon) on the convergence rate of any implementation of the iteration. Thus, the dependence of our upper bounds on 1/epsilon 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 p 2 in some cases).