Matrix balancing in L_p norms: bounding the convergence rate of Osborne's iteration

DOI10.1137/1.9781611974782.11MaRDI QIDQ4575746zbMATH OpenOpenAlexFDO

Authors Rafail Ostrovsky, Yuval Rabani, Arman Yousefi

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.08083

Mathematics Subject Classification ID

Preconditioners for iterative methods (65F08) Numerical computation of matrix norms, conditioning, scaling (65F35)

Abstract: We study an iterative matrix conditioning algorithm due to Osborne (1960). The goal of the algorithm is to convert a square matrix into a balanced matrix where every row and corresponding column have the same norm. 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. Recently, Schulman and Sinclair (2015), 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_{infty}$ norm and a different order of choosing row-column pairs. In this paper we study matrix balancing in the $L_1$ norm and other $L_p$ norms. We show the following results for any matrix $A=(a_{ij}{)}_{i,j=1}^n$, resolving in particular a main open problem mentioned by Schulman and Sinclair. 1) We analyze the iteration for the $L_1$ norm under a greedy order of balancing. We show that it converges to an $epsilon$-balanced matrix in $K=O(minepsilo{n}^{-2}logw,epsilo{n}^{-1}{n}^{3/2}log(w/epsilon))$ iterations that cost a total of $O(m+Knlogn)$ arithmetic operations over $O(nlogw)$-bit numbers. Here $m$ is the number of non-zero entries of $A$, and $w=su{m}_{i,j}|a_{ij}|/a_{min}$ with $a_{min}=min|a_{ij}|:a_{ij}eq0$. 2) We show that the original round-robin implementation converges to an $epsilon$-balanced matrix in $O(epsilo{n}^{-2}{n}^{2}logw)$ iterations totalling $O(epsilo{n}^{-2}mnlogw)$ arithmetic operations over $O(nlogw)$-bit numbers. 3) We demonstrate a lower bound of $Omega(1/sqrtepsilon)$ on the convergence rate of any implementation of the iteration.

Recommendations

• scientific article; zbMATH DE number 7376020
• Analysis of a classical matrix preconditioning algorithm
• Analysis of a Classical Matrix Preconditioning Algorithm
• A fast algorithm for matrix balancing
• On the Complexity of Matrix Balancing

Cited in

(7)

• Near-linear convergence of the random Osborne algorithm for matrix balancing
• Analysis of a classical matrix preconditioning algorithm
• scientific article; zbMATH DE number 7376020 (Why is no real title available?)
• Approximating min-mean-cycle for low-diameter graphs in near-optimal time and memory
• Directed shortest paths via approximate cost balancing
• Near-linear runtime for a classical matrix preconditioning algorithm
• Quantum algorithms for matrix scaling and matrix balancing

This page was built for publication: Matrix balancing in \(L_p\) norms: bounding the convergence rate of Osborne's iteration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575746)