Exact network averaging in 2N additions by back substitution: analysis and 53-node numerical test

Researcher Ricardo Merched published a mathematical study in Applied Network Science on average consensus: how N agents in a cooperative network find the exact arithmetic mean of dispersed local data without a central fusion processor. According to the paper, on an undirected connected graph the exact average can be computed by forward and backward substitution recursions with as little as 2N additions in total complexity springer.comApplied Network Sciencespringer.comOpen source ↗. For undirected graphs, existing schemes require O(KN²) multiplications, where K is the number of distinct eigenvalues of the graph Laplacian matrix.

The author formulates average consensus as a linearly constrained least-squares problem. This yields a sparse lower-triangular matrix factor whose columns sum to zero and whose sparsity matches the physical links between nodes.

Back substitution instead of matrix inversion

At the offline design stage, the symmetric reverse Cuthill-McKee permutation reorders the graph into a block-tridiagonal profile. The nodes then run a three-pass sequential algorithm of forward and backward substitutions, which avoids the dense matrix inversion needed by minimum-norm projections.

The triangular factor can be set with constant entries of 1 and −1 below the main diagonal, so no multiplications are needed at runtime. The network reaches the exact average in 2N communication steps with 2N additions in total. Triangular substitutions are backward-stable, so, as the paper reports, the result does not depend on the graph's algebraic connectivity or the conditioning of its Laplacian springer.comApplied Network Sciencespringer.comOpen source ↗.

The study also gives an alternative exact form as a matrix finite impulse response graph filter. The strictly lower-triangular part of the reordered factor is nilpotent, so its Neumann series terminates. In a 53-node graph the operator vanished after 23 iterations, and the whole operation took 47 matrix passes with complexity of the order of N² additions.

Why the eigenstep method fails numerically

The finite-time eigenstep method uses time-varying step sizes equal to the reciprocals of the distinct nonzero eigenvalues of the combination matrix, which in theory removes disagreement modes in K iterations. The paper shows that the unnormalized recursions are numerically unstable on large or ill-conditioned matrices: step sizes far above stability thresholds multiply rounding residuals from finite-precision arithmetic.

For the largest modes, the author derives a first-order bound on error amplification: the spectral condition number minus one, raised to a power proportional to the network dimension. In a test on an undirected 53-node network with a path-graph branch, a machine roundoff error of about 2.22×10⁻¹⁶ grew to the order of 10⁴², and the network did not reach consensus springer.comApplied Network Sciencespringer.comOpen source ↗.

The work also generalizes the eigenstep method to directed graphs with asymmetric combination matrices. Theorem 1 states that time-varying eigensteps converge in exactly K steps for diagonalizable asymmetric matrices.