Distributed-Memory Randomized Algorithms for Sparse Tensor CP Decomposition

Abstract

Candecomp / PARAFAC (CP) decomposition, a generalization of the matrix singular value decomposition to higher-dimensional tensors, is a popular tool for analyzing multidimensional sparse data. On tensors with billions of nonzero entries, computing a CP decomposition is a computationally intensive task. We propose the first distributed-memory implementations of two randomized CP decomposition algorithms, CP-ARLS-LEV and STS-CP, that offer nearly an order-of-magnitude speedup at high decomposition ranks over well-tuned non-randomized decomposition packages. Both algorithms rely on leverage score sampling and enjoy strong theoretical guarantees, each with varying time and accuracy tradeoffs. We tailor the communication schedule for our random sampling algorithms, eliminating expensive reduction collectives and forcing communication costs to scale with the random sample count. Finally, we optimize the local storage format for our methods, switching between analogues of compressed sparse column and compressed sparse row formats. Experiments show that our methods are fast and scalable, producing 11x speedup over SPLATT by decomposing the billion-scale Reddit tensor on 512 CPU cores in under two minutes.

To appear in the Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'24). 14 pages, 13 figures, 5 tables

References in corpus (6)

• Minimum Cost Loop Nests for Contraction of a Sparse Tensor with a Tensor Network
• Sketching for Kronecker Product Regression and P-splines
• Fast Exact Leverage Score Sampling from Khatri-Rao Products with Applications to Tensor Decomposition
• More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees
• SpDISTAL: Compiling Distributed Sparse Tensor Computations
• Dynasor: A Dynamic Memory Layout for Accelerating Sparse MTTKRP for Tensor Decomposition on Multi-core CPU