A new efficient parallelization strategy for the \(QR\) algorithm (Q1315915)

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.