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.
| Type: | Proceedings paper |
|---|---|
| Title: | The Cost of Compositionality A High-Performance Implementation of String Diagram Composition |
| Event: | 4th International Conference on Applied Category Theory (ACT 2021) |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.4204/EPTCS.372.19 |
| Publisher version: | https://cgi.cse.unsw.edu.au/~eptcs/paper.cgi?ACT20... |
| Language: | English |
| Additional information: | © P. Wilson & F. Zanasi This work is licensed under the Creative Commons Attribution License |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10161859 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
