1. PARALLEL CANDECOMP/PARAFAC DECOMPOSITION OF SPARSE TENSORS USING DIMENSION TREES.
- Author
-
Kaya, Oguz and Uçar, Bora
- Subjects
- *
TENSOR algebra , *PARALLEL algorithms - Abstract
CANDECOMP/PARAFAC (CP) decomposition of sparse tensors has been success- fully applied to many problems in web search, graph analytics, recommender systems, health care data analytics, and many other domains. In these applications, efficiently computing the CP de- composition of sparse tensors is essential in order to be able to process and analyze data of massive scale. For this purpose, we investigate an efficient computation of the CP decomposition of sparse tensors and its parallelization. We propose a novel computational scheme for reducing the cost of a core operation in computing the CP decomposition with the traditional alternating least squares (CP-ALS) based algorithm. We then effectively parallelize this computational scheme in the context of CP-ALS in shared and distributed memory environments and propose data and task distribution models for better scalability. We implement parallel CP-ALS algorithms and compare our imple- mentations with an efficient tensor factorization library using tensors formed from real-world and synthetic datasets. With our algorithmic contributions and implementations, we report up to 5.96x, 5.65x, and 3.9x speedup in sequential, shared memory parallel, and distributed memory parallel executions over the state of the art and achieve strong scalability up to 4096 cores on an IBM BlueGene/Q supercomputer. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF