用函数复合统一表示张量运算，稀疏张量乘法可自动只算非零项
Representing Tensors as Compositions for Efficient Computation on Sparse and Structured Data
写张量计算库的朋友可以看看这篇。它把稠密、稀疏、锯齿张量和einsum统一成函数复合，稀疏矩阵乘法自动跳过零元素，复杂度从O(mn²)降到O(m+k²)，代码草案已开源。
一篇arXiv论文提出新的数学形式化方法：把所有张量表示为从索引到值的函数，张量运算则统一为函数复合。元素级操作（如激活函数）是作用在值上的复合，reshape、转置等重索引是作用在索引上的复合，而归约操作（求和、求积、取最大）由索引函数与归约运算共同复合而成。
结合张量堆叠，这套复合代数可以表示稠密、锯齿、各种稀疏模式以及矩阵分解等张量类型，并能懒惰化实现现代张量框架中的绝大多数操作，包括任意类型张量之间的einsum。利用复合式之间的恒等关系，可以在不求值的情况下改写表达式，例如两个稀疏矩阵的乘积可被改写为只在非零值之间做乘法，避免稀疏问题退化为稠密计算。
作者认为，若将这套代数作为张量计算引擎的中间表示，可以把代码库复杂度从O(mn²)（m为张量间二元操作数、n为张量类型数）降到O(m+k²)（k为索引函数类型数），即从为每种张量类型定义操作转向只定义索引函数上的代数。一个基于该代数的张量计算框架草案已开源。
Representing Tensors as Compositions for Efficient Computation on Sparse and Structured Data
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.
This report is categorized under AITOP's "Papers" desk. Within our cross-regional analytical framework, it directly maps to AI developer toolchains, coding agents, and engineering workflows. Key entities and technical topics under continuous tracking include 张量计算, 稀疏矩阵, einsum, 函数复合.
Source attribution: curated from arXiv cs.LG (@Valérian Rey, Praneth Paruchuri).
