Near-Optimal Parallel $M$-Matrix Scaling

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.

Source: arXiv:2610.22302v1 - http://arxiv.org/abs/2610.22302v1 PDF: https://arxiv.org/pdf/2610.22302v1 Original Link: http://arxiv.org/abs/2610.22302v1