Parallel Nonnegative CP Decomposition of Dense Tensors

Grey Ballard; Koby Hayashi; Ramakrishnan Kannan

doi:10.1109/HiPC.2018.00012

Parallel Nonnegative CP Decomposition of Dense Tensors

Grey Ballard, Koby Hayashi, Ramakrishnan Kannan

Discrete Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

16 Scopus citations

Abstract

The CP tensor decomposition is a low-rank approximation of a tensor. We present a distributed-memory parallel algorithm and implementation of an alternating optimization method for computing a CP decomposition of dense tensors that can enforce nonnegativity of the computed low-rank factors. The principal task is to parallelize the Matricized-Tensor Times Khatri-Rao Product (MTTKRP) bottleneck subcomputation. The algorithm is computation efficient, using dimension trees to avoid redundant computation across MTTKRPs within the alternating method. Our approach is also communication efficient, using a data distribution and parallel algorithm across a multidimensional processor grid that can be tuned to minimize communication. We benchmark our software on synthetic as well as hyperspectral image and neuroscience dynamic functional connectivity data, demonstrating that our algorithm scales well to 100s of nodes (up to 4096 cores) and is faster and more general than the currently available parallel software.

Original language	English
Title of host publication	Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	22-31
Number of pages	10
ISBN (Electronic)	9781538683866
DOIs	https://doi.org/10.1109/HiPC.2018.00012
State	Published - Jul 2 2018
Event	25th IEEE International Conference on High Performance Computing, HiPC 2018 - Bengaluru, India Duration: Dec 17 2018 → Dec 20 2018

Publication series

Name	Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018

Conference

Conference	25th IEEE International Conference on High Performance Computing, HiPC 2018
Country/Territory	India
City	Bengaluru
Period	12/17/18 → 12/20/18

Funding

This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan). This manuscript has been co-authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. This research used resources of the Oak Ridge Leadership Computing Facility at the Oak Ridge National Laboratory, which is supported by the Office of Science of the U.S. Department of Energy. This project was partially funded by the Laboratory Director’s Research and Development fund at ORNL. This manuscript has been co-authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. This research used resources of the Oak Ridge Leadership Computing Facility at the Oak Ridge National Laboratory, which is supported by the Office of Science of the U.S. Department of Energy. This project was partially funded by the Laboratory Director's Research and Development fund at ORNL. This work has also been funded in part by the Laboratory-Directed Research & Development program at Sandia National Laboratories. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology and Engineering Solutions of Sandia, LLC., a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy's National Nuclear Security Administration under contract DE-NA- 0003525. This material is also based upon work supported by the National Science Foundation Grant No. ACI-1642385.

Funders	Funder number
UT-Battelle, LLC
National Science Foundation	1642385
U.S. Department of Energy
Office of Science
National Nuclear Security Administration	DE-NA-0003525
Oak Ridge National Laboratory
Sandia National Laboratories
National Science Foundation	ACI-1642385

Keywords

CP Decomposition
Lowrank Approximation
MTTKRP
Tensor

Access to Document

10.1109/HiPC.2018.00012

Cite this

Ballard, G., Hayashi, K., & Kannan, R. (2018). Parallel Nonnegative CP Decomposition of Dense Tensors. In Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018 (pp. 22-31). Article 8638076 (Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/HiPC.2018.00012

@inproceedings{f54085f336f648bb927b29cfdc6e14af,

title = "Parallel Nonnegative CP Decomposition of Dense Tensors",

abstract = "The CP tensor decomposition is a low-rank approximation of a tensor. We present a distributed-memory parallel algorithm and implementation of an alternating optimization method for computing a CP decomposition of dense tensors that can enforce nonnegativity of the computed low-rank factors. The principal task is to parallelize the Matricized-Tensor Times Khatri-Rao Product (MTTKRP) bottleneck subcomputation. The algorithm is computation efficient, using dimension trees to avoid redundant computation across MTTKRPs within the alternating method. Our approach is also communication efficient, using a data distribution and parallel algorithm across a multidimensional processor grid that can be tuned to minimize communication. We benchmark our software on synthetic as well as hyperspectral image and neuroscience dynamic functional connectivity data, demonstrating that our algorithm scales well to 100s of nodes (up to 4096 cores) and is faster and more general than the currently available parallel software.",

keywords = "CP Decomposition, Lowrank Approximation, MTTKRP, Tensor",

author = "Grey Ballard and Koby Hayashi and Ramakrishnan Kannan",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 25th IEEE International Conference on High Performance Computing, HiPC 2018 ; Conference date: 17-12-2018 Through 20-12-2018",

year = "2018",

month = jul,

day = "2",

doi = "10.1109/HiPC.2018.00012",

language = "English",

series = "Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "22--31",

booktitle = "Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018",

}

Ballard, G, Hayashi, K & Kannan, R 2018, Parallel Nonnegative CP Decomposition of Dense Tensors. in Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018., 8638076, Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018, Institute of Electrical and Electronics Engineers Inc., pp. 22-31, 25th IEEE International Conference on High Performance Computing, HiPC 2018, Bengaluru, India, 12/17/18. https://doi.org/10.1109/HiPC.2018.00012

Parallel Nonnegative CP Decomposition of Dense Tensors. / Ballard, Grey; Hayashi, Koby; Kannan, Ramakrishnan.
Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 22-31 8638076 (Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Parallel Nonnegative CP Decomposition of Dense Tensors

AU - Ballard, Grey

AU - Hayashi, Koby

AU - Kannan, Ramakrishnan

PY - 2018/7/2

Y1 - 2018/7/2

N2 - The CP tensor decomposition is a low-rank approximation of a tensor. We present a distributed-memory parallel algorithm and implementation of an alternating optimization method for computing a CP decomposition of dense tensors that can enforce nonnegativity of the computed low-rank factors. The principal task is to parallelize the Matricized-Tensor Times Khatri-Rao Product (MTTKRP) bottleneck subcomputation. The algorithm is computation efficient, using dimension trees to avoid redundant computation across MTTKRPs within the alternating method. Our approach is also communication efficient, using a data distribution and parallel algorithm across a multidimensional processor grid that can be tuned to minimize communication. We benchmark our software on synthetic as well as hyperspectral image and neuroscience dynamic functional connectivity data, demonstrating that our algorithm scales well to 100s of nodes (up to 4096 cores) and is faster and more general than the currently available parallel software.

AB - The CP tensor decomposition is a low-rank approximation of a tensor. We present a distributed-memory parallel algorithm and implementation of an alternating optimization method for computing a CP decomposition of dense tensors that can enforce nonnegativity of the computed low-rank factors. The principal task is to parallelize the Matricized-Tensor Times Khatri-Rao Product (MTTKRP) bottleneck subcomputation. The algorithm is computation efficient, using dimension trees to avoid redundant computation across MTTKRPs within the alternating method. Our approach is also communication efficient, using a data distribution and parallel algorithm across a multidimensional processor grid that can be tuned to minimize communication. We benchmark our software on synthetic as well as hyperspectral image and neuroscience dynamic functional connectivity data, demonstrating that our algorithm scales well to 100s of nodes (up to 4096 cores) and is faster and more general than the currently available parallel software.

KW - CP Decomposition

KW - Lowrank Approximation

KW - MTTKRP

KW - Tensor

UR - http://www.scopus.com/inward/record.url?scp=85062823352&partnerID=8YFLogxK

U2 - 10.1109/HiPC.2018.00012

DO - 10.1109/HiPC.2018.00012

M3 - Conference contribution

AN - SCOPUS:85062823352

T3 - Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018

SP - 22

EP - 31

BT - Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 25th IEEE International Conference on High Performance Computing, HiPC 2018

Y2 - 17 December 2018 through 20 December 2018

ER -

Ballard G, Hayashi K, Kannan R. Parallel Nonnegative CP Decomposition of Dense Tensors. In Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018. Institute of Electrical and Electronics Engineers Inc. 2018. p. 22-31. 8638076. (Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018). doi: 10.1109/HiPC.2018.00012

Parallel Nonnegative CP Decomposition of Dense Tensors

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this