Department of Computer Science, University of Waterloo, 1992. Techcnical Report CS-92-37.
We present a literature review on the algebraic path problem and describe different sequential and systolic algorithms for solving this problem.
A systolic algorithm is a parallel algorithm where computations are performed by a planar mesh of connected processors. All processors perform the same algorithm and every processor exchanges data only with its neighbours.
The algebraic path problem is the problem of performing a special unary operation, called closure, over a square matrix, whose entries are elements of a semiring. This problem generalizes some matrix problems (such as computing the inverse of a real-valued matrix), graph problems (e.g. transitive closure and reduction, shortest path, the stochastic communication network problem), and regular language problems (e.g. the proof of the correspondence between regular expressions and finite automata).
We describe two different approaches to an algebraic path problem and four special cases of the general problem: computing the closure of a matrix over a Dijkstra semiring, the transitive closure problem, the shortest path problem, and computing the inverse of a real-valued matrix. For each problem we present both sequential and systolic algorithms. Also, we describe a history of sequential and systolic solutions of each problem.