A new efficient parallelization strategy for the QR algorithm

DOI10.1016/0167-8191(94)90112-0MaRDI QIDQ1315915zbMATH OpenOpenAlexFDO

Authors Thomas Schreiber, Fridolin Hofmann, Peter T. Otto

Publication date 31 July 1994

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(94)90112-0

zbMATH Keywords

\(QR\) algorithmcyclic reductionsdivide and conquer strategyeigenvalueseigenvectorsmultiprocessing systemsparallel algorithmparallelizationteam mappingtridiagonal Hermitian matrix

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Parallel numerical computation (65Y05)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 27309
• scientific article; zbMATH DE number 833714
• scientific article; zbMATH DE number 1330403
• A fast and stable parallel QR algorithm for symmetric tridiagonal matrices
• Parallelizing the QR Algorithm for the Unsymmetric Algebraic Eigenvalue Problem: Myths and Reality

Cited in

(6)

• Gaussian quadrature for matrix valued functions on the real line
• Algorithm 953: Parallel library software for the multishift QR algorithm with aggressive early deflation
• scientific article; zbMATH DE number 1304344 (Why is no real title available?)
• Evaluating products of matrix pencils and collapsing matrix products
• Improved QMRCGSTAB method in distributed parallel environments
• A parallel implementation of the QR-algorithm

This page was built for publication: A new efficient parallelization strategy for the \(QR\) algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1315915)