Near-Optimal Parallel $M$-Matrix Scaling

• The symmetric problem encompasses asymmetric scaling: scaling an anti-block-diagonal matrix built from B and B⊤ yields row- and column-sum scaling for B.Source: §1 · p. 1
• Matrix scaling has applications across scientific disciplines, and linear programming can be reduced to it.Source: §1 · p. 1
• A symmetric M-matrix is positive definite with non-positive off-diagonal entries, and the target is a positive diagonal scaling whose row sums are within ε of one in ℓ2 norm.Source: §1 · p. 1
• The prior [Vla25] method used ˜O(d^1/3) IPM iterations, while [CKL+22] had almost-linear depth despite almost-linear running time.[Vla25] achieved ˜O(d^1/3) depth; the new algorithm improves on both comparisons.Source: §1 · p. 2
• With high probability, the algorithm computes an ε-accurate scaling in ˜O(nnz(A)·log^3 κ(A) log(1/ε) log log(1/ε)) time and poly-logarithmic depth.The accuracy criterion is ∥XAX⃗1 −⃗1∥2 ≤ ε.Source: §1 · p. 2
• The algorithm first scales A to be symmetric diagonally dominant, then uses an ˜O(1)-iteration IPM whose iterations are dominated by Laplacian-system solves.The initial SDD scaling is computable with ˜O(1) Laplacian-system solves.Source: §1 · p. 2

A Path-Following Approach to Matrix Scaling

• Path-following increases μ while keeping iterates close enough to the central path for a few Newton steps to minimize the next objective.A larger region counted as close permits more aggressive increases in μ and fewer overall iterations.Source: §2 · pp. 4–5

Our Approach

• An ℓ∞ congestion bound uses M-matrix structure to permit Θ(1) increases in μ while maintaining efficient centering, suggesting an O~(1)-iteration analysis.The bound relies on controlling the infinity norm of (I + A_μ(x))^-1 when the congestion vector has infinity norm below 1/2.Source: §2 · pp. 5–6

The Key Observation

• Choosing b entry-wise nonnegative makes the right-hand side of the key inverse bound entry-wise at most 1.The proposed initialization uses a positive y with YAY1 ≥ γ·1 to obtain a nonnegative b and complete the overview’s O~(1)-iteration analysis.Source: §2 · p. 6

Comparison with Quadratic Optimization and Limitations of Our Approach

• The overview’s faster analysis does not directly extend to quadratic optimization because its linear-term vector b cannot be freely chosen nonnegative.The authors report no direct reduction between the two problems and leave their relationship as an open problem.Source: §2 · p. 7

3.1 ℓ∞-Path Following Algorithm

• The path-following algorithm first decreases μ through approximate Newton steps, then sets μ to zero and minimizes the row-sum residual.The first phase halves μ; the second decreases the ℓ∞ residual quadratically, requiring O(log(dq) + log log(1/ε)) total iterations.Source: §3.1 · pp. 7, 12
• The paper contrasts its quadratic-optimization perspective with a convex-cost-flow approach, noting that prior flow algorithms for scaling were almost-linear-time but highly sequential.The flow approach is discussed as related work rather than as part of the parallel path-following algorithm.Source: §3.1 · p. 7
• Each iteration reduces to solving an SDD linear system, with the approximate-solve accuracy adjusted to the scaling matrix’s condition number.The section’s runtime and parallel-depth bounds are expressed through the costs of SDD solves.Source: §3.1 · pp. 11–12

3.2 Initializing the Path-Following Algorithm

• The initialization uses [AJSS19] to find a scaling that makes the M-matrix diagonally dominant, providing the initial point required by path following.Together with the path-following theorem, this reduces scaling to ˜O(1) iterations of SDD system solves.Source: §3.2 · pp. 12–13
• Theorem 3.11 gives a high-probability algorithm for ε-approximate scaling after initialization, using the path-following result and an initial-point construction.The proof plugs in known SDD solvers to obtain the stated time and parallel-depth bounds; the supplied theorem text does not include the full bounds.Source: §3.2 · p. 13

A Almost-Linear Time M-Matrix Scaling via Convex Flow

• After making A diagonally dominant, the section decomposes it as A = C + D, where C is a Laplacian and D is nonnegative diagonal.The Laplacian is represented as C = B⊤WB using a graph incidence matrix B and nonnegative diagonal matrix W.Source: A Almost-Linear Time M-Matrix Scaling… · p. 18
• The scaling optimum is characterized through an optimization problem and its dual, which the section converts into a convex flow formulation.The supplied passages do not include the full optimization objective or dual.Source: A Almost-Linear Time M-Matrix Scaling… · pp. 18–19
• Adding a vertex connected to each original vertex with infinite capacity in both directions yields a flow network whose minimum-cost flow converts back to the scaling minimizer by duality.Original-edge costs and added-edge costs are specified separately in the formulation.Source: A Almost-Linear Time M-Matrix Scaling… · p. 19

B Omitted Proofs

• The proof bounds the iterates’ conditioning using lower and upper bounds on their coordinates and on the Hessian eigenvalues.These bounds yield κ(∇²fµ′(x)) ≤ 4q for the Newton system described in the proof.Source: B Omitted Proofs · pp. 19–20
• The Newton system can be implemented through an SDD solve because I + A(x) is SDD in the centered region, with the solution transformed by X.The required SDD-solve accuracy is adjusted by κ(X)^2.Source: B Omitted Proofs · p. 21
• The initialization procedure repeatedly halves α while maintaining an approximate solution for A/s + αI, stopping when α∥vα∥∞ ≤ 1/4.The proof then uses the resulting vector to obtain the required positive scaling vector.Source: B Omitted Proofs · pp. 21–22
• The initialization takes O(log(dκ(A))) iterations, each using SDD solver calls for time and parallel-depth costs.The stated per-iteration costs include an additional O(log(dκ(A))) factor and an accuracy polynomial in d and κ(A).Source: B Omitted Proofs · p. 22