cs.LGNov 7, 2026

Representing Tensors as Compositions for Efficient Computation on Sparse and Structured Data

Authors: Valérian Rey, Praneth Paruchuri

Organizations: SimplexLab

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We propose a new mathematical formalism in which all kinds of tensors and of operations on those tensors are represented as simple function compositions. Tensors are functions from indices to values. An element-wise operation (e.g. an activation function) is a composition with a function applied to values; re-indexing (e.g. reshape, transposition) is a composition with a function applied to indices; and a reduction is a composition with both an index function, mapping each index to several indices, and a reduction operation (e.g. product, sum, max). Combined with tensor stacking, these compositions can represent most interesting kinds of tensors (e.g. dense, jagged, all kinds of sparsity patterns, matrix factorizations), as well as lazy versions of almost every operation available in modern tensor computation frameworks, including einsums between tensors of any kind. Identities between compositions can then be used to rewrite such expressions into equivalent ones, without evaluating them. For instance, the product of two sparse matrices can be rewritten so that only products between non-zero values are computed, turning a sparse problem into a dense one. Using this algebra as the intermediate representation of a tensor computation engine would shift the focus from defining operations on tensors (e.g. einsum between sparse tensors) to defining an algebra on index functions. This should reduce the codebase complexity from O(mn2)\mathcal{O}(mn^2), with mm the number of binary operations between tensors and nn the number of tensor types, to O(m+k2)\mathcal{O}(m + k^2), with kk the number of types of index functions. A draft implementation of a tensor computation framework based on this algebra is publicly available.

Figures & tables

Figure 1: Compositions with a function: on values for element-wise operations (a), and on indices for re-indexings (b–e).
Figure 2: Reduction tensors. The index function maps each index to a multiset of indices of the underlying tensor, whose values, gathered by Uˉ∘ψ\bar{U}\circ\psi , are then reduced.
Figure 3: Sparse matrices, represented as sum tensors.
Figure 4: Stacking, and element-wise operations between several tensors, represented as reductions over a stack.
Figure 5: Dense matrix multiplication C=ABC=AB , represented as an einsum. In each subfigure, the result is the underlying tensor of the next one. This illustrates the definition, not an actual implementation.
Figure 6: Element-wise product A1⊙A2A_{1}\odot A_{2} of a diagonal matrix A1=Σ∘U1‾∘ψ1A_{1}=\Sigma\circ\overline{U_{1}}\circ\psi_{1} and an anti-diagonal matrix A2=Σ∘U2‾∘ψ2A_{2}=\Sigma\circ\overline{U_{2}}\circ\psi_{2} (Theorem 2 ). Only 11 product is computed, instead of 99 . Subfigure (a) shows the inputs, (b) computes the product YY from the stack of their stored values, and (c) is the right-hand side of Equation ( 10 ), whose underlying tensor is the result of (b). The stored values at the index of Q{\mathcal{Q}} are in red, and those outside of Q{\mathcal{Q}} , which are not needed, are gray.
Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

PyTorch codeTensor
torch.zeros(M, N)Σ∘Uˉ∘ψ:[M]×[N]→R\Sigma\circ\bar{U}\circ\psi:[M]\times[N]\to{\mathbb{R}} U:∅→RU:\emptyset\to{\mathbb{R}} ψ(v)={ ⁣ ⁣{} ⁣ ⁣}\psi({\boldsymbol{v}})=\{\!\!\{\}\!\!\}
torch.ones(M, N)Π∘Uˉ∘ψ:[M]×[N]→R\Pi\circ\bar{U}\circ\psi:[M]\times[N]\to{\mathbb{R}} U:∅→RU:\emptyset\to{\mathbb{R}} ψ(v)={ ⁣ ⁣{} ⁣ ⁣}\psi({\boldsymbol{v}})=\{\!\!\{\}\!\!\}
torch.tanh(A) A.shape: (M, N)tanh⁡∘A:[M]×[N]→]−1,1[\tanh{}\circ A:[M]\times[N]\to{]}{-1},1{[} tanh⁡:R→]−1,1[\tanh:{\mathbb{R}}\to{]}{-1},1{[}
torch.transpose(A, 0, 1) A.shape: (M, N)A∘ρ:[N]×[M]→RA\circ\rho:[N]\times[M]\to{\mathbb{R}} ρ(n,m)=(m,n)\rho(n,m)=(m,n)
A.reshape(M, N) A.shape: (M*N,)A∘ρ:[M]×[N]→RA\circ\rho:[M]\times[N]\to{\mathbb{R}} ρ(m,n)=N(m−1)+n\rho(m,n)=N(m-1)+n
A[:, j] A.shape: (M, N)A∘ρ:[M]→RA\circ\rho:[M]\to{\mathbb{R}} ρ(m)=(m,j+1)\rho(m)=(m,j+1)
Appendix
Table 1: Translation of common PyTorch operations into our algebra of compositions.

Explore similar work

CardsList

  1. Automated Tensor-Relational Decomposition for Large-Scale Sparse Tensor Computation

    Mar 9, 2026Yuxin Tang, Zhiyuan Xin, Zhimin Ding +4High-Performance Computing

    Rice University Houston, Texas, USA

  2. Lightweight Representation Learning for Low Tucker Rank Tensors

    Oct 31, 2026Hiroki Hasegawa, Yukihiko OkadaLow-Rank Representation LearningRepresentation Learning

    Graduate School of Science and Technology, University of Tsukuba, Tsukuba, Japan · Center for Artificial Intelligence Research, Tsukuba Institute for Advanced Research, University of Tsukuba, Tsukuba, Japan · Institute of Systems and Information Engineering, University of Tsukuba, Tsukuba, Japan

  3. It's All Just Vectorization: einx, a Universal Notation for Tensor Operations

    Jul 30, 2026Florian Fervers, Sebastian Bullinger, Christoph Bodensteiner +1

    Fraunhofer IOSB