Communication-Efficient Distributed Algorithms for Solving Linear Algebraic Equations over Directed Graphs

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    5 Citations (Scopus)

    Abstract

    This paper presents two communication-efficient distributed algorithms for solving linear algebraic equations of the form Ax = b, which has at least one solution, among a network of m> 1 agents. Each agent knows only a subset of the rows of the partitioned matrix [A b] and recursively updates its estimate of a solution by utilizing information received only from its neighbors. Neighbor relations are characterized by a fixed directed graph. The first algorithm aims to reduce communication costs at each iteration, in which each agent broadcasts the entries of its estimate in a cyclic manner, instead of broadcasting the entire vector of its estimate. It is shown that for any strongly connected neighbor graph, the algorithm causes all agents' estimates to converge to the same solution to Ax = b exponentially fast. The second algorithm reduces the vector size of each agent's estimate by exploiting the sparsity of the matrix A. It is shown that the algorithm causes each agent's estimate to converge to a specific part of the same solution to Ax = b corresponding to its own interest exponentially fast for a certain class of directed graphs.

    Original languageEnglish
    Title of host publication2020 59th IEEE Conference on Decision and Control, CDC 2020
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages5360-5365
    Number of pages6
    ISBN (Electronic)9781728174471
    DOIs
    Publication statusPublished - 14 Dec 2020
    Event59th IEEE Conference on Decision and Control, CDC 2020 - Virtual, Jeju Island, Korea, Republic of
    Duration: 14 Dec 202018 Dec 2020

    Publication series

    NameProceedings of the IEEE Conference on Decision and Control
    Volume2020-December
    ISSN (Print)0743-1546
    ISSN (Electronic)2576-2370

    Conference

    Conference59th IEEE Conference on Decision and Control, CDC 2020
    Country/TerritoryKorea, Republic of
    CityVirtual, Jeju Island
    Period14/12/2018/12/20

    Fingerprint

    Dive into the research topics of 'Communication-Efficient Distributed Algorithms for Solving Linear Algebraic Equations over Directed Graphs'. Together they form a unique fingerprint.

    Cite this