Tensor-matrix products with a compressed sparse tensor

Shaden Smith, George Karypis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

73 Scopus citations


The Canonical Polyadic Decomposition (CPD) of tensors is a powerful tool for analyzing multi-way data and is used extensively to analyze very large and extremely sparse datasets. The bottleneck of computing the CPD is multiplying a sparse tensor by several dense matrices. Algorithms for tensormatrix products fall into two classes. The first class saves oating point operations by storing a compressed tensor for each dimension of the data. These methods are fast but super high memory costs. The second class uses a single uncompressed tensor at the cost of additional oating point operations. In this work, we bridge the gap between the two approaches and introduce the compressed sparse fiber (CSF) a data structure for sparse tensors along with a novel parallel algorithm for tensor-matrix multiplication. CSF offers similar operation reductions as existing compressed methods while using only a single tensor structure. We validate our contributions with experiments comparing against state-ofthe- art methods on a diverse set of datasets. Our work uses 58% less memory than the state-of-the-art while achieving 81% of the parallel performance on 16 threads.

Original languageEnglish (US)
Title of host publicationProceedings of the 5th Workshop on Irregular Applications
Subtitle of host publicationArchitectures and Algorithms, IA3 2015
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450340014
StatePublished - Nov 15 2015
Event5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015 - Austin, United States
Duration: Nov 15 2015 → …

Publication series

NameProceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015


Other5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015
Country/TerritoryUnited States
Period11/15/15 → …

Bibliographical note

Funding Information:
This work was supported in part by NSF (IIS-0905220, OCI- 1048018, CNS-1162405, IIS-1247632, IIP-1414153, IIS-1447788), Army Research Office (W911NF-14-1-0316), Intel Software and Services Group, and the Digital Technology Center at the University of Minnesota. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing Institute.


Dive into the research topics of 'Tensor-matrix products with a compressed sparse tensor'. Together they form a unique fingerprint.

Cite this