On the Complexity of Matrix Balancing

DOI10.1137/S0895479895289765MaRDI QIDQ4337392zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(17)

• On complexity of matrix scaling
• Matrix scaling, entropy minimization, and conjugate duality. I: Existence conditions
• Analysis of a classical matrix preconditioning algorithm
• scientific article; zbMATH DE number 7376020 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 6703492 (Why is no real title available?)
• 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)