• DocumentCode
    961658
  • Title

    A Parallel QR Algorithm for Symmetric Tridiagonal Matrices

  • Author

    Sameh, Ahmed H. ; Kuck, David J

  • Author_Institution
    Department of Computer Science and the Center for Advanced Computation, University of Illinois, Urbana, IL 61801.
  • Issue
    2
  • fYear
    1977
  • Firstpage
    147
  • Lastpage
    153
  • Abstract
    We show that if the size of the tridiagonal matrix in any given iteration is n, then the parallel QR algorithm requires 0(log2n) steps with 0(n) processors per iteration and no square roots. This results in a speedup of 0(n/log2n) over the sequential algorithm with an efficiency of 0(1/log2n). We also give an error analysis of the parallel triangular system solvers used in each iteration.
  • Keywords
    Arithmetic; Computer errors; Concurrent computing; Eigenvalues and eigenfunctions; Error analysis; Hardware; Parallel algorithms; Parallel processing; Software design; Symmetric matrices; Error analysis; Givens reduction; parallelism; recurrence relations; triangular systems;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/TC.1977.5009293
  • Filename
    5009293
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=961658