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

HaupttitelA constant time parallel algorithm for the triangularization of a sparse matrix using CD-PARBS
AutorWankar, Rajeev
AutorChaudhari, N. S.
AutorFehr, Elfriede
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl18 S.
Schriftenreihe Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]00,05
Freie SchlagwörterPARBS; CD-PARBS; dag.
DDC004 Datenverarbeitung; Informatik
ZusammenfassungAn 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.
Dokumente
PDF-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutInstitut für Informatik
Erscheinungsjahr2000
Dokumententyp/-SammlungenKarten
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am28.04.2009 - 09:27:20
Letzte Änderung23.01.2014 - 16:21:24
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001676
Zugriffsstatistik
 

LOADING...