DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2018.93

Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration

Authors: Rafail Ostrovsky, Yuval Rabani, and Arman Yousefi

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

Osborne's iteration is a method for balancing n x 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 R^n, but it is normally used in the L_2 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 < infty. We design a specific implementation of Osborne's iteration in any L_p norm that converges to a strictly epsilon-balanced matrix in O~(epsilon^{-2}n^{9} K) iterations, where K measures, roughly, the number of bits required to represent the entries of the input matrix. This is the first result that proves a variant of Osborne's iteration in the L_2 norm (or any L_p norm, p < infty) 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 strict balancing of another variant of Osborne's iteration in the L_infty norm. Their result does not imply any bounds on strict balancing in other norms.

Cite as

Rafail Ostrovsky, Yuval Rabani, and Arman Yousefi. Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 93:1-93:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ostrovsky_et_al:LIPIcs.ICALP.2018.93,
  author =	{Ostrovsky, Rafail and Rabani, Yuval and Yousefi, Arman},
  title =	{{Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{93:1--93:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.93},
  URN =		{urn:nbn:de:0030-drops-90976},
  doi =		{10.4230/LIPIcs.ICALP.2018.93},
  annote =	{Keywords: Numerical Linear Algebra, Optimization}
}

Search Results

Documents authored by Yousefi, Arman

Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration

Abstract

Cite as

Thanks for your feedback!

Could not send message