arXiv preprint ·
Near-Optimal Parallel $M$-Matrix Scaling
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
When is a better LLM worth paying for? Stochastic Optimization with Switching Mixed-Fidelity Oracles
ParetoChat: An LLM-Based Interface for Interactive Multi-Objective Optimization
Honesty is the Best Policy ... or is it? Demand Management for Probabilistic Service Options
Distributed Performance Boosting through Neural Control for Plug-and-Play Networks
Quantum-compatible Riemannian conjugate gradient for ground-state preparation
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.