TY - GEN
T1 - Decentralized computation of effective resistances and acceleration of consensus algorithms
AU - Aybat, Necdet Serhat
AU - Gurbuzbalaban, Mert
N1 - Funding Information:
∗Research of N. S. Aybat was partially supported by NSF grants CMMI-1400217 and CMMI-1635106, and ARO grant W911NF-17-1-0298. †Research of M. Gürbüzbalaban was partially supported by the NSF grant DMS-1723085.
Publisher Copyright:
© 2017 IEEE.
PY - 2018/3/7
Y1 - 2018/3/7
N2 - The effective resistance between a pair of nodes in a weighted undirected graph is defined as the potential difference induced between them when a unit current is injected at the first node and extracted at the second node, treating edge weights as the conductance values of edges. The effective resistance is a key quantity of interest in many applications and fields including solving linear systems, Markov Chains and continuous-time averaging networks. We develop an efficient linearly convergent distributed algorithm for computing effective resistances and demonstrate its performance through numerical studies. We also apply our algorithm to the consensus problem where the aim is to compute the average of node values in a distributed manner. We show that the distributed algorithm we developed for effective resistances can be used to accelerate the convergence of the classical consensus iterations considerably by a factor depending on the network structure.
AB - The effective resistance between a pair of nodes in a weighted undirected graph is defined as the potential difference induced between them when a unit current is injected at the first node and extracted at the second node, treating edge weights as the conductance values of edges. The effective resistance is a key quantity of interest in many applications and fields including solving linear systems, Markov Chains and continuous-time averaging networks. We develop an efficient linearly convergent distributed algorithm for computing effective resistances and demonstrate its performance through numerical studies. We also apply our algorithm to the consensus problem where the aim is to compute the average of node values in a distributed manner. We show that the distributed algorithm we developed for effective resistances can be used to accelerate the convergence of the classical consensus iterations considerably by a factor depending on the network structure.
UR - http://www.scopus.com/inward/record.url?scp=85048130703&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048130703&partnerID=8YFLogxK
U2 - 10.1109/GlobalSIP.2017.8308701
DO - 10.1109/GlobalSIP.2017.8308701
M3 - Conference contribution
AN - SCOPUS:85048130703
T3 - 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings
SP - 538
EP - 542
BT - 2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 5th IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017
Y2 - 14 November 2017 through 16 November 2017
ER -