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

DOI10.1007/BF02253318zbMath0562.68056MaRDI QIDQ1057068

Günter Rote

Publication date: 1985

Published in: Computing (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmsmatrix inversionalgebraic path problemtransitive closure of a relationGauß-Jordan eliminationhexagonal systolic arrayparallelizationspartially complete semiringspipelining delayshortest distances in a networksystolic array algorithmWarshall- Floyd algorithm

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Semirings (16Y60) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (16)

PROCESSOR-TIME-OPTIMAL SYSTOLIC ARRAYS ⋮ Max-plus definite matrix closures and their eigenspaces ⋮ Universal algorithms for solving the matrix Bellman equations over semirings ⋮ Max-linear models on directed acyclic graphs ⋮ Matrix inversion by systolic rank annihilation ⋮ Generalized semigroup semirings which are zero-divisor-free or multiplicatively left-cancellative ⋮ An incremental mechanical development of systolic solutions to the algebraic path problem ⋮ The Markov chain tree theorem in commutative semirings and the state reduction algorithm in commutative semifields ⋮ Towards systolizing compilation ⋮ An orthogonal systolic array for the algebraic path problem ⋮ Optimal systolic array algorithms for tensor product ⋮ Quantitative \(\mu\)-calculus and CTL defined over constraint semirings ⋮ Universal numerical algorithms and their software implementation ⋮ Computing transitive closure on systolic arrays of fixed size ⋮ Z-matrix equations in max-algebra, nonnegative linear algebra and other semirings ⋮ Geometrical tools to map systems of affine recurrence equations on regular arrays

Uses Software

• Algorithm 97

Cites Work

• Algebraic structures for transitive closure
• A Unified Approach to Path Problems
• Regular Algebra Applied to Path-finding Problems
• An Algebra for Network Routing Problems
• A Theorem on Boolean Matrices
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion)