Günter Rote:
A systolic array algorithm for the algebraic path problem (shortest paths;
matrix inversion)
-
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.
-
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.
-
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.
Last update: September 14, 2001.