Navigation/Menü: Links auf weitere Seiten dieser Website
Objekt-Metadaten
| A constant time parallel algorithm for the triangularization of a sparse matrix using CD-PARBS Wankar, Rajeev |
| Haupttitel | A constant time parallel algorithm for the triangularization of a sparse matrix using CD-PARBS |
| Autor | Wankar, Rajeev; Chaudhari, N. S.; Fehr, Elfriede |
| Seitenzahl | 18 S. |
| Schriftenreihe | Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]00,05 |
| Fachbereich/Einrichtung | FB Mathematik und Informatik |
| Arbeitsbereich/Institut | Institut für Informatik |
| Erscheinungsjahr | 2000 |
| Dokumente | PDF-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
|
| Freie Schlagwörter | PARBS; CD-PARBS; dag. |
| DDC | 004 Datenverarbeitung; Informatik |
| Dokumententyp/-Sammlungen | Report |
| Medientyp/Format | Text |
| 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. |
| Sprache | Englisch |
| Rechte | Nutzungsbedingungen |
| Zugriffstatistik | |
| Statische URL | http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001676 |
| Erstellt am | 28.04.2009 - 11:27:20 |
| Letzte Änderung | 04.04.2013 - 09:33:28 |
