Distributed Solution of Large-Scale Linear Systems Via Accelerated Projection-Based Consensus
Abstract
Solving a large-scale system of linear equations is a key step at the heart of many algorithms in scientific computing, machine learning, and beyond. When the problem dimension is large, computational and/or memory constraints make it desirable, or even necessary, to perform the task in a distributed fashion. In this paper, we consider a common scenario in which a taskmaster intends to solve a large-scale system of linear equations by distributing subsets of the equations among a number of computing machines/cores. We propose a new algorithm called Accelerated Projection-based Consensus (APC) for this problem. The convergence behavior of the proposed algorithm is analyzed in detail and analytically shown to compare favorably with the convergence rate of alternative distributed methods, namely distributed gradient descent, distributed versions of Nesterov's accelerated gradient descent and heavy-ball method, the block Cimmino method, and ADMM. On randomly chosen linear systems, as well as on real-world data sets, the proposed method offers significant speed-up relative to all the aforementioned methods.
Additional Information
© 2018 IEEE.Attached Files
Submitted - 1708.01413
Files
Name | Size | Download all |
---|---|---|
md5:ae2a388c29e4b4d6ba55e9be08b9aa03
|
520.5 kB | Download |
Additional details
- Eprint ID
- 89783
- DOI
- 10.1109/ICASSP.2018.8462630
- Resolver ID
- CaltechAUTHORS:20180920-110215437
- Created
-
2018-09-20Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field