{"id":"arxiv/2610.22302","url":"https://arxiv.org/abs/2610.22302","tags":["cs.DS","math.OC"],"score":0,"title":"Near-Optimal Parallel $M$-Matrix Scaling","domain":"cs.DS","source":"arxiv","authors":["Chih-Hung Liu","Aaron Sidford","Ta-Wei Tu"],"reviews":0,"subject":"cs.DS","summary":"In this paper we consider the problem of computing a positive diagonal scaling of a $d \\times d$ symmetric $M$-matrix so that all row and column sums are $1$. 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 $\\tilde{O}(d^{1/3})$ 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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-15","reactions":{}}