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.
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
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
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· ACM Transactions on Architec...· 0 citations
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
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
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.