Near-Optimal Parallel -Matrix Scaling
In the authors' words
In this paper we consider the problem of computing a positive diagonal scaling of a symmetric -matrix so that all row and column sums are . We provide a poly-logarithmic iteration algorithm that solves this problem to high accuracy, where the cost of each iteration is dominated by the cost of solving a Laplacian system. This improves upon the recent iteration bound of [Vladu STOC 2025] and yields a randomized algorithm for the problem that runs in near-linear time and poly-logarithmic parallel depth.
Main resultThe abstract does not state a limitation.
Appeared: Friday, October 16. arXiv. Preprint, not yet peer-reviewed.