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

Abstract

Tensors provide a natural representation for multi-dimensional data, and Tucker decomposition via Higher-Order Orthogonal Iteration (HOOI) is widely used to uncover their latent structure. Many tensors that arise in practice are highly sparse. On GPUs, sparse HOOI is bottlenecked by the tensor-times-matrix chain (TTMc) and the full singular value decomposition (SVD). TTMc suffers from load imbalance, while SVD incurs high time and workspace costs. Prior GPU work has focused primarily on TTMc, leaving the SVD update largely unoptimized. At high sparsity, SVD can dominate iteration time. At large mode dimensions, it can exhaust GPU memory entirely. We present SAKTHI, an end-to-end GPU framework that optimizes the full sparse HOOI pipeline. For TTMc, SAKTHI operates on the Compressed Sparse Fiber (CSF) format and adaptively selects between two kernels. IntraDyn uses intra-SM dynamic scheduling to eliminate global atomics for third-order tensors when fibers are reasonably uniform. FullDyn combines a one-time task decomposition with global warp scheduling to address both intra- and inter-slice imbalance when the fiber-length distribution is highly irregular. For SVD, SAKTHI replaces the full SVD with a Gram-matrix-based truncated SVD, gated at runtime by a gap-to-noise-ratio condition derived from a perturbation analysis. On a range of real-world and synthetic sparse tensors, SAKTHI 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.