• DocumentCode
    1364011
  • Title

    A parallel algorithm for solving sparse triangular systems

  • Author

    Ho, Chin-wen ; Lee, R.C.T.

  • Author_Institution
    Inst. of Comput. & Decision Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
  • Volume
    39
  • Issue
    6
  • fYear
    1990
  • fDate
    6/1/1990 12:00:00 AM
  • Firstpage
    848
  • Lastpage
    852
  • Abstract
    A fast parallel algorithm, which is generalized from the parallel algorithms for solving banded linear systems, is proposed to solve sparse triangular systems. The original problem is transformed into a directed graph. The solving procedure then consists of eliminating edges in this graph. The worst-case time-complexity of this parallel algorithm is O(log2n) where n is the size of the coefficient matrix. When the coefficient matrix is a triangular banded matrix with bandwidth m, then the time-complexity of the algorithm is O(log(m)×log(n))
  • Keywords
    computational complexity; directed graphs; parallel algorithms; banded linear systems; coefficient matrix; directed graph; parallel algorithm; sparse triangular systems; triangular banded matrix; worst-case time-complexity; Bandwidth; Computational modeling; Concurrent computing; Equations; Linear systems; Multiprocessing systems; Parallel algorithms; Phase change random access memory; Processor scheduling; Sparse matrices;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/12.53610
  • Filename
    53610
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1364011