Sparse factorization of the square all-ones matrix of arbitrary order

DOI10.1137/24M1633790MaRDI QIDQ7016668zbMATH OpenFDO

Authors Xin Jiang, Edward Duc Hien Nguyen, César A. Uribe, Bicheng Ying

Publication date 6 March 2025

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/24M1633790

zbMATH Keywords

all-ones matrixaverage consensusdecentralized optimizationfinite-time consensussparse matrix factorization

Mathematics Subject Classification ID

Factorization of matrices (15A23) Stochastic matrices (15B51) Computational methods for sparse matrices (65F50) Distributed algorithms (68W15)

Review text

The authors study the sparse factorization of the scaled all-ones \(n\times n\) matrix\N\[\NJ = \frac{1}{n} \begin{bmatrix} 1 & 1 & \cdots & 1 \\\N1 & 1 & \cdots & 1 \\\N\vdots & \vdots & \ddots & \vdots \\\N1 & 1 & \cdots & 1 \end{bmatrix}.\N\]\NThis problem finds applications in graph theory, decentralized consensus and optimization algorithms. \N\NThey introduce a novel class of factorizations designed to minimize communication cost in distributed systems by decomposing \( J \) into a finite product of sparse matrices. The \textit{Hierarchically Banded (HB) Factorization} expresses \( J \) as \( J = J_0 A J_0 \), where \( J_0 \) models intra-cluster communication and \( A \) models sparse inter-cluster interactions. Two variants are developed: the \textit{Reduced HB (RHB)} factorization minimizes the number of nonzeros in \( A \), and the \textit{Doubly Stochastic HB (DSHB)} factorization ensures that \( A \) is symmetric and doubly stochastic. The authors also propose a \textit{Sequential Doubly Stochastic (SDS)} factorization, in which \( J \) is expressed as a product of symmetric, doubly stochastic matrices, supporting one-peer-per-round communication schemes. The paper presents detailed algorithms and theoretical guarantees for constructing these factorizations for arbitrary matrix sizes, and demonstrates their applicability to decentralized averaging and optimization in hierarchical computing environments. These contributions provide practical tools for reducing communication overhead while maintaining convergence guarantees in distributed algorithms.

Cites work

• \(g\)-circulant solutions to the (0,1) matrix equation \(A^m=J_n\)
• Binary factorizations of the matrix of all ones
• Central groupoids, central digraphs, and zero-one matrices \(A\) satisfying \(A^{2}=J\).
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• Introduction to hierarchical matrices with applications.
• On the convergence of decentralized gradient descent
• On the g-circulant solutions to the matrix equation A^ m= J. II
• On the g-circulant solutions to the matrix equation \(A^m=\lambda J\)
• Optimal strategies in the average consensus problem
• The g-circulant solutions of \(A^ m=\lambda J\)

This page was built for publication: Sparse factorization of the square all-ones matrix of arbitrary order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7016668)