Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1157.90347
Xiao, Lin; Boyd, Stephen
Fast linear iterations for distributed averaging. (English)
[J] Syst. Control Lett. 53, No. 1, 65-78 (2004). ISSN 0167-6911

Summary: We consider the problem of finding a linear iteration that yields distributed averaging consensus over a network, i.e., that asymptotically computes the average of some initial values given at the nodes. When the iteration is assumed symmetric, the problem of finding the fastest converging linear iteration can be cast as a semidefinite program, and therefore efficiently and globally solved. These optimal linear iterations are often substantially faster than several common heuristics that are based on the Laplacian of the associated graph.We show how problem structure can be exploited to speed up interior-point methods for solving the fastest distributed linear iteration problem, for networks with up to a thousand or so edges. We also describe a simple subgradient method that handles far larger problems, with up to 100 000 edges. We give several extensions and variations on the basic problem.

MSC 2000:: *90B10 Flows in networks
90C22 Semidefinite programming
90C35 Network programming

Keywords: Distributed consensus; Linear system; Spectral radius; Graph Laplacian; Semidefinite programming

Cited in: Zbl 1166.93018

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]