A new efficient parallelization strategy for the \(QR\) algorithm (Q1315915)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new efficient parallelization strategy for the \(QR\) algorithm |
scientific article |
Statements
A new efficient parallelization strategy for the \(QR\) algorithm (English)
0 references
31 July 1994
0 references
The paper presents a new efficient parallelization for loosely-coupled multiprocessing systems, based upon cyclic reductions, applying the \(QR\) algorithm for the calculation of all eigenvalues and all eigenvectors of a tridiagonal Hermitian matrix. A classic solution for generating a parallel algorithm is based upon a divide and conquer strategy. The proposed algorithm does not employ rank- one modifications and establishes a mapping (team mapping) of the rows of \(Q\) onto the existing processes. The computation of the columns of \(R\) is distributed in the same way as the rows of \(Q\). Theorem 3.3 proves that by using cyclic reductions and distributing the computation via team mapping, one gains an asymptotically 100\% efficient parallelization, i.e. the \(QR\) algorithm can be divided into many independent processes as a result of cyclic reductions.
0 references
\(QR\) algorithm
0 references
parallelization
0 references
multiprocessing systems
0 references
cyclic reductions
0 references
eigenvalues
0 references
eigenvectors
0 references
tridiagonal Hermitian matrix
0 references
parallel algorithm
0 references
divide and conquer strategy
0 references
team mapping
0 references