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

• URL: http://arxiv.org/abs/2603.08957v1
• Date: Mon, 09 Mar 2026 21:43:39 GMT
• Title: Automated Tensor-Relational Decomposition for Large-Scale Sparse Tensor Computation
• Abstract summary: We introduce upper-case-lower-case textttEinSum, which is a tensor-relational version of the classical Einstein Summation Notation.<n>We study how to automatically rewrite a computation in Einstein Notation into upper-case-lower-case textttEinSum so that computationally intensive components are executed using efficient numerical kernels.
• Score: 10.683298568098076
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: A \emph{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 \texttt{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 \texttt{EinSum} so that computationally intensive components are executed using efficient numerical kernels, while sparsity is managed relationally.

Related papers

• Efficient Tensor Completion Algorithms for Highly Oscillatory Operators [7.563400478703737]
  This paper presents low-complexity tensor completion algorithms and their efficient implementation.<n>The underlying tensor decomposition is based on the reshaping of the input matrix and its butterfly decomposition into an order $O (log n)$ tensor.
  arXiv  Detail & Related papers  (2025-10-20T16:45:59Z)
• Scaling Probabilistic Circuits via Monarch Matrices [109.65822339230853]
  Probabilistic Circuits (PCs) are tractable representations of probability distributions.<n>We propose a novel sparse and structured parameterization for the sum blocks in PCs.
  arXiv  Detail & Related papers  (2025-06-14T07:39:15Z)
• Determinant Estimation under Memory Constraints and Neural Scaling Laws [48.68885778257016]
  We derive a novel hierarchical algorithm for large-scale log-determinant calculation in memory-constrained settings.<n>We show that the ratio of pseudo-determinants satisfies a power-law relationship, allowing us to derive corresponding scaling laws.<n>This enables accurate estimation of NTK log-determinants from a tiny fraction of the full dataset.
  arXiv  Detail & Related papers  (2025-03-06T13:32:13Z)
• Fast Causal Discovery by Approximate Kernel-based Generalized Score Functions with Linear Computational Complexity [29.444911198185206]
  We propose an approximate kernel-based generalized score function with $mathcalO(n)$ time and space complexities.<n>Our method can not only significantly reduce computational costs, but also achieve comparable accuracy, especially for large datasets.
  arXiv  Detail & Related papers  (2024-12-23T16:51:45Z)
• Computing with Residue Numbers in High-Dimensional Representation [7.736925756277564]
  We introduce Residue Hyperdimensional Computing, a computing framework that unifies residue number systems with an algebra defined over random, high-dimensional vectors. We show how residue numbers can be represented as high-dimensional vectors in a manner that allows algebraic operations to be performed with component-wise, parallelizable operations on the vector elements.
  arXiv  Detail & Related papers  (2023-11-08T18:19:45Z)
• Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
  We present a novel distributed computing framework that is robust to slow compute nodes, and is capable of both approximate and exact computation of linear operations. We propose a sequential decoding algorithm designed to handle real valued data while maintaining low computational complexity for recovery. We demonstrate the potential applications of this framework in various contexts, such as large-scale matrix multiplication and black-box optimization.
  arXiv  Detail & Related papers  (2023-09-01T18:02:04Z)
• Learning distributed representations with efficient SoftMax normalization [3.8673630752805437]
  We propose a linear-time approximation to compute the normalization constants of $rm SoftMax(XYT)$ for embedding vectors with bounded norms.<n>We show on some pre-trained embedding datasets that the proposed estimation method achieves higher or comparable accuracy with competing methods.<n>The proposed algorithm is interpretable and easily adapted to arbitrary embedding problems.
  arXiv  Detail & Related papers  (2023-03-30T15:48:26Z)
• Linear Self-Attention Approximation via Trainable Feedforward Kernel [77.34726150561087]
  In pursuit of faster computation, Efficient Transformers demonstrate an impressive variety of approaches. We aim to expand the idea of trainable kernel methods to approximate the self-attention mechanism of the Transformer architecture.
  arXiv  Detail & Related papers  (2022-11-08T08:14:11Z)
• Arithmetic circuit tensor networks, multivariable function representation, and high-dimensional integration [0.0]
  We introduce a direct mapping from the arithmetic circuit of a function to circuit tensor networks. We demonstrate the power of the circuit construction in examples of multivariable integration on the unit hypercube in up to 50 dimensions.
  arXiv  Detail & Related papers  (2022-08-16T23:02:14Z)
• On Algebraic Constructions of Neural Networks with Small Weights [21.915057426589748]
  We study the trade-offs among the weight sizes, circuit size and depth of neural gates. Specifically, given a single linear equation with arbitrary coefficients, we would like to express it using a system of linear equations with smaller (even constant) coefficients. We explicitly construct a constant weight, optimal size matrix to compute the EQUALITY function. We prove the existence of the best-known weight size (linear) matrices to compute the COMPARISON function.
  arXiv  Detail & Related papers  (2022-05-17T00:09:23Z)
• Automatic differentiation for Riemannian optimization on low-rank matrix and tensor-train manifolds [71.94111815357064]
  In scientific computing and machine learning applications, matrices and more general multidimensional arrays (tensors) can often be approximated with the help of low-rank decompositions. One of the popular tools for finding the low-rank approximations is to use the Riemannian optimization.
  arXiv  Detail & Related papers  (2021-03-27T19:56:00Z)
• Tensor Relational Algebra for Machine Learning System Design [7.764107702934616]
  We present an alternative implementation abstraction called the relational tensor algebra (TRA) TRA is a set-based algebra based on the relational algebra. Our empirical study shows that the optimized TRA-based back-end can significantly outperform alternatives for running ML in distributed clusters.
  arXiv  Detail & Related papers  (2020-09-01T15:51:24Z)
• Coded Distributed Computing with Partial Recovery [56.08535873173518]
  We introduce a novel coded matrix-vector multiplication scheme, called coded computation with partial recovery (CCPR) CCPR reduces both the computation time and the decoding complexity by allowing a trade-off between the accuracy and the speed of computation. We then extend this approach to distributed implementation of more general computation tasks by proposing a coded communication scheme with partial recovery.
  arXiv  Detail & Related papers  (2020-07-04T21:34:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.