Accelerating the distributed Kaczmarz algorithm by strong over-relaxation

Riley Borgard; Steven N. Harding; Haley Duba; Chloe Makdad; Jay Mayfield; Randal Tuggle; Eric S. Weber

doi:10.1016/j.laa.2020.10.035

Accelerating the distributed Kaczmarz algorithm by strong over-relaxation

Riley Borgard, Steven N. Harding, Haley Duba, Chloe Makdad, Jay Mayfield, Randal Tuggle, Eric S. Weber

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

The distributed Kaczmarz algorithm is an adaptation of the standard Kaczmarz algorithm to the situation in which data is distributed throughout a network represented by a tree. We isolate substructures of the network and study convergence of the distributed Kaczmarz algorithm for relatively large relaxation parameters associated to these substructures. If the system is consistent, then the algorithm converges to the solution of minimal norm; however, if the system is inconsistent, then the algorithm converges to an approximated least-squares solution that is dependent on the parameters and the network topology. We show that the relaxation parameters may be larger than the standard upper-bound in literature in this context and provide numerical experiments to support our results.

Original language	English
Pages (from-to)	334-355
Number of pages	22
Journal	Linear Algebra and Its Applications
Volume	611
DOIs	https://doi.org/10.1016/j.laa.2020.10.035
State	Published - Feb 15 2021
Externally published	Yes

Funding

Riley Borgard, Haley Duba, Chloe Makdad, Jay Mayfield, and Randal Tuggle were supported by the National Science Foundation through the REU award # 1457443 . Steven Harding and Eric Weber were supported by the National Science Foundation and the National Geospatial-Intelligence Agency under award # 1830254 . Eric Weber was also supported under award #1934884.

Funders	Funder number
National Science Foundation
Directorate for Mathematical and Physical Sciences	1830254, 1457443
National Geospatial-Intelligence Agency	1934884

Keywords

Kaczmarz algorithm

Access to Document

10.1016/j.laa.2020.10.035

Cite this

@article{95a9a919ab3948a98eb0290907e284be,

title = "Accelerating the distributed Kaczmarz algorithm by strong over-relaxation",

abstract = "The distributed Kaczmarz algorithm is an adaptation of the standard Kaczmarz algorithm to the situation in which data is distributed throughout a network represented by a tree. We isolate substructures of the network and study convergence of the distributed Kaczmarz algorithm for relatively large relaxation parameters associated to these substructures. If the system is consistent, then the algorithm converges to the solution of minimal norm; however, if the system is inconsistent, then the algorithm converges to an approximated least-squares solution that is dependent on the parameters and the network topology. We show that the relaxation parameters may be larger than the standard upper-bound in literature in this context and provide numerical experiments to support our results.",

keywords = "Kaczmarz algorithm",

author = "Riley Borgard and Harding, {Steven N.} and Haley Duba and Chloe Makdad and Jay Mayfield and Randal Tuggle and Weber, {Eric S.}",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

year = "2021",

month = feb,

day = "15",

doi = "10.1016/j.laa.2020.10.035",

language = "English",

volume = "611",

pages = "334--355",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier",

}

TY - JOUR

T1 - Accelerating the distributed Kaczmarz algorithm by strong over-relaxation

AU - Borgard, Riley

AU - Harding, Steven N.

AU - Duba, Haley

AU - Makdad, Chloe

AU - Mayfield, Jay

AU - Tuggle, Randal

AU - Weber, Eric S.

PY - 2021/2/15

Y1 - 2021/2/15

N2 - The distributed Kaczmarz algorithm is an adaptation of the standard Kaczmarz algorithm to the situation in which data is distributed throughout a network represented by a tree. We isolate substructures of the network and study convergence of the distributed Kaczmarz algorithm for relatively large relaxation parameters associated to these substructures. If the system is consistent, then the algorithm converges to the solution of minimal norm; however, if the system is inconsistent, then the algorithm converges to an approximated least-squares solution that is dependent on the parameters and the network topology. We show that the relaxation parameters may be larger than the standard upper-bound in literature in this context and provide numerical experiments to support our results.

AB - The distributed Kaczmarz algorithm is an adaptation of the standard Kaczmarz algorithm to the situation in which data is distributed throughout a network represented by a tree. We isolate substructures of the network and study convergence of the distributed Kaczmarz algorithm for relatively large relaxation parameters associated to these substructures. If the system is consistent, then the algorithm converges to the solution of minimal norm; however, if the system is inconsistent, then the algorithm converges to an approximated least-squares solution that is dependent on the parameters and the network topology. We show that the relaxation parameters may be larger than the standard upper-bound in literature in this context and provide numerical experiments to support our results.

KW - Kaczmarz algorithm

UR - http://www.scopus.com/inward/record.url?scp=85095807182&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2020.10.035

DO - 10.1016/j.laa.2020.10.035

M3 - Article

AN - SCOPUS:85095807182

SN - 0024-3795

VL - 611

SP - 334

EP - 355

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

Accelerating the distributed Kaczmarz algorithm by strong over-relaxation

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this