Parallel Computations in *-Semirings

*-semirings are algebraic structures that provide a unified approach to several problem classes in computer science and operations research. For example, *-semirings can be used to describe the algebra related to regular expressions, graph-theoretical path problems, and compiled-code optimization. The theory of matrices over *-semirings has a number of similarities to linear algebra. For example, eliminants and asterates (closures) behave analogously in many ways to determinants and matrix inverses. Matrix computations over *-semirings are interesting in their own right as well as because of their potential applications to linear algebra. This paper uses the eliminant formulation of *-semiring properties to derive parallel algorithms for three kinds of problems involving matrices over *-semirings: eliminant computation, solution of linear systems over *-semirings, and matrix asteration. The algorithms discussed allow the most general computations in which the asteration operation in the base *-semiring is assumed to be non-trivial, and the matrices are assumed to be dense and without any particular structure.