Wilson, P; Zanasi, F; (2022) The Cost of Compositionality A High-Performance Implementation of String Diagram Composition. In: Kishida, Kohei, (ed.) Proceedings of the Fourth International Conference on Applied Category Theory (ACT 2021). (pp. pp. 262-275). Open Publishing Association: Cambridge, UK.

Preview

Text Zanasi_ACT_2021_paper_59.pdf Download (310kB) | Preview

Abstract

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.

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as CSVXMLJSON

Downloads by country - last 12 months

Export as XMLCSVJSON

Archive Staff Only

View Item