A lower bound on the computational complexity of the \(QR\) decomposition on a shared memory \(SIMD\) computer (Q1184549)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A lower bound on the computational complexity of the \(QR\) decomposition on a shared memory \(SIMD\) computer |
scientific article; zbMATH DE number 34748
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A lower bound on the computational complexity of the \(QR\) decomposition on a shared memory \(SIMD\) computer |
scientific article; zbMATH DE number 34748 |
Statements
A lower bound on the computational complexity of the \(QR\) decomposition on a shared memory \(SIMD\) computer (English)
0 references
28 June 1992
0 references
Computing the QR decomposition of \(m\times n\)-matrix on a shared memory SIMD computer is considered using the Greedy algorithm. The authors derive the lower bounds for the transient length of the Greedy algorithm, which improve upon the known results. The results are obtained by studying the dynamical evolution of so-called Greedy automaton whose transient length is equivalent to that of the Greedy algorithm.
0 references
time complexity
0 references
Givens rotations
0 references
parallel QR decomposition
0 references
shared memory SIMD computer
0 references
Greedy algorithm
0 references
lower bounds
0 references
Greedy automaton
0 references
0.90306735
0 references
0.8807503
0 references
0.87866527
0 references
0.8780049
0 references
0.86355615
0 references
0.8543811
0 references
0.8496602
0 references
