A lower bound on the computational complexity of the QR decomposition on a shared memory SIMD computer

Eric Goles; Marcos Kiwi

doi:10.1016/0167-8191(92)90102-D

A lower bound on the computational complexity of the QR decomposition on a shared memory SIMD computer

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

Abstract

The time complexity of the Greedy algorithm is investigated. This algorithm provides the parallel QR decomposition of a dense rectangular matrix, through Givens rotations, and it is the optimal procedure within the class of parallel algorithms. The study is carried out analyzing the dynamical evolution of the Greedy automation that we introduce. The known lower bounds for the number of steps required by the Greedy algorithm, for the square matrix case, are improved.

Original language	English
Pages (from-to)	345-354
Number of pages	10
Journal	Parallel Computing
Volume	18
Issue number	3
DOIs	https://doi.org/10.1016/0167-8191(92)90102-D
State	Published - Mar 1992
Externally published	Yes

Keywords

QR decomposition
SIMD machine
greedy automation
lower bound
transient time

Access to Document

10.1016/0167-8191(92)90102-D

Cite this

@article{0978bb4751e44c65bed49cbe91b35e35,

title = "A lower bound on the computational complexity of the QR decomposition on a shared memory SIMD computer",

abstract = "The time complexity of the Greedy algorithm is investigated. This algorithm provides the parallel QR decomposition of a dense rectangular matrix, through Givens rotations, and it is the optimal procedure within the class of parallel algorithms. The study is carried out analyzing the dynamical evolution of the Greedy automation that we introduce. The known lower bounds for the number of steps required by the Greedy algorithm, for the square matrix case, are improved.",

keywords = "QR decomposition, SIMD machine, greedy automation, lower bound, transient time",

author = "Eric Goles and Marcos Kiwi",

note = "Funding Information: * This work was supported by Fondo Nacional de Ciencias 1211-91, Chile",

year = "1992",

month = mar,

doi = "10.1016/0167-8191(92)90102-D",

language = "English",

volume = "18",

pages = "345--354",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - A lower bound on the computational complexity of the QR decomposition on a shared memory SIMD computer

AU - Goles, Eric

AU - Kiwi, Marcos

N1 - Funding Information: * This work was supported by Fondo Nacional de Ciencias 1211-91, Chile

PY - 1992/3

Y1 - 1992/3

N2 - The time complexity of the Greedy algorithm is investigated. This algorithm provides the parallel QR decomposition of a dense rectangular matrix, through Givens rotations, and it is the optimal procedure within the class of parallel algorithms. The study is carried out analyzing the dynamical evolution of the Greedy automation that we introduce. The known lower bounds for the number of steps required by the Greedy algorithm, for the square matrix case, are improved.

AB - The time complexity of the Greedy algorithm is investigated. This algorithm provides the parallel QR decomposition of a dense rectangular matrix, through Givens rotations, and it is the optimal procedure within the class of parallel algorithms. The study is carried out analyzing the dynamical evolution of the Greedy automation that we introduce. The known lower bounds for the number of steps required by the Greedy algorithm, for the square matrix case, are improved.

KW - QR decomposition

KW - SIMD machine

KW - greedy automation

KW - lower bound

KW - transient time

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

U2 - 10.1016/0167-8191(92)90102-D

DO - 10.1016/0167-8191(92)90102-D

M3 - Article

AN - SCOPUS:0026825880

SN - 0167-8191

VL - 18

SP - 345

EP - 354

JO - Parallel Computing

JF - Parallel Computing

IS - 3

ER -

A lower bound on the computational complexity of the QR decomposition on a shared memory SIMD computer

Abstract

Keywords

Access to Document

Fingerprint

Cite this