A constant time parallel algorithm for the triangularization of a sparse matrix using CD-PARBS Wankar, RajeevChaudhari, N. S.Fehr, ElfriedeUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
A constant time parallel algorithm for the triangularization of a sparse matrix using CD-PARBS
Chaudhari, N. S.
Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; 00,05
PARBS; CD-PARBS; dag.
004 Data processing and Computer science
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.
If your browser can't open the file, please download the file first and then open it