Home // INFOCOMP 2017, The Seventh International Conference on Advanced Communications and Computation // View article

A Parallel Nonzero CP Decomposition Algorithm for Higher Order Sparse Data Analysis

Authors:
Oguz Kaya

Keywords: parallel sparse tensor factorization; CP decomposition; higher order data analysis

Abstract:
In the age of big data, tensor decomposition methods are increasingly being used due to their ability to naturally express and analyze high dimensional big data. Obtaining these decompositions gets very expensive both in terms of computa- tional and memory requirements, particularly as the tensor’s dimensionality increases. To efficiently handle such high dimensional tensors, we propose a parallel algorithm for computing a CP decomposition in which factor matrices are assumed to not contain any zero elements. This additional constraint enables a very efficient computation of the costliest step of the algorithms for computing CANDECOMP/PARAFAC (CP) decomposition for high dimensional tensors, and the performance gains increase with the dimensionality of tensor. For an N-dimensional tensor having k nonzero entries, our method provides O(log k) and O(log N log k) faster preprocessing times, and performs O(N) and O(log N) less work in computing a CP decomposition over two efficient state-of-the-art libraries Splatt and Hypertensor, respectively. With these algorithmic contributions and a highly tuned parallel implementation, we achieve up to 16.7x speedup in sequential, and up to 10.5x speedup in parallel executions over these libraries on a 28-core workstation. In doing so, we incur with up to 24x less preprocessing time, and use up to O(log N) less memory for storing intermediate computations. We show using a real-world tensor that the accuracy of our method is comparable to the standard CP decomposition.

Pages: 40 to 45

Copyright: Copyright (c) IARIA, 2017

Publication date: June 25, 2017

Published in: conference

ISSN: 2308-3484

ISBN: 978-1-61208-567-8

Location: Venice, Italy

Dates: from June 25, 2017 to June 29, 2017