Improved parallel method for scaling special matrices faster
Near-Optimal Parallel $M$-Matrix Scaling
Data Structures and Algorithms
Summary
This paper deals with scaling certain square grids of numbers called symmetric M-matrices so that each row and column adds up to one. The authors present a new algorithm that achieves this very accurately with fewer steps than previous methods. Each step mainly relies on solving a related problem about networks called Laplacian systems. Their approach is faster and works well in parallel computing, meaning many calculations can be done simultaneously.
What this means in practice
- •For numerical linear algebra teams: Compute balanced scalings of matrices efficiently for numerical simulations requiring fast and accurate normalization.
- •For parallel computing engineers: Implement scalable and near-linear time matrix normalization routines in parallel environments to improve computational workflows.
Authors
Chih-Hung Liu, Aaron Sidford, Ta-Wei Tu
Abstract
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.