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 algorithms; matrix inversion; algebraic path problem; transitive closure of a relation; Gauß-Jordan elimination; hexagonal systolic array; parallelizations; partially complete semirings; pipelining delay; shortest distances in a network; systolic array algorithm; Warshall- Floyd algorithm

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

16Y60: Semirings

65F05: Direct numerical methods for linear systems and matrix inversion

Related Items

PROCESSOR-TIME-OPTIMAL SYSTOLIC ARRAYS, An incremental mechanical development of systolic solutions to the algebraic path problem, Towards systolizing compilation, Computing transitive closure on systolic arrays of fixed size, Max-plus definite matrix closures and their eigenspaces, Generalized semigroup semirings which are zero-divisor-free or multiplicatively left-cancellative, Geometrical tools to map systems of affine recurrence equations on regular arrays, Universal numerical algorithms and their software implementation, 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, Matrix inversion by systolic rank annihilation

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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