String diagrams are an increasingly popular algebraic language for the analysis of graphical models of computations across different research fields. Whereas string diagrams have been thoroughly studied as semantic structures, much less attention has been given to their algorithmic properties, and efficient implementations of diagrammatic reasoning are almost an unexplored subject. This work intends to be a contribution in such a direction. We introduce a data structure representing string diagrams in terms of adjacency matrices. This encoding has the key advantage of providing simple and efficient algorithms for composition and tensor product of diagrams. We demonstrate its effectiveness by showing that the complexity of the two operations is linear in the size of string diagrams. Also, as our approach is based on basic linear algebraic operations, we can take advantage of heavily optimised implementations, which we use to measure performances of string diagrammatic operations via several benchmarks.
翻译:字符串图是一种越来越受欢迎的代数语言,用于分析不同研究领域计算图的图形模型。字符串图作为语义结构进行了彻底研究,但很少注意它们的算法特性,而有效地实施图表推理几乎是一个尚未探讨的主题。这项工作意在为这个方向作出贡献。我们引入了一种数据结构,用相邻矩阵来代表字符串图。这一编码具有提供简单有效的算法和图表的成份和成份。我们通过显示两个操作的复杂性在字符串图的大小上是线性的,来证明它的有效性。此外,由于我们的方法是以基本的线性平面变形操作为基础,我们可以利用高度优化的操作来测量字符串图操作的性能,我们用这些应用来通过几个基准来衡量字符串图操作的性能。