Günter Rote:

A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion)

  1. A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion).
    Computing 34 (1985), 191–219, (Zentralblatt für Mathematik 546.68047 (562.68056); Mathematical Reviews #86k:68046). doi:10.1007/BF02253318 This is a shortened and extended version of the report 3 below.
  2. A systolic array algorithm for the algebraic path problem.
    Diplomarbeit (Master's thesis), February 1985. Supervisor: Prof. Dr. R. E. Burkard. This is a corrected version of 3.
  3. A systolic array for the algebraic path problem (which includes the inverse of a matrix and shortest distances in a graph).
    Rechenzentrum Graz, Bericht 101, 1984, 69 pages.

Abstract

It is shown how the Gauß-Jordan elimination algorithm for the Algebraic Path Problem can be implemented on a hexagonal systolic array of a quadratic number of simple processors in linear time. Special instances of this general algorithm include parallelizations of the Warshall-Floyd algorithm, which computes shortest distances in a graph or the transitive closure of a relation, and of the Gauß-Jordan elimination algorithm for computing the inverse of a real matrix.

  scanned TIFF file   Postscript file gzipped   pdf file   free PDF view@Springer
other papers about this subject
Last update: September 14, 2001.