## A survey of sequential and systolic algorithms
for the algebraic path problem

### Eugene Fink

Department of Computer Science, University of Waterloo, 1992.
Techcnical Report CS-92-37.

### Abstract

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.