Dokumentenserver der Freien Universität Berlin

Objekt-Metadaten

A constant time parallel algorithm for the triangularization of a sparse matrix using CD-PARBS
Wankar, Rajeev ;  Chaudhari, N. S. ;  Fehr, Elfriede ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

Main titleA constant time parallel algorithm for the triangularization of a sparse matrix using CD-PARBS
AuthorWankar, Rajeev
AuthorChaudhari, N. S.
AuthorFehr, Elfriede
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages18 S.
Series Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]00,05
KeywordsPARBS; CD-PARBS; dag.
Classification (DDC)004 Data processing and Computer science
AbstractAn 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.
Documents
PDF-Datei
If your browser can't open the file, please download the file first and then open it
 
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication2000
Type of documentMaps
LanguageEnglish
Terms of use/Rights Nutzungsbedingungen
Created at2009-04-28 : 09:27:20
Last changed2014-01-23 : 04:21:24
 
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001676
Statistics
 

LOADING...