Implementation of some concurrent algorithms for matrix factorization

J. J. Dongarra; A. H. Sameh; D. C. Sorensen

doi:10.1016/0167-8191(86)90004-9

Implementation of some concurrent algorithms for matrix factorization

J. J. Dongarra, A. H. Sameh, D. C. Sorensen

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

23 Scopus citations

Abstract

Three parallel algorithms for computing the QR-factorization of a matrix are presented. The discussion is primarily concerned with implementation of these algorithms on a computer that supports tightly coupled parallel processes sharing a large common memory. The three algorithms are a Householder method based upon high-level modules, a Windowed Householder method that avoids fork-join synchronization, and a Pipelined Givens method that is a variant of the data-flow type algorithms offering large enough granularity to mask synchronization costs. Numerical experiments were conducted on the Denelcor HEP computer. The computational results indicate that the Pipelined Givens method is preferred and that this is primarily due to the number of array references required by the various algorithms.

Original language	English
Pages (from-to)	25-34
Number of pages	10
Journal	Parallel Computing
Volume	3
Issue number	1
DOIs	https://doi.org/10.1016/0167-8191(86)90004-9
State	Published - Mar 1986
Externally published	Yes

Funding

* An earlier version of this paper appeared in the proceedings of the Eighteenth Annual Hawaii International Conference on System Sciences in January 1985. ** Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under Contract g-31-109-Eng-33.

Funders	Funder number
Office of Energy Research
U.S. Department of Energy	g-31-109-Eng-33

Keywords

Denelcor HEP
performance analysis

Access to Document

10.1016/0167-8191(86)90004-9

Cite this

@article{07dc48ab322e469591a855fa660ab72c,

title = "Implementation of some concurrent algorithms for matrix factorization",

abstract = "Three parallel algorithms for computing the QR-factorization of a matrix are presented. The discussion is primarily concerned with implementation of these algorithms on a computer that supports tightly coupled parallel processes sharing a large common memory. The three algorithms are a Householder method based upon high-level modules, a Windowed Householder method that avoids fork-join synchronization, and a Pipelined Givens method that is a variant of the data-flow type algorithms offering large enough granularity to mask synchronization costs. Numerical experiments were conducted on the Denelcor HEP computer. The computational results indicate that the Pipelined Givens method is preferred and that this is primarily due to the number of array references required by the various algorithms.",

keywords = "Denelcor HEP, performance analysis",

author = "Dongarra, {J. J.} and Sameh, {A. H.} and Sorensen, {D. C.}",

year = "1986",

month = mar,

doi = "10.1016/0167-8191(86)90004-9",

language = "English",

volume = "3",

pages = "25--34",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Implementation of some concurrent algorithms for matrix factorization

AU - Dongarra, J. J.

AU - Sameh, A. H.

AU - Sorensen, D. C.

PY - 1986/3

Y1 - 1986/3

N2 - Three parallel algorithms for computing the QR-factorization of a matrix are presented. The discussion is primarily concerned with implementation of these algorithms on a computer that supports tightly coupled parallel processes sharing a large common memory. The three algorithms are a Householder method based upon high-level modules, a Windowed Householder method that avoids fork-join synchronization, and a Pipelined Givens method that is a variant of the data-flow type algorithms offering large enough granularity to mask synchronization costs. Numerical experiments were conducted on the Denelcor HEP computer. The computational results indicate that the Pipelined Givens method is preferred and that this is primarily due to the number of array references required by the various algorithms.

AB - Three parallel algorithms for computing the QR-factorization of a matrix are presented. The discussion is primarily concerned with implementation of these algorithms on a computer that supports tightly coupled parallel processes sharing a large common memory. The three algorithms are a Householder method based upon high-level modules, a Windowed Householder method that avoids fork-join synchronization, and a Pipelined Givens method that is a variant of the data-flow type algorithms offering large enough granularity to mask synchronization costs. Numerical experiments were conducted on the Denelcor HEP computer. The computational results indicate that the Pipelined Givens method is preferred and that this is primarily due to the number of array references required by the various algorithms.

KW - Denelcor HEP

KW - performance analysis

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

U2 - 10.1016/0167-8191(86)90004-9

DO - 10.1016/0167-8191(86)90004-9

M3 - Article

AN - SCOPUS:0022673955

SN - 0167-8191

VL - 3

SP - 25

EP - 34

JO - Parallel Computing

JF - Parallel Computing

IS - 1

ER -

Implementation of some concurrent algorithms for matrix factorization

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this