A constant time parallel algorithm for the triangularization of a sparse matrix using CD-PARBS

Abstract

An algorithm for the triangularization of a matrix whose graph is a directed acyclic graph, popularly known as dag, is presented. One of the algorithms for obtaining this special form has been given by Sargent and Westerberg. Their approach is practically good but sequential in nature and cannot be parallelised easily. In this work we present a parallel algorithm which is based on the observation that, if we find the transitive closure matrix of a directed acyclic graph, count the number of entries in each row, sort them in the ascending order of their values and rank them accordingly, we get a lower triangular matrix. We show that all these operations can be done using 3-d CD- PARBS(Complete Directed PARBS) in constant time. The same approach can be used for the block cases, producing the same relabelling as produced by Tarjan’s algorithm, in constant time. To the best of our knowledge, it is the first approach to solve such problems using directed PARBS.