Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration

Authors Rafail Ostrovsky, Yuval Rabani, Arman Yousefi



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.93.pdf
  • Filesize: 496 kB
  • 11 pages

Document Identifiers

Author Details

Rafail Ostrovsky
  • Department of Computer Science, University of California Los Angeles, USA
Yuval Rabani
  • The Rachel and Selim Benin School of Computer Science and Engineering, The Hebrew University of Jerusalem, Israel
Arman Yousefi
  • Department of Computer Science, University of California Los Angeles, USA

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ICALP.2018.93

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Numerical Linear Algebra
  • Optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. EISPACK implementation. URL: http://www.netlib.org/eispack/balanc.f.
  2. Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Much faster algorithms for matrix scaling. In Proc. of the 58th Ann. IEEE Symp. on Foundations of Computer Science, 2017. Google Scholar
  3. T.-Y. Chen. Balancing sparse matrices for computing eigenvalues. Master’s thesis, UC Berkeley, May 1998. Google Scholar
  4. Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balancing via box constrained newton’s method and interior point methods. In Proc. of the 58th Ann. IEEE Symp. on Foundations of Computer Science, 2017. Google Scholar
  5. B. C. Eaves, A. J. Hoffman, U. G. Rothblum, and H. Schneider. Line-sum-symmetric scalings of square nonnegative matrices. In Mathematical Programming Essays in Honor of George B. Dantzig Part II, pages 124-141. Springer, 1985. Google Scholar
  6. J. Grad. Matrix balancing. The Computer Journal, 14(3):280-284, 1971. Google Scholar
  7. D. J. Hartfiel. Concerning diagonal similarity of irreducible matrices. In Proceedings of the American Mathematical Society, pages 419-425, 1971. Google Scholar
  8. B. Kalantari, L. Khachiyan, and A. Shokoufandeh. On the complexity of matrix balancing. SIAM Journal on Matrix Analysis and Applications, 118(2):450-463, 1997. Google Scholar
  9. D. Kressner. Numerical methods for general and structured eigenvalue problems. Princeton University Press, 2005. Google Scholar
  10. E. E. Osborne. On pre-conditioning of matrices. Journal of the ACM (JACM), 7(4):338-345, 1960. Google Scholar
  11. Rafail Ostrovsky, Yuval Rabani, and Arman Yousefi. Matrix balancing in lp norms: Bounding the convergence rate of osborne’s iteration. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pages 154-169, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3039686.3039697.
  12. B. N. Parlett and C. Reinsch. Balancing a matrix for calculation of eigenvalues and eigenvectors. Numerische Mathematik, 13(4):293-304, 1969. Google Scholar
  13. W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes: The Art of Scientific Computing, 3rd Edition. Cambridge University Press, 2007. Google Scholar
  14. H. Schneider and M. H. Schneider. Max-balancing weighted directed graphs and matrix scaling. Mathematics of Operations Research, 16(1):208-222, 1991. URL: http://dx.doi.org/10.1287/moor.16.1.208.
  15. L. J. Schulman and A. Sinclair. Analysis of a classical matrix preconditioning algorithm. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 831-840, 2015. Google Scholar
  16. L. N. Trefethen and M. Embree. Spectra and pseudospectra: The behavior of nonnormal matrices and operators. Springer, 2005. Google Scholar
  17. N. E. Young, R. E. Tarjan, and J. B. Orlin. Faster parametric shortest path and minimum-balance algorithms. Networks, 21(2):205-221, 1991. URL: http://dx.doi.org/10.1002/net.3230210206.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail