Skip to content
DraconiticResearch
Search Sources API
182,544 studies31 sourcesUpdated 39 min ago
PreprintarXiv licencearXiv

Near-Optimal Parallel M-Matrix Scaling

  • Chih-Hung Liu
  • Aaron Sidford
  • Ta-Wei Tu
Open at sourcePDFDOICite

Abstract

In this paper we consider the problem of computing a positive diagonal scaling of a d × 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 Õ(d1/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.

Related

  1. Near-Optimal Nonconvex Matrix Completion
    Jian-Feng Cai, Xiliang Lu, Juntao You
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
  2. Axis-parallel square packing with an exact formula for optimal packing of seven squares
    Matthew Badger
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  3. An exact formula for optimal axis-parallel packing of eight squares
    Matthew Badger
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  4. The threshold for fractional clique decompositions of random hypergraphs, via matrix scaling
    Tuan Tran
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  5. Distance and resistance on random series-parallel graphs: logarithmic speeds and near-critical asymptotics
    Ruiqi Ding, Zehua He, Yutao Liang +1
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{liu2026nearoptimal,
  title = {{Near-Optimal Parallel $M$-Matrix Scaling}},
  author = {Chih-Hung Liu and Aaron Sidford and Ta-Wei Tu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.22302},
  eprint = {2610.22302},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.22302},
}
RIS
TY  - UNPB
TI  - Near-Optimal Parallel M-Matrix Scaling
AU  - Chih-Hung Liu
AU  - Aaron Sidford
AU  - Ta-Wei Tu
PY  - 2026
DA  - 2026/10/15
PB  - arXiv
DO  - 10.48550/arxiv.2610.22302
UR  - https://arxiv.org/abs/2610.22302
AB  - In this paper we consider the problem of computing a positive diagonal scaling of a d × 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 Õ(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.
ER  -