# Efficient parallel CP decomposition with pairwise perturbation and multi-sweep dimension tree

arXiv: https://arxiv.org/abs/2010.12056 · HTML: https://mlsanity.com/paper/2010.12056/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2020.

## Built on by (most cited first, 4 of 4)

- [Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions](https://mlsanity.com/paper/2104.01101/) (2021)
- [Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs](https://mlsanity.com/paper/2205.13163/) (2022)
- [Alternating Mahalanobis Distance Minimization for Stable and Accurate CP Decomposition](https://mlsanity.com/paper/2204.07208/) (2022)
- [Efficient Tensor Completion Algorithms for Highly Oscillatory Operators](https://mlsanity.com/paper/2510.17734/) (2025)

## Abstract (arXiv)

CP tensor decomposition with alternating least squares (ALS) is dominated in cost by the matricized-tensor times Khatri-Rao product (MTTKRP) kernel that is necessary to set up the quadratic optimization subproblems. State-of-art parallel ALS implementations use dimension trees to avoid redundant computations across MTTKRPs within each ALS sweep. In this paper, we propose two new parallel algorithms to accelerate CP-ALS. We introduce the multi-sweep dimension tree (MSDT) algorithm, which requires the contraction between an order N input tensor and the first-contracted input matrix once every (N-1)/N sweeps. This algorithm reduces the leading order computational cost by a factor of 2(N-1)/N relative to the best previously known approach. In addition, we introduce a more communication-efficient approach to parallelizing an approximate CP-ALS algorithm, pairwise perturbation. This technique uses perturbative corrections to the subproblems rather than recomputing the contractions, and asymptotically accelerates ALS. Our benchmark results show that the per-sweep time achieves 1.25X speed-up for MSDT and 1.94X speed-up for pairwise perturbation compared to the state-of-art dimension trees running on 1024 processors on the Stampede2 supercomputer.