Many foundational problems in science and engineering ultimately reduce to solving a system of linear equations, $Ax = b$. When the scale of the data becomes too massive for a single machine, or when the data is inherently collected by a decentralized network of agents (such as sensor networks or robotic fleets), we must solve these systems distributively.
In a distributed setting, the global matrix $A$ and vector $b$ are partitioned into local shards, meaning each node $i$ only knows its local equations, $A_i x = b_i$. The challenge is to compute the exact global solution—or, if the system is overdetermined and inconsistent, the global least-squares solution—using only local computation and neighbor-to-neighbor communication.
Traditional consensus methods often settle for approximations or require highly specific network structures. However, a powerful paradigm has emerged that reformulates linear equation solving as a distributed optimization problem, enabling networks to achieve mathematically exact solutions without sacrificing precision.
The Core Intuition: Balancing Consensus and Local Gradients
To understand why this works, consider what happens if each node attempts to solve its local system independently. Node $i$ wants to minimize its local residual error, $\|A_i x_i - b_i\|^2$. If it runs standard gradient descent, its estimate $x_i$ will quickly converge to a local solution that satisfies its own equations but completely ignores the constraints held by the rest of the network.
To fix this, we can reformulate the problem as a constrained optimization task. We want to minimize the sum of all local errors while forcing all nodes to agree on the final state:
$$\min_{x_1, x_2, \dots, x_n} \sum_{i=1}^n \|A_i x_i - b_i\|^2 \quad \text{subject to} \quad x_i = x_j \text{ for all neighbors } (i,j)$$
This formulation reveals a beautiful tension between two forces: local optimization (moving down the gradient of local error) and global consensus (pulling neighboring estimates together).
In Distributed least squares solver for network linear equations, Tao Yang et al. demonstrate how a discrete-time algorithm can perfectly balance these forces. In their framework, nodes update their estimates by taking a weighted average of their neighbors' states and then injecting a correction step based on their local gradient. The authors derive a precise, necessary and sufficient condition on the step-size that guarantees the entire network will converge exponentially to the exact global least-squares solution. A similar first-order approach is unified by Yang Liu et al. in Network flows that solve least squares for linear equations, showing that this mechanism robustly accommodates both unique and non-unique solution spaces.
Continuous-Time and Primal-Dual Dynamics
Instead of discrete steps, we can also view this process through the lens of continuous-time dynamical systems. By treating the consensus constraints as physical forces, we can design network flows that naturally drain energy out of the system until it settles into the global minimum.
One classic optimization tool for handling constraints is the Arrow-Hurwicz-Uzawa flow, which updates primal variables (the solution estimates) and dual variables (the penalty prices for disagreement) simultaneously. In An Arrow-Hurwicz-Uzawa type flow as least squares solver for network linear equations, Yang Liu et al. adapt this flow to network linear equations. The dual variables act as a memory mechanism, accumulating the history of disagreement between neighbors and applying a corrective pressure that prevents the algorithm from getting stuck in local minima.
For more complex matrix equations of the form $AXB = F$, Xianlin Zeng et al. introduce a continuous-time primal-dual framework with derivative feedback in Distributed computation of linear matrix equations: An optimization perspective. By incorporating derivative feedback, the network can anticipate changes in the consensus error, leading to guaranteed exponential convergence to the least-squares solution even when the underlying equations are completely inconsistent.
[ Local Gradient Step ] ──> Pushes toward local fit: A_i * x_i ≈ b_i
│
▼
[ Node Estimate (x_i) ] <──> [ Neighbor Communication ] ──> Pulls toward consensus: x_i ≈ x_j
Real-world networks, however, are rarely static or perfectly reliable. Communication links drop, and topologies change randomly. To address this, Peng Yi et al. analyze Distributed Linear Equations Over Random Networks. They prove that by employing a diminishing step-size, a distributed gradient descent algorithm can overcome temporal and spatial network dependencies, driving all nodes to the unique least-squares solution at a sublinear convergence rate.
Scaling Up: Distributed Krylov and Second-Order Methods
While first-order consensus methods are elegant and robust, they can require many communication rounds to converge on massive, high-dimensional problems. For applications like large-scale machine learning or 3D computer vision, we need faster, second-order optimization techniques.
The key insight here is that we do not need to explicitly construct or communicate high-dimensional matrices across the network. Instead, we can distribute iterative linear solvers like the Conjugate Gradient (CG) method. Because CG fundamentally relies on matrix-vector products ($Ax$), and because matrix multiplication can be broken down into independent row-vector products ($\sum A_i x$), we can distribute the computation perfectly. Nodes compute their local matrix-vector products simultaneously, and the network only needs to synchronize the resulting low-dimensional vectors.
In DiSCO: Distributed Optimization for Self-Concordant Empirical Loss, Yuchen Zhang et al. combine an inexact Newton method with a distributed preconditioning strategy. By using a distributed CG method to solve the Newton step, DiSCO achieves a communication cost that is virtually independent of the total amount of data in the network, scaling gracefully as more machines are added.
This exact distributed solving strategy has revolutionized fields like Bundle Adjustment (BA) in computer vision, where thousands of camera poses and 3D points must be optimized globally. Rather than relying on heuristic "divide-and-conquer" approximations that sacrifice accuracy, modern systems maintain global integrity by parallelizing the exact equations.
For instance, Jie Ren et al. developed MegBA: A GPU-Based Distributed Library for Large-Scale Bundle Adjustment, which utilizes distributed Schur elimination and a distributed preconditioned conjugate gradient solver. By synchronizing states across GPU nodes with high-speed communication libraries, the library produces results identical to a single-node exact solver while shattering memory bottlenecks. Similarly, Maoteng Zheng et al. demonstrate in Distributed bundle adjustment with block-based sparse matrix compression for super large scale datasets that parallelizing the formation and solving of the exact system equations preserves maximum precision, proving that distributed scale does not require an accuracy trade-off.
Key Foundational Work
Distributed Computation of Linear Matrix Equations: An Optimization Perspective (2017) — contributed 1 concept elements to this direction.
DiSCO: Distributed Optimization for Self-Concordant Empirical Loss (2015) — contributed 1 concept elements to this direction.