NDLI: A Distributed Algorithm for Solving a Linear Algebraic Equation

Content Provider	IEEE Xplore Digital Library
Author	Shaoshuai Mou Ji Liu Morse, A.S.
Copyright Year	1963
Abstract	A distributed algorithm is described for solving a linear algebraic equation of the form Ax = b assuming the equation has at least one solution. The equation is simultaneously solved by m agents assuming each agent knows only a subset of the rows of the partitioned matrix [A b], the current estimates of the equation's solution generated by its neighbors, and nothing more. Each agent recursively updates its estimate by utilizing the current estimates generated by each of its neighbors. Neighbor relations are characterized by a time-dependent directed graph N(t) whose vertices correspond to agents and whose arcs depict neighbor relations. It is shown that for any matrix A for which the equation has a solution and any sequence of “repeatedly jointly strongly connected graphs” N(t), t = 1, 2, ..., the algorithm causes all agents' estimates to converge exponentially fast to the same solution to Ax = b. It is also shown that, under mild assumptions, the neighbor graph sequence must actually be repeatedly jointly strongly connected if exponential convergence is to be assured. A worst case convergence rate bound is derived for the case when Ax = b has a unique solution. It is demonstrated that with minor modification, the algorithm can track the solution to Ax = b, even if A and b are changing with time, provided the rates of change of A and bare sufficiently small. It is also shown that in the absence of communication delays, exponential convergence to a solution occurs even if the times at which each agent updates its estimates are not synchronized with the update times of its neighbors. A modification of the algorithm is outlined which enables it to obtain a least squares solution to Ax = b in a distributed manner, even if Ax = b does not have a solution.
Sponsorship	IEEE Control Systems Society
Starting Page	2863
Ending Page	2878
Page Count	16
File Size	395705
File Format	PDF
ISSN	00189286
Volume Number	60
Issue Number	11
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Facsimile Conferences Meetings Distributed algorithms Equations Open Access Materials multi-agent systems Autonomous agents distributed algorithms
Content Type	Text
Resource Type	Article
Subject	Control and Systems Engineering Electrical and Electronic Engineering Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Consensus Computation in Unreliable Networks: A System Theoretic Approach

Event-Based Second-Order Consensus Control for Multi-Agent Systems via Synchronous Periodic Event Detection

Constrained Consensus and Optimization in Multi-Agent Networks

A Class of Bounded Distributed Control Strategies for Connectivity Preservation in Multi-Agent Systems

Cooperative Output Regulation of Linear Multi-Agent Systems

Connectivity Preservation in Nonholonomic Multi-Agent Systems: A Bounded Distributed Control Strategy

A Distributed Algorithm for Solving Linear Algebraic Equations Over Random Networks

Distributed Consensus Control of Multi-Agent Systems With Higher Order Agent Dynamics and Dynamically Changing Directed Interaction Topologies

Comments on “Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules”

A Distributed Algorithm for Solving a Linear Algebraic Equation

Similar Documents

Consensus Computation in Unreliable Networks: A System Theoretic Approach

Event-Based Second-Order Consensus Control for Multi-Agent Systems via Synchronous Periodic Event Detection

Constrained Consensus and Optimization in Multi-Agent Networks

A Class of Bounded Distributed Control Strategies for Connectivity Preservation in Multi-Agent Systems

Cooperative Output Regulation of Linear Multi-Agent Systems

Connectivity Preservation in Nonholonomic Multi-Agent Systems: A Bounded Distributed Control Strategy

A Distributed Algorithm for Solving Linear Algebraic Equations Over Random Networks

Distributed Consensus Control of Multi-Agent Systems With Higher Order Agent Dynamics and Dynamically Changing Directed Interaction Topologies

Comments on “Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules”

A Distributed Algorithm for Solving a Linear Algebraic Equation