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

Valérian Rey; Praneth Paruchuri

cs.LGNov 7, 2026

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

Authors: Valérian Rey, Praneth Paruchuri

Organizations: SimplexLab

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 $\mathcal{O}(mn^2)$ , with $m$ the number of binary operations between tensors and $n$ the number of tensor types, to $\mathcal{O}(m + k^2)$ , with $k$ the number of types of index functions. A draft implementation of a tensor computation framework based on this algebra is publicly available.

Figures & tables

Panel of Figure 1 — Figure 1: Compositions with a function: on values for element-wise operations (a), and on indices for re-indexings (b–e).

Panel of Figure 2 — Figure 2: Reduction tensors. The index function maps each index to a multiset of indices of the underlying tensor, whose values, gathered by $\bar{U}\circ\psi$ , are then reduced.

Panel of Figure 3 — Figure 3: Sparse matrices, represented as sum tensors.

Panel of Figure 4 — Figure 4: Stacking, and element-wise operations between several tensors, represented as reductions over a stack.

Panel of Figure 5 — Figure 5: Dense matrix multiplication $C=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.

Panel of Figure 6 — Figure 6: Element-wise product $A_{1}\odot A_{2}$ of a diagonal matrix $A_{1}=\Sigma\circ\overline{U_{1}}\circ\psi_{1}$ and an anti-diagonal matrix $A_{2}=\Sigma\circ\overline{U_{2}}\circ\psi_{2}$ (Theorem 2 ). Only $1$ product is computed, instead of $9$ . Subfigure (a) shows the inputs, (b) computes the product $Y$ 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 ${\mathcal{Q}}$ are in red, and those outside of ${\mathcal{Q}}$ , which are not needed, are gray.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

PyTorch code	Tensor
torch.zeros(M, N)	$\Sigma\circ\bar{U}\circ\psi:[M]\times[N]\to{\mathbb{R}}$ $U:\emptyset\to{\mathbb{R}}$ $\psi({\boldsymbol{v}})=\{\!\!\{\}\!\!\}$
torch.ones(M, N)	$\Pi\circ\bar{U}\circ\psi:[M]\times[N]\to{\mathbb{R}}$ $U:\emptyset\to{\mathbb{R}}$ $\psi({\boldsymbol{v}})=\{\!\!\{\}\!\!\}$
torch.tanh(A) A.shape: (M, N)	$\tanh{}\circ A:[M]\times[N]\to{]}{-1},1{[}$ $\tanh:{\mathbb{R}}\to{]}{-1},1{[}$
torch.transpose(A, 0, 1) A.shape: (M, N)	$A\circ\rho:[N]\times[M]\to{\mathbb{R}}$ $\rho(n,m)=(m,n)$
A.reshape(M, N) A.shape: (M*N,)	$A\circ\rho:[M]\times[N]\to{\mathbb{R}}$ $\rho(m,n)=N(m-1)+n$
A[:, j] A.shape: (M, N)	$A\circ\rho:[M]\to{\mathbb{R}}$ $\rho(m)=(m,j+1)$

Appendix

Table 1: Translation of common PyTorch operations into our algebra of compositions.

Mar 9, 2026

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

A tensor-relational computation is a relational computation where individual tuples carry vectors, matrices, or higher-dimensional arrays. An advantage of tensor-relational computation is that the overall computation can be executed on top of a relational system, inheriting the system's ability to automatically handle very large inputs with high levels of sparsity while high-performance kernels (such as optimized matrix-matrix multiplication codes) can be used to perform most of the underlying mathematical operations. In this paper, we introduce upper-case-lower-case EinSum, which is a tensor-relational version of the classical Einstein Summation Notation. We study how to automatically rewrite a computation in Einstein Notation into upper-case-lower-case EinSum so that computationally intensive components are executed using efficient numerical kernels, while sparsity is managed relationally.

Yuxin Tang, Zhiyuan Xin, Zhimin Ding +4

Rice University Houston, Texas, USA

High-Performance Computing

Ask PDF

Oct 31, 2026

Lightweight Representation Learning for Low Tucker Rank Tensors

Low Tucker rank tensors provide compact representations of multidimensional dependencies, but standard learning pipelines can incur substantial computational and memory overhead from redundant intermediate quantities. We reduce this overhead without modifying the underlying representation objective or parameterization. Our approach combines three complementary components: (i) sequential extraction of only task-required spectral components, avoiding unnecessary full decompositions; (ii) factor-wise multilinear contractions without materializing large Kronecker operators; and (iii) compact latent-state updates without storing full ambient tensor iterates. These components preserve the algebraic operations and learning trajectories of the original algorithms while reducing their computational and memory footprints. Across five low Tucker rank tensor estimators, our implementations match the original trajectories to numerical precision (relative discrepancies of

10^{-16}

10^{-13}

), while reducing per-iteration runtime by up to

3.12\times

and resident memory by up to

616\times

(

99.8\%

) on the main order-3 benchmark at

n=100

, with memory reductions exceeding

900\times

across the full evaluation suite. These results show that substantial computational redundancy can be eliminated from Tucker representation learning without changing the underlying model or learned representation.

Hiroki Hasegawa, Yukihiko Okada

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

Low-Rank Representation Learning Representation Learning Tucker Decomposition

Ask PDF

Jul 30, 2026

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

Tensor operations represent a cornerstone of modern scientific computing. However, the Numpy-like notation adopted by predominant tensor frameworks is often difficult to read and write and prone to so-called shape errors, i.a., due to following inconsistent rules across a large, complex collection of operations. Alternatives like einsum and einops have gained popularity, but are inherently restricted to few operations and lack the generality required for a universal model of tensor programming. To derive a better paradigm, we revisit vectorization as a function for transforming tensor operations, and use it to both lift lower-order operations to higher-order operations, and conceptually decompose higher-order operations to lower-order operations and their vectorization. Building on the universal nature of vectorization, we introduce einx, a universal notation for tensor operations. It uses declarative, pointful expressions that are defined by analogy with loop notation and represent the vectorization of tensor operations. The notation reduces the large APIs of existing frameworks to a small set of elementary operations, applies consistent rules across all operations, and enables a clean, readable and writable representation in code. We provide an implementation of einx that is embedded in Python and integrates seamlessly with existing tensor frameworks: https://github.com/fferflo/einx

Florian Fervers, Sebastian Bullinger, Christoph Bodensteiner +1

Fraunhofer IOSB

Topic pending

Ask PDF

Abstract

Explore similar work

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

Lightweight Representation Learning for Low Tucker Rank Tensors

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