Skip to content
Book Open access

From 2^N to N^2: Tree-Free Scalable Sparse Symmetric Tucker Decomposition

Sep 2026 · Proceedings of the International Conference on Parallel Processing · 0 citations · 32 references

Abstract

Symmetric sparse tensors arise naturally from multi-relational data, such as co-purchasing patterns, co-authorship networks, and temporal interaction data, and Tucker decomposition of such data extracts low-rank latent structure. The primary computational bottleneck is the Symmetric Sparse Tensor Times Same Matrix Chain (S3TTMc), which contracts the tensor with the factor matrix along all but one mode through a Kronecker product per nonzero. State-of-the-art methods exploit redundancy across nonzeros that share common index subsequences by organizing computation on a global prefix tree, enabling memoization of intermediate Kronecker products. However, as tensor dimensions grows, nonzero indices overlap less and the housekeeping cost of maintaining the tree grows exponentially, leaving \(\mathcal {O}(2^N)\) intermediate products per nonzero, multi-gigabyte working sets, and a traversal order that limits parallel scalability. We propose SPLIT N2, a nonzero-parallel algorithm that eliminates the tree: a chain of symmetric extensions reduces the per-nonzero cost from \(\mathcal {O}(2^N)\) to \(\mathcal {O}(N^2)\) symmetric vector–tensor products, computed independently for each nonzero. On real-world and synthetic tensors, SPLIT N2 achieves up to 504 × kernel speedup and 109 × end-to-end Tucker decomposition speedup, with 4–7 orders-of-magnitude reduction in memory footprint. Since its memory footprint depends only on rank and tensor order—not on the global index structure—SPLIT N2 enables decomposition of tensors with higher orders, larger dimensions, more nonzeros, and higher ranks than any prior tree-based method.

Read PDF

Similar papers

Preprint Oct 2026

Efficient Optimization of Tensor Rings with Low-Rank Environments

Tensor-ring (TR) decompositions provide a natural representation of periodic systems but are difficult to optimize because the closed geometry prevents a global canonical form and leads to costly, ill-conditioned environments. Existing periodic Density Matrix Renormalization Group (DMRG) methods alleviate this difficul...

Matthieu Jeannin, A. Chessari, J. von Delft · 0 citations
Preprint Sep 2026

Dense Matrices Are Alike; Sparse Matrices Are Sparse in Their Own Way: A Structure-Adaptive Tile Cholesky Factorization

A lightweight selector captures the sparsity pattern of the Cholesky factor and routes the matrix to one of three regimes: dense, sparse, or an intermediate semisparse regime, which achieves the lowest total factorization time in every regime.

Esmail Abdul Fattah, H. Ltaief, H. Rue et al. · 1 citation
Open access Sep 2026

SAKTHI: Sparse Tucker Acceleration via Adaptive Kernels for TTMc and SVD in HOOI

SAKTHI, an end-to-end GPU framework that optimizes the full sparse HOOI pipeline, delivers orders-of-magnitude end-to-end speedups over the prior state of the art, runs successfully on tensors where previous methods fail due to memory exhaustion, and produces matching fit.

Bhaskar Marati, Raghavendra Kanakagiri · 0 citations
#artificial intelligence Preprint Aug 2026

Iterative tensor network transformations for element-wise evaluation of elementary and filtering functions

Tensor networks are powerful formats for compressing large-scale data. However, their application to general data processing has been limited by the difficulty of performing nonlinear operations. Here, we introduce iterative tensor network transformations (ITNTs), a general algorithmic framework for the element-wise ev...

Xiao Wang, Tomohiro Hashizume, Pia Siegl et al. · 2 citations
#machine learning Preprint Sep 2026

CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs

CAST (Canonical Approximate Schur Tree) is introduced, which replaces this clique with a weighted random spanning tree sampled directly from it, and it is proved that its leverage-score marginals minimize the largest normalized reweighted-edge contribution among unbiased inverse-marginal one-tree estimators.

Meher Chaitanya, Cameron Musco, A. Gionis · 1 citation
Preprint Aug 2026

Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure

A stochastic, alternating least-squares algorithm that operates on smaller blocks of this dense matrix and scales as a result to much larger problems and is used to analyze the sparse matrix of synaptic weights for the recently published $\textit{Drosphilia}$ connectome.

Lawrence K. Saul, N. Huang, Dennis Bollweg et al. · 1 citation · ⚡1

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.