On the Complexity of Matrix Balancing

DOI10.1137/S0895479895289765zbMATH Open0882.65031OpenAlexW1993677524MaRDI QIDQ4337392FDOQ4337392

Authors: Bahman Kalantari, Ali Shokoufandeh, Leonid G. Khachiyan 

Publication date: 3 February 1998

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895479895289765

Recommendations

• A fast algorithm for matrix balancing
• A Comparative Study of Algorithms for Matrix Balancing
• scientific article; zbMATH DE number 7376020
• Balancing an arbitrary matrix using computations with Stieltjes matrices
• scientific article; zbMATH DE number 2096649
• On the construction of balanced matrices
• Matrix Balancing on a Massively Parallel Connection Machine
• Interval-constrained matrix balancing
• On complexity of matrix scaling
• Vector and parallel computing for matrix balancing

zbMATH Keywords

geometric programmingpolynomial time complexitymatrix balancing

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Graph theory (including graph drawing) in computer science (68R10) Nonlinear programming (90C30) Numerical computation of matrix norms, conditioning, scaling (65F35)

Cited In (17)

• On complexity of matrix scaling
• Analysis of a classical matrix preconditioning algorithm
• Title not available (Why is that?)
• Matrix scaling, entropy minimization, and conjugate duality. I: Existence conditions
• Krylov Method Revisited with an Application to the Localization of Eigenvalues
• Matrix Balancing on a Massively Parallel Connection Machine
• Near-linear convergence of the random Osborne algorithm for matrix balancing
• Accelerating the Sinkhorn-Knopp iteration by Arnoldi-type methods
• A fast algorithm for matrix balancing
• Matrix balancing in \(L_p\) norms: bounding the convergence rate of Osborne's iteration
• Spectral analysis of matrix scaling and operator scaling
• Approximating min-mean-cycle for low-diameter graphs in near-optimal time and memory
• A lower bound for the Balan-Jiang matrix problem
• Title not available (Why is that?)
• MATRIX BALANCING PROBLEM AND BINARY AHP(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)
• On the complexity of general matrix scaling and entropy minimization via the RAS algorithm
• Scientific contributions of Leo Khachiyan (a short overview)

This page was built for publication: On the Complexity of Matrix Balancing

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