Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.00979 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918152501198848 |
|---|---|
| author | Koopman, Thomas Bisseling, Rob H. Scholz, Sven-Bodo |
| author_facet | Koopman, Thomas Bisseling, Rob H. Scholz, Sven-Bodo |
| contents | We show that a particular class of parallel algorithm for linear functions can be straightforwardly generalized to a parallel algorithm of their tensor product. The central idea is to take a model of parallel algorithms -- Bulk Synchronous Parallel (BSP) -- that decomposes parallel algorithms into so-called supersteps that are one of two types: a computation superstep that only does local computations, or a communication superstep that only communicates between processors. We connect each type of supersteps to linear algebra with functors. Each superstep in isolation is simple enough to compute their tensor product in Vect with well-known techniques of linear algebra. We then individually translate the tensor product of supersteps back to the language of BSP algorithms. The functoriality of the tensor product allows us to compose the supersteps back into a BSP algorithm for the tensor product of the original function. We state the recipe for creating these new algorithms with only a minimal amount of algebra, so that it can be applied without understanding the category-theoretic details. We have previously used this to derive an efficient algorithm for the higher-dimensional Discrete Fourier Transform, which we use as an example throughout this paper. We also derive a parallel algorithm for the Discrete Cosine Transform to demonstrate the generality of our approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_00979 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Category Theory for Supercomputing: The Tensor Product of Linear BSP Algorithms Koopman, Thomas Bisseling, Rob H. Scholz, Sven-Bodo Category Theory 18A99, 68W10, 15A69 We show that a particular class of parallel algorithm for linear functions can be straightforwardly generalized to a parallel algorithm of their tensor product. The central idea is to take a model of parallel algorithms -- Bulk Synchronous Parallel (BSP) -- that decomposes parallel algorithms into so-called supersteps that are one of two types: a computation superstep that only does local computations, or a communication superstep that only communicates between processors. We connect each type of supersteps to linear algebra with functors. Each superstep in isolation is simple enough to compute their tensor product in Vect with well-known techniques of linear algebra. We then individually translate the tensor product of supersteps back to the language of BSP algorithms. The functoriality of the tensor product allows us to compose the supersteps back into a BSP algorithm for the tensor product of the original function. We state the recipe for creating these new algorithms with only a minimal amount of algebra, so that it can be applied without understanding the category-theoretic details. We have previously used this to derive an efficient algorithm for the higher-dimensional Discrete Fourier Transform, which we use as an example throughout this paper. We also derive a parallel algorithm for the Discrete Cosine Transform to demonstrate the generality of our approach. |
| title | Category Theory for Supercomputing: The Tensor Product of Linear BSP Algorithms |
| topic | Category Theory 18A99, 68W10, 15A69 |
| url | https://arxiv.org/abs/2510.00979 |