Wilson, PW; Zanasi, F; (2021) The Cost of Compositionality: A High-Performance Implementation of String Diagram Composition. In: Applied Category Theory 2021. (pp. p. 59). Computer Laboratory of the University of Cambridge: Cambridge, UK.

Preview

Text 2105.09257.pdf - Accepted Version Download (235kB) | 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 fewer 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 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 CSVJSONXML

Download activity - last 12 months

Export as XMLJSONCSV

Downloads by country - last 12 months

Export as XMLJSONCSV

Archive Staff Only

View Item