# The Cost of Compositionality: A High-Performance Implementation of String Diagram Composition

arXiv: https://arxiv.org/abs/2105.09257 · HTML: https://mlsanity.com/paper/2105.09257/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2021.

## Built on by (most cited first, 1 of 1)

- [Categories of Differentiable Polynomial Circuits for Machine Learning](https://mlsanity.com/paper/2203.06430/) (2022)

## Abstract (arXiv)

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.