Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration

2017/04/24 by Ostrovsky, Rafail, Rabani, Yuval, Yousefi, Arman
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1704.07406

Abstract

Osborne's iteration is a method for balancing n× n matrices which is widely used in linear algebra packages, as balancing preserves eigenvalues and stabilizes their numeral computation. The iteration can be implemented in any norm over ℝⁿ, but it is normally used in the L₂ norm. The choice of norm not only affects the desired balance condition, but also defines the iterated balancing step itself. In this paper we focus on Osborne's iteration in any L_p norm, where p < ∞. We design a specific implementation of Osborne's iteration in any L_p norm that converges to a strictly ε-balanced matrix in O(ε^-2n⁹ K) iterations, where K measures, roughly, the \em number of bits required to represent the entries of the input matrix. This is the first result that proves that Osborne's iteration in the L₂ norm (or any L_p norm, p < ∞) strictly balances matrices in polynomial time. This is a substantial improvement over our recent result (in SODA 2017) that showed weak balancing in L_p norms. Previously, Schulman and Sinclair (STOC 2015) showed strong balancing of Osborne's iteration in the L_∞ norm. Their result does not imply any bounds on strict balancing in other norms.

Related

• Matrix Balancing in Lp Norms: A New Analysis of Osborne's Iteration
• Near-linear convergence of the Random Osborne algorithm for Matrix Balancing
• Analysis of a Classical Matrix Preconditioning Algorithm
• Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm
• Matrix Scaling and Balancing via Box Constrained Newton's Method and\n Interior Point Methods